To construct a PDA from CFG, we only need to use these two simple rules:
- If the rule is of the form $S \rightarrow t$, where $t$ is a terminal, the transition is $t, t \rightarrow \epsilon$.
- If the rule is of the form $S \rightarrow s$, where $s$ is any string (including variables and terminals), $|s| >
1$, the transition is $\epsilon, S \rightarrow s$.
The first rule is simple and straightforward, but the second rule requires a little bit of work. Let says, we have a CFG defined as follows:
$$S \rightarrow aTXb$$
$$T \rightarrow XTS | \epsilon$$
$$X \rightarrow a | b$$
Initially, we have three states, where S stands for starting rule and \$ stands for stack symbol. Your book probably uses Z for stack symbol, so feel free to change it. It's just the matter of preference.
The restriction of a stack in PDA is that we can only push "one" symbol at a time. So to push a production rule onto a stack, we will break them into variables and terminals. Specifically, have a look at above picture, you can see that the first transition rule says push $S\$$ onto a stack, where $\$$ is stack symbol. This is not allowed in PDA, so we have to break the transition into two steps:
Note that this transition is a little special because it involves both stack variable $\$$ and the starting variable $S$. The next example of breaking long production rule should be more obvious. Firstly, all the production rule will go through the state after we pop $S$, i.e 2. We then apply the same procedure for any production rule that has length greater 1. So our first transition graph is as below:
In this graph, here are three transitions that need to be reconstructed. They are:
$$\epsilon, \epsilon \rightarrow S\$$$
$$\epsilon, S \rightarrow XTS$$
$$\epsilon, S \rightarrow aTXb$$
Since we've already done $\epsilon, \epsilon \rightarrow S$, the next transition need to reconstructed is $\epsilon, S \rightarrow aTXb$. Note that the order of popping is from "right to left". So we pop $S \rightarrow T \rightarrow X$ respectively as below:
Reconstruct the last transition rule $\epsilon, S \rightarrow aTXb$, we have our final PDA as follows:
Reference
- Introduction to the Theory of Computation by Micheal Sipser
- Lecture notes from prof. Marvin K. Nakayama, New Jersey Institute of Technology
One state, non-accepting, and no transitions. (That’s an NFA; if you want a DFA, have one transition from the state to itself for each letter of whatever alphabet is specified.)
Best Answer
We have shown (link in comment) that the language of this PDA is L = { a^n b (a* b)* a^n , n ≥ 0 } , now let's build the grammer ,
S --> aSa | bT
T --> AbT | ε
Α --> aA | ε
The first rule generates a^n b T a^n accounting for n = 0 , T generates (a* b)* , note how A generates a* , Ab is the same as a* b , and adding T , AbT allows for repeating ( you can form AbAbT , AbAbAbT and so on , or use T --> ε ) which is analogous to the *
As for your grammer , comparing it to the language you provided ( which is not the language for the PDA ) , it doesn't describe the language correctly , it doesn't also describe the correct language of the PDA
If we use the rules S --> aSa , then S --> B , we arrive at aBa , now use B --> ε ,and you get the string aa , which doesn't belong to the language you provided or that of the PDA ( note how the languages require at least one b to be in any string )