So the complement of L1 = $\{a^{n}b^{n}c^{n} \mid n \geq 1\}$ would be L2 = $\{a,b,c\}^* \setminus \{a^{n}b^{n}c^{n} \mid n \geq 1\}$.

In other words, any combinations of a,b and c where we dont have an equal number of all three letters and w = $\varepsilon$ is also legit.

However, while I'm certain that there should be a contextfree grammar for L2, I can't seem to find a grammer that allows you to generate the terminals freely without allowing $a^{n}b^{n}c^{n}$ with n $\geq$ 1.

My attempt was to make a starting Rule S -> $Q_{_{a}}$ ; $Q_{_{b}}$ ; $Q_{_{c}}$ ; $\varepsilon$ so that the individual Q rules would make it possible for two of the terminals a, b and c to have an equal number, but not for the third. (in $Q_{_{a}}$, a is restricted by max(b,c), in $Q_{_{b}}$, b is restricted by max(a,c), in $Q_{_{c}}$, c is restricted by max(a,b) so that the restricted terminal can never show up as often as the unrestricted terminal with the highest count)

The rules I set up though, only allow to have unlimited numbers of unrestricted terminals in any order. I'm not sure how to implement a rule for the restricted terminal, without allowing it to have as high a count as the unrestricted ones, if the unrestricted ones have the same count.

here's my P for G$_{_{L2}}$ so far

S $\rightarrow$ $Q_{_{a}}$ ; $Q_{_{b}}$ ; $Q_{_{c}}$ ; $\varepsilon$

$Q_{_{a}}$ $\rightarrow$ $Q_{_{a}}$b $Q_{_{a}}$ ; $Q_{_{a}}$c $Q_{_{a}}$ ; $\varepsilon$

$Q_{_{b}}$ $\rightarrow$ $Q_{_{b}}$a $Q_{_{b}}$ ; $Q_{_{b}}$c $Q_{_{b}}$ ; $\varepsilon$

$Q_{_{c}}$ $\rightarrow$ $Q_{_{c}}$a $Q_{_{c}}$ ; $Q_{_{c}}$b $Q_{_{c}}$ ; $\varepsilon$

These are still missing the rules for the individual restricted variable. In what fashion can I add those, without breaking the [ $a^{n}b^{n}c^{n}$ | n = 0 ] rule?

Edit: it occured to me that I could refine the restricting rules, such that the restricted terminal can be derived from a rule if, and only if one (and only one) of the unrestricted ones is always created with it. For example:

S $\rightarrow$ $Q_{_{a}}$ ; $Q_{_{b}}$ ; $Q_{_{c}}$ ; $\varepsilon$

$Q_{_{a}}$ $\rightarrow$ $Q_{_{ab}}$b $Q_{_{ab}}$ ; $Q_{_{ac}}$c $Q_{_{ac}}$

$Q_{_{ab}}$ $\rightarrow$ $Q_{_{ab}}$b $Q_{_{ab}}$ ; $Q_{_{ab}}$c $Q_{_{ab}}$ ; $Q_{_{ab}}$ a $Q_{_{ab}}$ b $Q_{_{ab}}$ ; $Q_{_{ab}}$ b $Q_{_{ab}}$ a $Q_{_{ab}}$ ; $\varepsilon$

$Q_{_{ac}}$ $\rightarrow$ $Q_{_{ac}}$b $Q_{_{ac}}$ ; $Q_{_{ac}}$c $Q_{_{ac}}$ ; $Q_{_{ac}}$ a $Q_{_{ac}}$ c $Q_{_{ac}}$ ; $Q_{_{ac}}$ c $Q_{_{ac}}$ a $Q_{_{ac}}$ ; $\varepsilon$

At this point my brain starts running in circles. Would this set me on the right path?


2 Answers 2


You're overcomplicating. There is no need for the grammar to be deterministic, so it's OK for cases to overlap.

Say $\omega \in \overline{L_1}$. At least one of the following statements must be true:

  • $\omega = a^ib^j\nu \text{ where } i \ge 1, j\ge 0 \text{ and } i \ne j, \text{ and } \nu \text{ does not start with } b$
  • $\omega = a^ib^jc^k \text{ where } i, j, k \ge 1, \text{ and }j \ne k$
    (I don't require $i = j$, although if $i \ne j$ then the first condition also applies.)
  • $\omega \text{ does not start with } a$
  • $\omega \text{ contains } ba, ca \text{ or }cb$

These all have reasonably simple grammars.

Just in case it's not obvious, there are a few ways to do $a^jb^k | j\ne k$. One simple one:

$$\begin{align} S &\to A \mid B \\ A &\to aC \mid aA \\ B &\to Cb \mid Bb \\ C &\to \epsilon \mid aCb \end{align} $$

$C$ is a balanced sequence of $a$ and $b$, $A$ has more $a$s, $B$ has more $b$s, and $S$ has either more $a$s or more $b$s.

  • $\begingroup$ are strings like $abcabc$ handled by the grammar which you showed above? I guess such strings should be there in the language. $\endgroup$ Oct 7, 2021 at 16:33
  • 1
    $\begingroup$ @AbhishekGhosh: The grammar I presented is not a grammar for the full language. It just shows how to write one part of the puzzle; I was assuming that OP could put the pieces together themselves. $\endgroup$
    – rici
    Oct 7, 2021 at 16:48
  • $\begingroup$ ok. Got it now. Thanks for the clarification. :) $\endgroup$ Oct 7, 2021 at 16:57

Informally let us first see the structure of the language.

$$L_2= \Sigma^* \text{\\} \{a^nb^nc^n | n \geq 1\}$$

This language has all strings which :

  1. starts with $b$.
  2. starts with $c$.
  3. starts with $a$ and have the form $a^i b^j c^k . (a+b+c)^*$ where $\lnot((i=j) \land (i=k) \land (j=k)) \equiv ((i\neq j) \lor (i\neq k) \lor (j\neq k))$. Now strings of this form can be represented as follows: $$(a^ib^jc^* + a^i b^* c^j + a^+b^ic^j). (a+b+c)^*, \text{where $(i\neq j)$}$$
  4. starts with $a$ and have the form (to handle strings such as $abcabc$ for instance): $$(a^+b^+c^+)((a^++b^+)^+c^*)(a+b+c)^*$$

Cases 1,2,4 are regular and case 3 is the one which requires stack. So we can easily create a PDA out of this. It shall be NPDA I guess, because on seeing we should work in parallel in two possible path ways, (3 and 4).

  • $\begingroup$ If I have missed any case or I have made some mistake in my analysis, please do rectify me. $\endgroup$ Oct 7, 2021 at 16:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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