I am trying to find context free grammar for the following language
$$L=\{0^i1^j2^k\mid i\ne j\vee j\ne k,\ i,j,k>0\}$$
I tried to write the following rules: \begin{align*}S&\to S_1C\mid S_2C\mid AS_3\mid AS_4 \\ S_1&\to 0A\mid 0S_11 \\ S_2&\to 1B\mid 0S_21 \\ S_3&\to 1B\mid 1S_32 \\ S_4&\to 2C\mid 1S_42 \\ A&\to 0A\mid \varepsilon \\ B&\to 1B\mid \varepsilon \\ C&\to 2C\mid \varepsilon \end{align*} but the solution does not satisfy the condition $i,j,k>0$. How should I change it?
Best Answer
It was easier to start from scratch, though I think that we’re following the same basic idea.
$$\begin{align*} S&\to S_{i<j}C\mid S_{i>j}C\mid AS_{j<k}\mid AS_{j>k}\\ S_{i<j}&\to XB\\ S_{i>j}&\to AX\\ S_{j<k}&\to YC\\ S_{j>k}&\to BY\\ X&\to 0X1\mid 01\\ Y&\to 1Y2\mid 12\\ A&\to 0A\mid 0\\ B&\to 1B\mid 1\\ C&\to 2C\mid 2\\ \end{align*}$$