Home | Contact Us

C-Sharp | Java | Python | Swift | GO | WPF | Ruby | Scala | F# | JavaScript | SQL | PHP | Angular | HTML

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

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 | ε


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


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 0104 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  

Thus 0104 is accepted by the PDA.

Example 3:

Draw a PDA for the CFG given below:

S → aSb
S → a | b | ε


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, ε)

Next TopicTuring Machine

Related Links:

Related Links

Adjectives Ado Ai Android Angular Antonyms Apache Articles Asp Autocad Automata Aws Azure Basic Binary Bitcoin Blockchain C Cassandra Change Coa Computer Control Cpp Create Creating C-Sharp Cyber Daa Data Dbms Deletion Devops Difference Discrete Es6 Ethical Examples Features Firebase Flutter Fs Git Go Hbase History Hive Hiveql How Html Idioms Insertion Installing Ios Java Joomla Js Kafka Kali Laravel Logical Machine Matlab Matrix Mongodb Mysql One Opencv Oracle Ordering Os Pandas Php Pig Pl Postgresql Powershell Prepositions Program Python React Ruby Scala Selecting Selenium Sentence Seo Sharepoint Software Spellings Spotting Spring Sql Sqlite Sqoop Svn Swift Synonyms Talend Testng Types Uml Unity Vbnet Verbal Webdriver What Wpf