Automata CFG to PDA Conversion

Automata CFG to PDA Conversion with automata tutorial, finite automata, dfa, nfa, regexp, transition diagram in automata, transition table, theory of automata, examples of dfa, minimization of dfa, non deterministic finite automata, etc.

<< Back to AUTOMATA

next → ← prev

CFG to PDA Conversion

The first symbol on R.H.S. production must be a terminal symbol. The following steps are used to obtain PDA from CFG is:

Step 1: Convert the given productions of CFG into GNF.

Step 2: The PDA will only have one state {q}.

Step 3: The initial symbol of CFG will be the initial symbol in the PDA.

Step 4: For non-terminal symbol, add the following rule:

δ(q, ε, A) = (q, α)

Where the production rule is A → α

Step 5: For each terminal symbols, add the following rule:

δ(q, a, a) = (q, ε) for every terminal symbol

Example 1:

Convert the following grammar to a PDA that accepts the same language.

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

Solution:

The CFG can be first simplified by eliminating unit productions:

S → 0S1 | 1S0 |  ε

Now we will convert this CFG to GNF:

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

The PDA can 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:

Construct PDA for the given CFG, and test whether 0104 is acceptable by this PDA.

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

Solution:

The PDA can be given 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, 0, 0) = {(q, ε)}
R4: δ(q, 1, 1) = {(q, ε)}

Testing 010⁴ i.e. 010000 against 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 010⁴ is accepted by the PDA.

Example 3:

Draw a PDA for the CFG given below:

S → aSb
S → a | b | ε

Solution:

The PDA can be given as:

P = {(q), (a, b), (S, a, b, z0), δ, q, z0, q}

The mapping function δ will be:

R1: δ(q, ε, S) = {(q, aSb)}
R2: δ(q, ε, S) = {(q, a) | (q, b) | (q, ε)}
R3: δ(q, a, a) = {(q, ε)}
R4: δ(q, b, b) = {(q, ε)}
R5: δ(q, ε, z0) = {(q, ε)}

Simulation: Consider the string aaabb

δ(q, εaaabb, S) ⊢ δ(q, aaabb, aSb)             R3
                ⊢ δ(q, εaabb, Sb)              R1                               
                ⊢ δ(q, aabb, aSbb)             R3
                ⊢ δ(q, εabb, Sbb)              R2
                ⊢ δ(q, abb, abb)               R3
                ⊢ δ(q, bb, bb)                 R4
                ⊢ δ(q, b, b)                   R4
                ⊢ δ(q, ε, z0)                  R5
                ⊢ δ(q, ε)
                ACCEPT

Next TopicTuring Machine

← prev next →

.Net

.NET Array Dictionary List String 2D Async DataTable Dates DateTime Enum File For Foreach Format IEnumerable If IndexOf Lambda LINQ Parse Path Process Property Regex Replace Sort Split Static StringBuilder Substring Switch Tuple

Java

Core Array ArrayList HashMap String 2D Cast Character Console Deque Duplicates File For Format HashSet If IndexOf Lambda Math ParseInt Process Random Regex Replace Sort Split StringBuilder Substring Switch Vector While

TheDeveloperBlog.com

Automata CFG to PDA Conversion

CFG to PDA Conversion

Example 1:

Example 2:

Example 3:

Related Links:

.Net

Java

Related Links