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*}$$

|cite|improve this question
$\endgroup$
  • 2
    $\begingroup$ That grammar obviously generates $\epsilon$, which is not in the language, and it generates $S\to aSbA\to abA\to abcA\to abc$, which is not in the language. I haven't thought about it carefully, but I think you are barking up the wrong tree, and the language is not context-free. $\endgroup$ – MJD Sep 27 '12 at 23:50
  • $\begingroup$ My reason for thinking that the language is not context-free is this: To test $i\ne j$, it has to count the as, which it can do on the stack, and then count backwards again as it sees the bs, which destroys the count that was on the stack. Then by the time it gets to the cs it has forgotten how many bs 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\}$. $\endgroup$ – MJD Sep 27 '12 at 23:56
3
$\begingroup$

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<j\}$; 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$.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Nice job, Brian, +1. $\endgroup$ – Rick Decker Sep 28 '12 at 0:09
  • $\begingroup$ So would something like S->Sc|aSb|Sb|b satisfy the i<j? $\endgroup$ – Takkun Sep 28 '12 at 0:32
  • 1
    $\begingroup$ @Takkun: You don’t want that: $S\Rightarrow aSb\Rightarrow aScb\Rightarrow abcb$. Don’t try to do everything at once. First generate $a^nb^n$, then generate at least one $b$, then generate an arbitrary number of $c$’s. $\endgroup$ – Brian M. Scott Sep 28 '12 at 0:35
  • $\begingroup$ S->Sc|A, A->aAb|B, B->bB|b? $\endgroup$ – Takkun Sep 28 '12 at 0:42
  • 1
    $\begingroup$ @Takkun: Yes, that should work. $\endgroup$ – Brian M. Scott Sep 28 '12 at 0: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.