Context Free Grammar for a 3-variable language

Question

I have to create a CFG for the following language:

$$\left\{ 0^i1^j2^k \mid i\ne j \space OR \space j\neq k \right\}$$

My idea is the following:

$$S→0S1S2S | AB |AC | BC | A | B | C$$ $$A→0A | 0$$ $$B→1B | 1$$ $$C→2C | 2$$

First I create a situation where all the letters are "equal" and also that there is at least $1$ instance of each letter. Then I have the conditions:

To create $j≠k→$

if j>k create AB
if k>j create AC

To create $i\ne j$

if i>j create AC
if i<j create BC

I can also create only "advantage" for $0/1/2$ if I go to $A$ $B$ or $C$ alone.

Is my idea correct?

Thanks,

Alan

Answer 1

Currently your grammar produces strings not in the language, e.g. 021021. I would suggest a different approach.

Hint:

• Split your language into 4 (partially overlapping) cases:
  1. $(i < j)$
  2. $(i > j)$
  3. $(j < k)$
  4. $(j > k)$
• The overlaps do not cause you any problems.
• For the first case $(i < j)$ it is enough to generate $0^i1^i11^x2^y$ for any $i, x, y$, other cases are similar.

I hope this helps $\ddot\smile$