2
$\begingroup$

$\{a^i b^j c^k \mid i\ne j\text{ or }j\ne k\}$

Is this language context free? I believe it is based on the following CFG but I would like some confirmation that I'm right.

$\begin{align*} &S\to aSbA \mid BbSc \mid\epsilon\\ &A\to cA \mid\epsilon\\ &B\to aB \mid\epsilon \end{align*}$

  • 0
    My reason for thinking that the language is not context-free is this: To test $i\ne j$, it has to count the `a`s, which it can do on the stack, and then count backwards again as it sees the `b`s, which destroys the count that was on the stack. Then by the time it gets to the `c`s it has forgotten how many `b`s there were, so it can't test $j\ne k$. This is of course not a proof, since there might be some other strategy for recognizing the language that *does* work, but I think it does suggest what approach to take: try the pumping lemma, as you would for $\{a^ib^ic^i\}$.2012-09-27

1 Answers 1

3

The grammar doesn’t generate the language. First, $\epsilon=a^0b^0c^0$, so $\epsilon$ is not in the language. It also generates an unwanted $abc$ via $S\Rightarrow aSbA\Rightarrow abA\Rightarrow abcA\Rightarrow abc$. In fact, your grammar generates words of the form $a^ib^jc^k$ such that $i=j$ or $j=k$.

The language is the union of $L_1=\{a^ib^jc^k:i\ne j\}$ and $L_2=\{a^ib^jc^k:j\ne k\}$, and context-free languages are closed under union, so it suffices to show that $L_1$ and $L_2$ are context-free. It’s not hard to design context-free grammars for $L_1$ and $L_2$. For $L_1$, for instance, start by designing a context-free grammar for $\{a^ib^jc^k:i; that’s pretty easy, and you can clearly do the same for $\{a^ib^jc^k:i>j\}$. Then just ‘paste’ them together properly to get a context-free grammar for $L_1$, and continue with $L_2$.

  • 1
    @Takkun: Yes, that should work.2012-09-28