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_1cap 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
