0
$\begingroup$

Let $L$ be the language $\{w \mid w \text{ has equal numbers of \(a\)'s, \(b\)'s and \(c\)'s}\}$. Prove that its complement $\overline{L}$ is context free.

$\endgroup$
  • 1
    $\begingroup$ Is this class material? Copied from a book? An exercise problem? It is a very localized question, so I don't see how the solution to this problem is worthwhile adding under Encyclopedia Stack Exchange paradigm, so I'm going to close this. $\endgroup$ – Raphael Oct 28 '13 at 8:01
  • $\begingroup$ @Raphael I see your Encyclopedia Stack Exchange and raise you the Wikipedia of long tail questions. $\endgroup$ – Gilles Sep 27 '14 at 12:00
  • $\begingroup$ I just noticed that this is self-answered. Normally, this would not be considered a good question (because it is a problem dump, with no evidence of effort in the question, no attempt to pose a specific question, etc.). However I see that this is self-answered, which might make the question acceptable. Just noting my reasoning, since I initially overlooked that it was self-answered. $\endgroup$ – D.W. Sep 28 '14 at 1:43
  • $\begingroup$ @Raphael, If I say a language L= {w ∣ w has equal numbers of a's, b's, c's and d's}. Then is the complement of this language CSL ? $\endgroup$ – Garrick Oct 9 '16 at 17:54
3
$\begingroup$

So let us remember the closure properties of context-free languages, gone over in class and stated by the TFS:

* closed under union
* closed under concatenation
* closed under Kleene Star

Now I will show that my language $L'$ is the same as the language $L$. Let $NE(x,y,z)$ be an operation that generates a language such that the number of x's is not the same as the number of y's, with as many z's as one wants anywhere in the language. Thus my language $L'$ is defined as:

$$ NE(a,b,c) \cup NE(c,a,b) \cup NE(b,c,a) $$

This language is obviously $L$. It is all instances of a not equal to b, b not equal to c, and c not equal to a. The nice thing here is that if we prove $NE()$ is context free, then because of symetry and closure under union operation. Let us represent NE as a PDA here:

$$ (s,\epsilon,\epsilon) \rightarrow (p,\$) $$ $$ (p,a,\epsilon) \rightarrow (p,1) $$ $$ (p,b,1) \rightarrow (p,\epsilon) $$ $$ (p,b,\$) \rightarrow (m,1\$) $$ $$ (p,c,\epsilon) \rightarrow (p,\epsilon) $$ $$ (m,c,\epsilon) \rightarrow (p,\epsilon) $$ $$ (m,b,\epsilon) \rightarrow (m,1) $$ $$ (m,a,1) \rightarrow (m,\epsilon) $$ $$ (m,a,\epsilon) \rightarrow (p,1\$) $$ $$ (p,\epsilon,a) \rightarrow (f,\epsilon) $$ $$ (p,\epsilon,b) \rightarrow (f,\epsilon) $$ $$ (m,\epsilon,a) \rightarrow (f,\epsilon) $$ $$ (m,\epsilon,b) \rightarrow (f,\epsilon) $$

So now that I have represented this language as a PDA, all I need to show is that the language I represented corresponds to $NE()$.

First I will show that my PDA, $X$ is $X \subseteq NE$. This is quite easy to see. The only way that one can enter a final state in $X$ is when, under one of our rules, we hit the end of the string, and there is something left on the stack (meaning that there is an unequal number of either a's or b's). we can see here that this is a subset.

Next I will show that $X \supseteq NE$, or in other words, all strings that are part of $NE()$ can be made by $X$. One can see that one can have as many c's as one wants in this model, by the rules: $ (p/m,c,\epsilon) \rightarrow (p/m,\epsilon) $, so that is not a problem. But how does it promise that all strings of unequal number of a's and b's are not in this language. Again, the grammar only keeps track of how many excess a's or b's there are, and can accept any string of arbitrary length with any permutation of letters as long as one of a or b, has an excess. Thus $X \supseteq NE$.

I have shown that $NE$ is Context Free by building a PDA, and I have shown that $L$ is a finite union of $NE$s, thus $L$ is context-free.

$\endgroup$
1
$\begingroup$

Hint: if $w \notin L$ then for some two characters $\alpha,\beta$, $w$ has more of $\alpha$ than of $\beta$. It is enough to show that each such language $L_{\alpha\beta}$ is context-free. Here the idea is to suitably modify a grammar for $\{ w : w \text{ has the same number of $\alpha$'s as $\beta$'s}\}$.

$\endgroup$
  • $\begingroup$ what if i say a language L= w ∣w has equal numbers of a's, b's, c's and d's}. Then is the complement of this language CSL. $\endgroup$ – Garrick Oct 9 '16 at 17:46

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.