Convert the CFG G4 given in Exercise 2.1 to an equivalent

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

Theorem 2.20

A language is context free if and only if some pushdown automaton recognizes it.

Step By Step Solution

Step 1 of 2

Given, CFG ,

The formal details of the construction of the pushdown automaton . To make the construction clearer, we use shorthand notation for the transition function. This notation provides a way to write an entire string on the stack in one step of the machine. We can simulate this action by introducing additional states to write the string one symbol at a time.

The following is an informal description of P :

1. Place the marker symbol  and the start variable on the stack.
2. Repeat the following steps forever.

1. If the top of stack is a variable symbol, nondeterministically select one of the rules for the variable and substitute the variable by the string on the right-hand side of the rule.
2. If the top of stack is a terminal symbol, read the next symbol from the input and compare it to the symbol. If they match, repeat. If they do not match, reject this branch of nondeterminism.
3. If the top of stack is the symbol , enter the accept state. Doing so accepts the input if it has all been read.