I'm having trouble constructing a Context Free Grammar for the following language: $$a^{\ast}b^{\ast}c^{\ast} - \{a^{n} b^{n} c^{n} \mid n \geq 0 \}$$

I believe it's telling me that no string can be generated that has the same number of of $a$'s $b$'s and $c$'s. This is due to the subtraction of the second set.

A good string from a newly formed language should be something like $aaabbc$ or $abbbcc$ and so on.

So I tried breaking the problem into three parts...

  • Single states:
    1. $S_{1} \rightarrow aS_{1} \mid a \mid \lambda$
    2. $S_{2} \rightarrow bS_{2} \mid b \mid \lambda$
    3. $S_{3} \rightarrow cS_{2} \mid b \mid \lambda$
  • Two States
    1. $S_{4} \rightarrow aS_{4}b \mid S_{1} \mid S_{2}$
    2. $S_{5} \rightarrow bS_{5}c \mid S_{2}$
    3. $S_{6} \rightarrow aS_{6}c \mid S_{3} \mid S_{1}$
  • States w/AB states
    1. $S_{7} \rightarrow S_{1} \mid S_{4}S_{6}$
    2. $S_{8} \rightarrow S_{2} \mid S_{5}S_{6}$
    3. $S_{9} \rightarrow S_{3} \mid S_{6}S_{3}$

with an orginal start state of ...

$$ S \rightarrow S_{7} \mid S_{8} \mid S_{9} $$

However I'm having problems building strings like $aaaabbbcc$ ...

Am I forming CFG's incorrectly? I felt like I was on the right track but now I'm quite lost.

  • 2
    $\begingroup$ Why do you think the subtraction deletes all strings with an even number of $a$s, $b$s and $c$s? It says nothing about evenness. $\endgroup$ – David Richerby Apr 28 '15 at 23:11
  • $\begingroup$ We have answered the original question before, but you are also asking about your attempts. $\endgroup$ – Raphael Apr 29 '15 at 14:57
  • $\begingroup$ The previous question was about building the PDA. Of course, there are standard constructions from one to the other, but not so easy to use in practice. $\endgroup$ – babou May 3 '15 at 19:15

This question has been answered before, but let me summarize the answer: $$ a^*b^*c^* \setminus \{ a^n b^n c^n \} = \\ \{ a^{n+1+m} b^n c^p \} \cup \{ a^n b^{n+1+m} c^p \} \cup \\ \{ a^{n+1+m} b^p c^n \} \cup \{ a^n b^p c^{n+1+m} \} \cup \\ \{ a^p b^{n+1+m} c^n \} \cup \{ a^p b^n c^{n+1+m} \}. $$ All parameters $n,m,p$ are assumed to be non-negative.

  • $\begingroup$ Do you have the link handy? $\endgroup$ – Raphael Apr 29 '15 at 8:58
  • $\begingroup$ No, and as we all know, searching stackexchange is very difficult. That's why I included the answer anyway. $\endgroup$ – Yuval Filmus Apr 29 '15 at 14:07
  • $\begingroup$ Well, good thing we can search or LaTeX; this is what you had in mind? I think we should close as duplicate, and merge your answer over there. That said, the OP was asking for feedback on their grammars which we don't really have provided until now, and such would make this question worthy to stand on its own. $\endgroup$ – Raphael Apr 29 '15 at 14:56
  • $\begingroup$ Yes, exactly what I had in mind. Thanks! I cannot quite make sense of the OP's question, and I'm doubtful it can get a meaningful answer, but if you're willing to give it a shot... $\endgroup$ – Yuval Filmus Apr 29 '15 at 14:58

The quick answer (no explanation):

The language $$L=a^*b^*c^* - \{a^n b^n c^n \mid n \geq 0 \}$$ is equal to

$$L=\{a^{i}b^{j} c^{k} \mid i\neq j\}\cup \{a^{i}b^{j}c^{k} \mid j\neq k\}$$ which is the union of two CF languages, thus CF. And writing a grammar for each should not be too difficult, from which one gets a CF grammar for $L$.

Of course, one can prove directly that this representation of the language is indeed correct. But I wondered what is a more systematic, or at least analytic, way of finding it. That is what I am presenting below, for whoever is interested. It is actually how I found this answer, pretty trivial in retrospect.

Understanding how I obtained that result

Warning: this goes a bit beyond the question.

Yuval Filmus gave previously a strong hint to answer this question, and a similar question was adressed previously. But I wondered whether this kind of problem can be adressed in a more systematic way, to prove that a language is CF, and to produce a grammar.

Thus, rather than just give a specific proof, I wish to analyze the example in details to understand what should be the strategy for a whole family of similar examples.

