# $L = \{ w \in \{0, 1, 2\}^*: |0| + |2| = |1| \}$ where |0| denotes number of 0s in the string w

I have come up with:

S→0SX | 1SY | 2SZ | SS | ϵ
X→1
Y→0 | 2
Z→1


I think I am wrong. Any directions?

• We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher.
– Raphael
Jul 12, 2017 at 21:34
• Why do you think you're wrong? Have you tried proving your grammar correct?
– Raphael
Jul 12, 2017 at 21:35
• I made this and I checked for some strings and they are all fine , but still I think if I am missing something. Jul 12, 2017 at 21:51
• First try to prove that any string $x \in L$ is derivable by your grammar. Then try to prove that if $x$ is derivable by your grammar then it is in $L$ (that is number of 1s is equal to the total number of 0s and 2s). If you prove both statements correctly then you are on the right track. Jul 12, 2017 at 21:59
• Also to simplify your work you may get rid off $X$, $Y$, and $Z$, leave only $S$, like $S \rightarrow 0S1 \ | \ 1S0 \ | \ 1S2 \ | \ 2S1 \ | \ SS \ | \epsilon$ Jul 12, 2017 at 22:08

1) Since the number of $1$s is equal to the sum of numbers of $0$s and $2$s, any string in $L$ is of even length.
2) Starting from $S$ any number of steps of a derivation without using $S \rightarrow SS \ | \ \epsilon$ results in a string $a_1a_2 \dots S \dots a_{n-1}a_n$ where number of $1$s is equal to the sum of $0$s and $2$s.
3) If $x = a_1a_2 \dots a_{n-1}a_n \in L$ ($|x|$ is even and number of $1$s in $x$ is equal to the total number of $0$s and $2$s) then $x$ has at least one of substrings $12, 21, 01$ or $10$ which is derived from $S \rightarrow 0S1 \ | \ 1S0 \ | \ 1S2 \ | \ 2S1$.