[Solved]: Are context-free languages in $a^*b^*$ closed under complement?

Problem Detail: 

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.

Asked By : Hendrik Jan

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/11110