Were w is any string composed over the alphabet $\Sigma = \{0,1\}$.

  1. For the first part of the exercise I've tried decomposing the problem into three different ones, mainly the first one is for the string before the 0 the second one for the 0 itself and the third for the rest of the string after the 0. This is what I came up with: $$ \begin{align} S &\rightarrow S_{1}S_{2}S_{3} \\ S_{1} &\rightarrow 0S_{1}|1S_{1}|\varepsilon \\ S_{2} &\rightarrow 0 \\ S_{3} &\rightarrow 0S_{3}|1S_{3}|\varepsilon \end{align} $$

But I'm not sure if the presence of the $\epsilon$ means that input strings such as $01$ or $10$ could be accepted, or if the $\epsilon$ at the end just ensure the recursion of the grammar.

  1. For the second part I have no idea about a possible solution.

Any help would be most appreciated. Thanks in advance

  • $\begingroup$ cs.stackexchange.com/q/18524/755 $\endgroup$
    – D.W.
    Jul 3 at 16:47
  • $\begingroup$ Please put your "answer" as part of your question. You can show what you did up to this point and where you got stuck but don't use the answer section for that purpose. $\endgroup$
    – Michel
    Jul 4 at 13:11
  • $\begingroup$ @Michel as it clearly shown I didn't use any space from the answer section. $\endgroup$
    – Lorenzo
    Jul 4 at 13:35

1 Answer 1


In your solution there is no guarantee that the words generated by $S_1$ and $S_2$ will have the same length. The trick is to generate both sides simultaneously: $$S \to 0S0 \mid0S1 \mid1S0 \mid1S1 \mid 0.$$

As for the second part, there are mechanical procedures to convert a CFG into a PDA.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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