HiveBrain v1.2.0
Get Started
← Back to all entries
patternModerate

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

Submitted by: @import:stackexchange-cs··
0
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.

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.

Context

StackExchange Computer Science Q#11110, answer score: 12

Revisions (0)

No revisions yet.