Question

Convert the CFG given in Exercise 2.1 to an equivalent PDA, using the procedure given in Theorem 2.20

Short answer

The equivalent PDA is as follows:

Step-by-step solution

Explain Pushdown Automata

A pushdown automaton is the computational way that is used to implement the Context-free grammar. The pushdown automaton is capable of storing infinite information.

Convert the CFG given in Exercise 2.1 to an equivalent PDA,

Consider the CFG given in Exercise 2.1,

$$\begin{gathered} E\to E+T|T \\ T\to T\times F|F \\ F\to (E)|a \end{gathered}$$

Construct equivalent PDA for $G_4$as follows,

• Consider the empty stack to store the values.
• First, place the variable E and $ on the stack.
• Pop the stack top variable E and push E+ Tor T onto the stack. In either option T will be the top element of the stack.
• Pop the stack top variable T and push T X For onto the stack. In either option F will be the top element of the stack.
• Pop the stack top variable F and push (E) or onto the stack.
• If terminal symbol is pushed in the before step, read the next input and compare. If the input and terminal matches, repeat else reject this branch.

If the top element of the stack is $ , then enter the accept state

Therefore, The equivalent PDA has been constructed for the CFG .