Context-free Grammar to Pushdown Automata
Each derivation or sequence of production rules that results in a given string is made up of intermediate strings (which are made at each step of the derivation).
The pushdown automata’s nondeterminism helps it to guess the sequence of steps in the derivation that will result in the desired string. So at each step in the derivation, one of the production rules for a given variable is selected nondeterministically and substituted in for the variable.
The pushdown automata begins by pushing a symbol onto the stack and then goes through the series of intermediate strings until it arrives at a string that contains only the terminal symbols (this will happen if the string is actually in the grammar, otherwise it will reject).
Read More: Definition of Pushdown Automata
Here’s what to do
- Push the start symbol, $, to the stack.
Then the following steps are repeated until the automaton finishes:
- If there is a variable X on top of the stack, nondeterministically pick one of the production rules for X and substitute X with the string on the right-hand side of the production rule.
- If there is a terminal variable a on the input, read the next symbol from the input and compare it to a . If they are the same, repeat and if they are not, reject on this branch of the nondeterminism.
- If it is the end of the input and the top of the stack has the start symbol, $, then accept
Can you come up with a diagram and formal description of a pushdown automaton that recognizes strings containing only parentheses and accepts on strings that have matched parentheses?
Σ = {(,)}
Γ = {$,Χ} note:, where the Χ could be any symbol you want
Q = { A, B, C, D }
F = {D}
q0 = A
Z = $
δ = {(A,ε, ε, A, $), (A,(,$,B,X), (B, (, X,B,X), (B,),X,C,ε) , (C,),X,C,ε), (C, ε, $, D, ε) }
[the_ad_group id=”24″]