Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Last Updated: Mar 27, 2024
Difficulty: Easy

CFG to PDA Conversion

Leveraging ChatGPT - GenAI as a Microsoft Data Expert
Speaker
Prerita Agarwal
Data Specialist @
23 Jul, 2024 @ 01:30 PM

Introduction

Before learning the technique of converting CFG to PDA, we will first understand the definition of CFG and PDA. CFG stands for Context-free Grammar, and PDA stands for Pushdown Automata.

CFG to PDA

Context-Free Grammar (CFG)

Context-free grammar (CFG) is a quadruple (N, T, P, S) made up of a finite collection of grammatical rules. Here N stands for the set of non-terminal symbols, T stands for the set of terminal symbols, P is a set of rules, and S is the start symbol. Also, N ∩ T should be NULL.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Pushdown Automata (PDA)

In a manner similar to how we create DFA for regular grammar, a pushdown automaton is a means to implement context-free grammar. A PDA can store unlimited amounts of information, but a DFA can only store a finite quantity.

We can also call PDA “Finite state machine” + “stack”.

PDA can be defined using a 7-tuple (Q, ∑, S, δ, q0, I, F)

  • Q : finite number of states
     
  • S : stack symbols
     
  • ∑ : input alphabet
     
  • δ : transition function (Q × (∑ ∪ {ε}) × S × Q × S*)
     
  • q0 : initial state (q0 ∈ Q)
     
  • I : initial stack top symbol (I ∈ S)
     
  • F : set of accepting states (F ∈ Q)

Also, the PDA has three components. They are as follows:

  • Input tape
     
  • Control unit
     
  • Stack with infinite size (it does two operations, PUSH and POP)

CFG to PDA Conversion

Steps

Conversion of CFG to PDA consists of five steps. The steps are as follows:

  • Convert the CFG productions into GNF.
  • There will only be one state, "q," on the PDA.
  • The CFG's first symbol will also be the PDA's initial symbol.
  • Include the following rule for non-terminal symbols:
    • δ(q, ε, A) = (q, α), Where the production rule is A → α
  • Add the following rule for each terminal symbol:
    • δ(q, a, a) = (q, ε) for every terminal symbol

Let us understand the above rules by an example.

 

Get detail information about Greibach Normal Form here.

 

Example 1

The following grammar should be converted to a PDA that supports the same language.

S → 0S1 | A  
A → 1A0 | S | ε  


Solution

Unit productions can be removed in order to first simplify the CFG:

S → 0S1 | 1S0 |  ε  


We shall now translate this CFG into GNF:

S → 0SX | 1SY |  ε  
X → 1  
Y → 0  


A PDA could be:

R1: δ(q, ε, S) = {(q, 0SX) | (q, 1SY) | (q, ε)}
R2: δ(q, ε, X) = {(q, 1)}
R3: δ(q, ε, Y) = {(q, 0)}
R4: δ(q, 0, 0) = {(q, ε)}
R5: δ(q, 1, 1) = {(q, ε)}

Example 2

Create a PDA for the provided CFG, and check if 0104 is supported by it.

S → 0BB  
B → 0S | 1S | 0  


Solution

You may present the PDA as:

A = {(q), (0, 1), (S, B, 0, 1), δ, q, S, ?}


The production rule δ can be:

R1: δ(q, ε, S) = {(q, 0BB)}
R2: δ(q, ε, B) = {(q, 0S) | (q, 1S) | (q, 0)}
R3: δ(q, 1, 1) = {(q, ε)}
R4: δ(q, 0, 0) = {(q, ε)}
Analyzing 0104, i.e., 010000, against a PDA
δ(q, 010000, S) ⊢ δ(q, 010000, 0BB)  
                ⊢ δ(q, 10000, BB)              R1  
                ⊢ δ(q, 10000,1SB)              R3    
                ⊢ δ(q, 0000, SB)               R2        
                ⊢ δ(q, 0000, 0BBB)             R1     
                ⊢ δ(q, 000, BBB)               R3        
                ⊢ δ(q, 000, 0BB)               R2      
                ⊢ δ(q, 00, BB)                 R3     
                ⊢ δ(q, 00, 0B)                 R2    
                ⊢ δ(q, 0, B)                   R3    
                ⊢ δ(q, 0, 0)                   R2  
                ⊢ δ(q, ε)                      R3    
                  ACCEPT


Thus, 0104 is accepted.

Also see, Turing Machine in TOC Arden's theorem

Frequently Asked Questions

What is automata CFG?

In order to produce every feasible pattern of strings in a given formal language, context-free grammar (CFG) is used. Four tuples are required to define it (V, T, P, S). Grammar is made up of a set of production rules, or G. It is used to create a language's strings.

Why do we use CFG?

CFGs are used to define computer languages, and context-free grammar can be used to automatically produce compiler parser programmes.

What are CFG and pushdown automata?

If a grammar G is context-free, we can construct a comparable nondeterministic PDA that will take the language that the context-free grammar G generates. The grammar G can have a parser constructed for it. Additionally, if P is a pushdown automaton, it is possible to create an analogous context-free grammar G where L(G) = L (P).

What is the PDA algorithm?

The Pushdown Automata is a finite automaton that has additional memory known as a stack that enables it to recognize context-free languages. An example of a pushdown automata (PDA) is Q; it is a collection of states. ∑  the collection of input symbols. Γ is a collection of pushdown symbols (which can be pushed and popped from the stack).

What are the different types of PDA?

There are two varieties of push-down automata as well: deterministic push-down automata (DPDA) and non-deterministic push-down automata, similar to DFA and non-deterministic finite automata (NFA) (NPDA). Context-free languages (CFL), indicated by LCF, are the languages that PDA can understand.

Conclusion

In this article, we have learned a simple technique to convert Context-free Grammar to Pushdown Automata. Also, we have solved examples that will help you understand the steps for converting CFG to PDA.

Recommended Readings:

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem DesignCompiler DesignAutomata Theory, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! Nevertheless, you may consider our paid courses to give your career an edge over others!

Happy Coding!

Topics covered
1.
Introduction
2.
Context-Free Grammar (CFG)
3.
Pushdown Automata (PDA)
4.
CFG to PDA Conversion
4.1.
Example 1
4.2.
Example 2
5.
Frequently Asked Questions
5.1.
What is automata CFG?
5.2.
Why do we use CFG?
5.3.
What are CFG and pushdown automata?
5.4.
What is the PDA algorithm?
5.5.
What are the different types of PDA?
6.
Conclusion