Theory

A pushdown automaton (PDA) is a finite automaton with a stack for memory purposes. A nondeterministic pushdown automaton (NPDA) has one, or more than one, transition for each input that it reads. A context-free grammar (CFG) is the generator of a language, whereas a PDA and NPDA are the recognizers of a non-regular language. To convert a CFG to an NPDA, we follow these steps:

• Step 1: The stack is initially empty. Make the first transition as ε, ε → Γ. Before reading or popping the CFG, push the start variable on the stack.
• Step 2: Read nothing from the CFG in case of the start variable, pop it from the top of the stack, and push all the productions that the start variable produces. In the same step, read all the inputs of the CFG, pop, and push from the top of the stack according to the grammar rules mentioned in the CFG. This step transitions into a self-loop until all productions are read, popped, and pushed according to the CFG.
• Step 3: When there are no more productions to be read as input, pop the Γ symbol and push nothing. Make the last state the final state.
• Step 4: symbol and push nothing. Make the last When there are no more productions to be read as input, pop the Γ state the final state.