Converting a PushDown Automaton to a Context-Free Grammar

posted in Theoretical Computer Science on by

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

Rendered by QuickLaTeX.com

Modify the PDA

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

  1. The PDA must have a single final state.
  2. The PDA must accept a string with an empty stack.
  3. 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

Rendered by QuickLaTeX.com

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

Variables

The CFG will have variables of the type A_{pq} where p and q are states in the PDA. Thus, a PDA with n states will have n^2 variables. Here are the variables for the above PDA.

      \begin{align*} & A_{{q_0}{q_0}}, A_{{q_0}{q_1}}, A_{{q_0}{q_2}} \cdots A_{{q_0}{q_4}} \\ & A_{{q_1}{q_0}}, A_{{q_1}{q_1}}, A_{{q_1}{q_2}} \cdots A_{{q_1}{q_4}} \\ & \vdots \\ & A_{{q_4}{q_0}}, A_{{q_4}{q_1}}, A_{{q_4}{q_2}} \cdots A_{{q_4}{q_4}} \\ \end{align*}

The start variable will be A_{start final}. In this case – A_{q_0q_4}.

Rules

First add rules of the type A_{pp} \rightarrow \epsilon for all states p in the PDA. Thus, a PDA with n states will have n rules of this type. Here are those rules.

      \begin{align*} & A_{{q_0}{q_0}} \rightarrow \epsilon \\ & A_{{q_1}{q_1}} \rightarrow \epsilon \\ & \vdots \\ & A_{{q_4}{q_4}} \rightarrow \epsilon \\ \end{align*}

Next, add rules of the type A_{pq} \rightarrow A_{pr}A_{rq} for all states p, q and r in the PDA. Thus, a PDA with n states will have n^3 rules of this type. Here are those rules.

      \begin{align*} & A_{{q_0}{q_0}} \rightarrow A_{{q_0}{q_0}}A_{{q_0}{q_0}} \\ & A_{{q_0}{q_0}} \rightarrow A_{{q_0}{q_1}}A_{{q_1}{q_0}} \\ & \vdots \\ & A_{{q_0}{q_0}} \rightarrow A_{{q_0}{q_4}}A_{{q_4}{q_0}} \\ & A_{{q_0}{q_1}} \rightarrow A_{{q_0}{q_0}}A_{{q_0}{q_1}} \\ & A_{{q_0}{q_1}} \rightarrow A_{{q_0}{q_1}}A_{{q_1}{q_1}} \\ & \vdots \\ & A_{{q_0}{q_1}} \rightarrow A_{{q_0}{q_4}}A_{{q_4}{q_1}} \\ & \vdots \\ & A_{{q_4}{q_4}} \rightarrow A_{{q_4}{q_0}}A_{{q_0}{q_4}} \\ & A_{{q_4}{q_4}} \rightarrow A_{{q_4}{q_1}}A_{{q_1}{q_4}} \\ & \vdots \\ & A_{{q_4}{q_4}} \rightarrow A_{{q_4}{q_4}}A_{{q_4}{q_4}} \\ \end{align*}

Finally, add rules of the type A_{pq} \rightarrow a A_{rs} b where there is a transition from p to r on reading a and a transition from s to q on reading b. The number of rules of this type depends on the PDA. Here are those rules

      \begin{align*} & A_{{q_0}{q_4}} \rightarrow \epsilon A_{{q_1}{q_3}} \epsilon \\ & A_{{q_1}{q_3}} \rightarrow 0 A_{{q_1}{q_3}} 1\\ & A_{{q_1}{q_3}} \rightarrow \epsilon A_{{q_2}{q_2}} \epsilon \\ & A_{{q_1}{q_3}} \rightarrow 0 A_{{q_1}{q_2}} \epsilon \\ & A_{{q_1}{q_3}} \rightarrow \epsilon A_{{q_2}{q_3}} 1\\ \end{align*}

Leave a Reply

Your email address will not be published. Required fields are marked *