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 '12 at 20:55
  • $\begingroup$ Checking out this question might help. $\endgroup$ – Luke Mathieson Sep 22 '12 at 9:00

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, privacy policy and cookie policy