Confirm that this language is context free?

411 Views Asked by At

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

1

There are 1 best solutions below

5
On BEST ANSWER

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$.