patternModerate
Are context-free languages in $a^*b^*$ closed under complement?
Viewed 0 times
freearelanguagesclosedundercomplementcontext
Problem
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.
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#11110, answer score: 12
Revisions (0)
No revisions yet.