1
$\begingroup$

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

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

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$.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.