I'm reviewing for my midterm and wanted to post this to see if anyone can spot any errors. Im supposed to make a PDA that recognizes this CFG:

$\qquad\begin{align} S &\to R1R1R1 \\ R &\to 0R \mid 1R \mid \varepsilon \end{align}$

Here is my solution; I'm aware that I forgot to draw the second circle around my accepting state.

enter image description here

  • $\begingroup$ Your course probably mentions the (simple) standard translation algorithm. Have you tried to apply it? (Also, that image is hard to decipher.) Which one is supposed to be the final state? Finally, not that "check my answer" questions tend to work not so well on SE (in the case that the answer is a boring "yes, no mistakes". $\endgroup$
    – Raphael
    Sep 21, 2012 at 20:55
  • $\begingroup$ Checking out this question might help. $\endgroup$ Sep 22, 2012 at 9:00

1 Answer 1


Doesn't that language simply recognize any string in $\{0,1\}^*$ that has at least three $1$s in it?

If so, you just need a regular finite deterministic automaton with that can count up to three in order to recognize it.

finite automaton that counts to three

This is because I'm not on the mood to do a direct translation of that grammar, if that is what you really wanted to check :P


Your Answer

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