Converting a PushDown Automaton (PDA) into an equivalent Context-Free Grammar (CFG) is quite involved. Consider the following PDA

## Modify the PDA

The first step is to modify this PDA to satisfy the following

- The PDA must have a single final state.
- The PDA must accept a string with an empty stack.
- Every transition of the PDA either pops or pushes but not both.

1 and 2 are already satisfied. To satisfy 3, the PDA is modified as follows

Now the PDA is ready to be converted to an equivalent CFG.

## Variables

The CFG will have variables of the type where and are states in the PDA. Thus, a PDA with states will have variables. Here are the variables for the above PDA.

The start variable will be . In this case – .

## Rules

First add rules of the type for all states in the PDA. Thus, a PDA with states will have rules of this type. Here are those rules.

Next, add rules of the type for all states , and in the PDA. Thus, a PDA with states will have rules of this type. Here are those rules.

Finally, add rules of the type where there is a transition from to on reading and a transition from to on reading . The number of rules of this type depends on the PDA. Here are those rules