Are context-free languages in $a^*b^*$ closed under complement?

The context-free languages are not closed under complement, we know that.

As far as I understand, context-free languages that are a subset of $a^*b^*$ for some letters $a,b$ are closed under complement(!?)

Here is my argument. Each CF language $L$ has a semi-linear Parikh image $\pi(L) = \{ (m,n) \mid a^mb^n \in L \}$. Semilinear sets are closed under complement. The set of vectors that represent the semi-linear set can easily be transformed into a linear grammar.

Question. Is there an easily accessible reference to this fact?

Technically these languages are called bounded, i.e., a subset of $w_1^* \dots w_k^*$ for some words $w_1,\dots,w_k$.

My motivation for this question is from a recent question on the context-freeness of $\{ a^nb^m \mid n^2 \neq m \}$. Its complement within $a^*b^*$ seems easier to handle.

Hendrik Jan

Posted 2013-04-07T19:05:16.153

Reputation: 24 682

Have you checked Ginsburg's "The Mathematical Theory of Context-Free Languages"? Apparently, Theorem 5.4.2 gives the characterization of bounded context-free languages you're referring to, and I bet Ginsburg would mention the implication for complementing bounded context-free languages (in the two-dimensional case). – Yuval Filmus – 2013-04-08T01:32:23.143

Answers

This characterization of bounded context-free languages is due to Ginsburg ("The Mathematical Theory of Context-Free Languages"), and appears as Corollary 5.3.1 in his book. For general $k$ there are some restrictions on the semilinear sets, but for $k \leq 2$ these restrictions are always satisfied, and so it is straightforward to deduce that the complement of such a language (within $w_1^* w_2^*$) is context-free.

Ginsburg mentions these implications in his book.

Corollary 5.6.1 If $M_1 \subseteq w_1^*w_2^*$ and $M_2$ are [context-free] languages, $w_1$ and $w_2$ words, then $M_1\cap M_2$ is a [context-free] language.

Corollary 5.6.2 If $M_1 \subseteq w_1^*w_2^*$ and $M_2$ are [context-free] languages, $w_1$ and $w_2$ words, then $M_1 - M_2$ and $M_2-M_1$ are [context-free] languages.

Yuval Filmus

Posted 2013-04-07T19:05:16.153

Reputation: 245 786

Another proof uses the following characterization proved in this answer:

The language $\{ a^i b^j : (i,j) \in A \}$ is context-free iff $A$ is definable in Presburger arithmetic.

Clearly $A$ is definable in Presburger arithmetic iff $\overline{A}$ is definable in Presburger arithmetic.

This shows that if languages $L_i \subseteq a^*b^*$ are context-free then every Boolean expression in the languages (involving union, intersection, and complementation) is context-free as well.

Yuval Filmus

Posted 2013-04-07T19:05:16.153

Reputation: 245 786