# Designing CFG that accepts # of 1's = # of 2's + # of 3's

Designing following language $\{ w \mid w\in\{0, 1\}^* \mbox{ such that } |w|_0 = |w|_1\}$ is easy.

Note $|w|_0$ means number of occurrences of 0.

$$S \to 0S1 \mid 1S0 \mid SS \mid \lambda$$

Then how about this? Language $\{ w \mid w\in\{1, 2, 3\}^* \mbox{ such that } |w|_1 = |w|_2 + |w|_3\}.$

It is somewhat difficult for me. Below is my solution. Is it correct?

$$S \to XSX \mid \lambda$$ $$X \to 1123 \mid 1132 \mid 1213 \mid 1231 \mid 1312 \mid 1321 \mid 2113 \mid 2131 \mid 2311 \mid 3112 \mid 3121 \mid 3211 \mid \lambda$$

• Your solution is incorrect. It cannot generate $111222222111$. May 19 '17 at 7:51
• @YuvalFilmus Thank you for your comment. What is the correct answer? Could you give me some hints? May 19 '17 at 7:53
• There is no single correct answer. Every context-free language can be generated by infinitely many context-free grammars. May 19 '17 at 7:55

## 1 Answer

Given a grammar for $\{ w \in \{0,1\}^* : |w|_0 = |w|_1 \}$, you can obtain a grammar for $\{ w \in \{1,2,3\}^* : |w|_2+|w|_3 = |w|_1 \}$ by replacing $0$ in the first grammar by a non-terminal $Z$, and adding the productions $Z\to 2 \mid 3$.