Table of contents
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 relationship between PDA and CFG?
5.5.
What is the equivalence of PDA and CFG?
6.
Conclusion
Last Updated: Jan 29, 2025
Easy

CFG to PDA Conversion

Author soham Medewar
1 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

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.

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

CFG to PDA Conversion

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 relationship between PDA and CFG?

A Pushdown Automaton (PDA) recognizes Context-Free Languages (CFLs), which are generated by Context-Free Grammars (CFGs), establishing a direct relationship between PDA and CFG.

What is the equivalence of PDA and CFG?

For every CFG, there exists an equivalent PDA that recognizes the same language, and vice versa, proving their theoretical equivalence in formal language theory.

Conclusion

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:

Live masterclass