It is based on several facts:

  1. While CF languages are not closed under complementation general, many CF languages are also co-CF, i.e. have a CF complement. This in particular the case for deterministic CF languages. Deterministic CF languages seem to show up often in exercises, though possibly a bit hidden, as is the case here.

  2. CF languages are not closed under intersection, but they are closed under union.

  3. Properties defining a language, that appear as conjunctions, turn into disjonction when considering complements (De Morgan's law). From a language point of view, the complement of the intersection of two languages is the union of the complement of each: $\overline{L_1\cap L_2}=\overline{L_1}\cup\overline{L_2}$

  4. CF languages are closed under intersection with regular sets, and of course with union.

  5. A few other set relations can be handy. For example we have $L_1-L_2=L_1\cap\overline{L_2}$.

  6. Last, but not least, all the closure properties are constructive, so that one may always hope to use them to extract the grammar from the CF-ness proof. We could certainly build tools to do it for us. For example, a general CF parser (such as CYK) can be used to compute the grammar for the intersection of its language with any regular set.

We look at the example given: $$L=a^{\ast}b^{\ast}c^{\ast} - \{a^{n} b^{n} c^{n} \mid n \geq 0 \}$$ and we analyze it in much details, so as to understand better the techniques that can be used.
We note that: $$L=a^{\ast}b^{\ast}c^{\ast} - \{a^{n} b^{n} c^{n} \mid n \geq 0 \} =a^{\ast}b^{\ast}c^{\ast}\cap\overline{\{a^{n} b^{n} c^{n} \mid n \geq 0 \}}$$

Since $a^{\ast}b^{\ast}c^{\ast}$ is regular, $L$ is CF iff $L_1=\overline{\{a^{n} b^{n} c^{n} \mid n \geq 0 \}}$ is CF.

$$\begin{align} \overline{L_1}&=\{a^{n}b^{n} c^{n} \mid n \geq 0 \}\\ &=\{a^{i}b^{j} c^{k} \mid i=j=k \geq 0 \}\\ &=\{a^{i}b^{j} c^{k} \mid i=j\wedge j=k \wedge i,j,k \geq 0 \}\\ &=\{a^{i}b^{j} c^{k} \mid i=j\wedge j=k\}\\ &=\{a^{i}b^{j} c^{k} \mid i=j\}\cap\{a^{i}b^{j} c^{k} \mid j=k\} \end{align} $$ The last condition does not really matter here, since exponents are necessarily non-negative integers.

Thus $$\begin{align} L_1&=\overline{\{a^{i}b^{j} c^{k} \mid i=j\}\cap\{a^{i}b^{j} c^{k} \mid j=k\}}\\ &=\overline{\{a^{i}b^{j} c^{k} \mid i=j\}}\cup\overline{\{a^{i}b^{j}c^{k} \mid j=k\}}\\ \end{align} $$

The two languages $M'=\{a^{i}b^{j} c^{k} \mid i=j\}$ et $M''=\{a^{i}b^{j}c^{k} \mid j=k\}$ are obviously CF, as it is quite easy to build a DPDA for each of them. Hence their complements are also CF, and so is their union $L1$. So we conclude that $L$ is CF. From this alone, we could extract a grammar for it, by mechanical means. But this is not easy by hand, and we will go a bit further.

We will try to make the complements of $M'$ and $M''$ a bit more explicit. It is not easy, since it does include for each all the string such that $a$, $b$, and $c$ are not seggregated in the right order. But we can always use the friendly help of intersection with a regular set, precisely $a^{\ast}b^{\ast}c^{\ast}$, that we discarded earlier, as not useful to prove the CF-ness of $L$. It comes back handily to simplify our work for building a grammar.

So we return to $L= a^{\ast}b^{\ast}c^{\ast}\cap L_1$

$$\begin{align} L&= a^{\ast}b^{\ast}c^{\ast}\cap L_1\\ &=a^{\ast}b^{\ast}c^{\ast}\cap(\overline{\{a^{i}b^{j} c^{k} \mid i=j\}}\cup\overline{\{a^{i}b^{j}c^{k} \mid j=k\}})\\ &=(a^{\ast}b^{\ast}c^{\ast}\cap\overline{\{a^{i}b^{j} c^{k}\mid i=j\}}) \cup (a^{\ast}b^{\ast}c^{\ast}\cap\overline{\{a^{i}b^{j} c^{k}\mid j=k\}})\\ &=\{a^{i}b^{j} c^{k} \mid i\neq j\}\cup \{a^{i}b^{j}c^{k} \mid j\neq k\} \end{align} $$

Building a CF grammar for these two languages id a standard, and not very hard, exercise. From that you get a grammar for the union of these two languages.

This is unlikely to be the only way to get such results, but it should give some ideas to deal with such problems.


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