Question

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

Short answer

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 G4given in Exercise 2.1 to an equivalent PDA,

Consider the CFG $G_4$given in Exercise 2.1,

Construct equivalent PDA for 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+ T or 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 F or F 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 $G_4$.