7
$\begingroup$

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

Improve this question
$\endgroup$
2
  • $\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
    Commented Sep 21, 2012 at 20:55
  • $\begingroup$ Checking out this question might help. $\endgroup$
    – Luke Mathieson
    Commented Sep 22, 2012 at 9:00

1 Answer 1

Reset to default
8
$\begingroup$

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

Improve this answer
$\endgroup$
0

Your Answer

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