20
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – Yuval Filmus Apr 8 '13 at 1:32
12
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.