0

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?

Galc127
  • 4,451

1 Answers1

2

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

Brian M. Scott
  • 616,228
  • The word '0' can be generated using these rules, but it is not in L... – Galc127 Dec 14 '16 at 11:04
  • @Galc127: Forgot about that condition. I’ve revised it very slightly so that at least one of each letter will be generated, I think without losing anything that we want. – Brian M. Scott Dec 14 '16 at 17:31