patternMinor
Converting a context free grammar to a PDA -- is my solution correct?
Viewed 0 times
freepdagrammarcorrectcontextconvertingsolution
Problem
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.
$\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.
Solution
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.
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
If so, you just need a regular finite deterministic automaton with that can count up to three in order to recognize it.
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
Context
StackExchange Computer Science Q#4654, answer score: 8
Revisions (0)
No revisions yet.