Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

How to convert CFG to NPDA

Ayesha Kanwal

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Overview

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.

Components of an NPDA

A PDA is defined by six tuples <Q,,Γ,δ,q0,F><Q, \sum, Γ, δ, q_0, F> where:

  • QQ is the set of all the states
  • \sum is the language or the input alphabet
  • ΓΓ is the stack alphabet
  • δδ is the transition function andδ:Q×ϵ×ΓϵP(Q×Γϵ)δ : Q \times \sum_\epsilon \times Γ_\epsilon \rightarrow P(Q \times Γ_\epsilon)
  • q0q_0 is the start state and q0Qq_0 \in Q
  • FF is the final state and FQF \subseteq Q

Steps to convert CFG to NPDA

To convert a CFG to an NPDA, we follow these steps:

  1. The stack is initially empty. Make the first transition as ϵ,ϵΓ\epsilon , \epsilon \rightarrow Γ.
  2. Before reading or popping the CFG, push the start variable on the stack.
  3. 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.
  4. When there are no more productions to be read as input, pop the ΓΓsymbol and push nothing. Make the last state the final state.

Examples

The components of making a PDA are writing the steps that construct the PDA and the pushdown automaton itself.

Let's take an example of the following CFG:

Step 1: Push $\$ as the stack symbol

Input nothing from the CFG, pop nothing from the stack as it is already empty, and push $\$ as the stack symbol.

Stack view

%0 node_1 $ top_node top node_1->top_node
The stack after pushing $

NPDA view

g ENTRY q0 q0 ENTRY->q0 q1 q1 q0->q1 ε, ε -> $
The PDA after pushing $ to the stack

Step 2: Push SS

Push SS on top of the stack, as it is the start variable. Input and pop nothing from the CFG and the stack, respectively.

Stack view

%0 node_1 $ node_1657099394399 S top_node top node_1657099394399->top_node
Stack after pushing S.

NPDA view

g ENTRY q0 q0 ENTRY->q0 q1 q1 q0->q1 ε, ε -> $ q2 q2 q1->q2 ε, ε -> S
PDA after pushing S.

Step 3: Self-loop state

Read all possible inputs from the CFG, pop the same input from the stack, and push the productions they produce accordingly.

In the case of the start variable, as it is already on the top of the stack initially, pop it and push all the productions it creates.

Stack view

%0 node_1 $ node_1657100452182 ... top_node top node_1657100452182->top_node
Stack after reading, popping, and pushing the CFG productions.

NPDA view

g ENTRY q0 q0 ENTRY->q0 q1 q1 q0->q1 ε, ε -> $ q2 q2 q1->q2 ε, ε -> S q2->q2 ε, S -> aTb, ε, S -> b, ε, T -> aT, ε, T -> ε, a, a -> ε, b, b -> ε
The PDA after reading, popping, and pushing the CFG productions

Step 4: Pop $\$

After all the productions have been read, pushed, and popped, only the $\$ is present on the stack. Pop it and transition into the final state.

Stack view

%0 node_1 top_node top node_1->top_node
The stack after popping $

NPDA view

g ENTRY q0 q0 ENTRY->q0 q3 q3 q1 q1 q0->q1 ε, ε -> $ q2 q2 q1->q2 ε, ε -> S q2->q3 ε, $ -> ε q2->q2 ε, S -> aTb, ε, S -> b, ε, T -> aT, ε, T -> ε, a, a -> ε, b, b -> ε
The PDA after popping $

This is the final form of the NPDA formed by the CFG, where:

Note: To learn more about PDA, we can visit here.

RELATED TAGS

CONTRIBUTOR

Ayesha Kanwal
Copyright ©2022 Educative, Inc. All rights reserved

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Keep Exploring