Module 2

Context Free Grammars and Pushdown
Automata
Module 2
Dr. A K Yadav
Department of Computer Science & Engineering
Amity School of Engineering and Technology

Amity University Uttar Pradesh, Noida
December 21, 2022

Learning Objectives and Outcomes
Sub-topic Learning Objective Learning Outcomes

CFG: Formal To understand the basic idea To obtain basic understanding
Definition of Context Free Grammar of CFG
Derivation and To understand the concept of To become aware of hierarchy
Syntax trees derivation and syntax trees and syntax of trees
Simplification To understand the process and To become familiar with
Forms necessicity of simplification of simplified CFG
CFG
Ambiguous To understand how a grammar To understand impact of
Grammar can be ambiguous Ambiguous grammar
Properties of To understand properties of To understand properties of
CFL CFL CFL
Normal Forms To become familiar different To understand different normal
(CNF and GNF) normal forms of CFG forms of CFG and their relevance
Pushdown Auto- To undertand the concept of To undertand the concept of
mata: Definitions Pushdown Automata Pushdown Automata
Relationship bet- To understand the relation To understand the relation
ween PDA and CFL between PDA and CFG between PDA and CFG
Decision To understand the concept of To become familiar with
Algorithms Decision Algorithms Decision Trees
Dr. A K Yadav CFG and PDA December 21, 2022 2/63

Outline
1 CFG: Formal Definition
2 Derivation and Syntax Trees
3 Ambiguous Grammar
4 Simplification Forms
5 Properties of CFL
6 Normal Forms (CNF and GNF)
7 Pumping Lemma for Context Free Language
8 Decision Algorithms
9 Linear Grammar
10 Pushdown Automata
11 Relationship between PDA and CFL

CFG: Formal Definition
Context Free Grammar
Finite Automata accepts all regular languages.

Simple languages such as
an b n : n = 0, 1, 2, ....
w : w is a Palindrome
are not regular and thus no finite automata accepts them.
Context Free Languages are a larger class of languages that
encompasses all regular languages and many others including
above examples.
Languages generated by context free grammar are called
Context free languages.
Context free grammar are more expressive than finite
automata: If a language L is accepted by a finite automata,
then L can be generated by a context-free grammar, While
opposite is not true

Context-Free Grammars
A Context-free grammar is a 4-tuple (Vn , Σ, P, S)

Vn is set of Variables.
Σ is set of terminals.
P is set of Productions.
S is the start symbol.
A Grammar G is Context free, if every production is of the
form A → α, where A ∈ VN and α ∈ (VN ∪ Σ)∗

Example:CFG
Contruct a CFG generating all integers (with sign).

Example:CFG

Solution: Let G = (V , Σ, P, S)
where V = {S, < sign >, < digit >, < integer >}
Σ = {0, 1, 2, 3, .....9, +, −}
P consists of:
S →< sign >< integer >
< sign >→ +|−
< integer >→< digit >< integer > | < digit >
< digit >→ 0|1|2| . . . |9

Example:CFG

Solution: Let G = (V , Σ, P, S)
where V = {S, < sign >, < digit >, < integer >}
Σ = {0, 1, 2, 3, .....9, +, −}
P consists of:
S →< sign >< integer >
< sign >→ +|−
< integer >→< digit >< integer > | < digit >
< digit >→ 0|1|2| . . . |9
Derivation for -42
S→< sign >< integer >
=⇒ -< integer >
=⇒ -< digit >< integer >
=⇒ -4< digit >
=⇒ -42

Derivation and Syntax Trees
Derivation Trees
Trees are used for derivation of CFG.
Definition: A derivation tree (or a parse tree) for a CFG
G = (V , Σ, P, S) is a tree satisfying:
Every vertex has a label which is variable/terminal/∧.
The root has label S.
The label of the internal vertex is a variable.
If vertices n1 , n2 , .....nk written with labels X1 , X2 , ....Xk are sons of
vertex ’n’ with label A, then A → X1 X2 ...Xk is a production in P.
A vertex ’n’ is a leaf if its label is a ∈ Σ or ∧; ’n’ is the only son of
its father if its label is ∧
Let G = ({S,A},{a,b},P,S) where P consists of
S → aAS|a|SS, A → SbA|ba

Derivation Trees
Yield of Derivation Tree:is a

concatenation of labels of
the leaves without repetition
in the left to right ordering.
Example: aabaa Figure 1: Derivation Tree T
Subtree of a Derivation Tree

T is a tree:
whose root is some vertex
’v ’ of T ,
whose vertices are
descendants of ’v ’ together
with their labels. Figure 2: Sub tree of Tree T
whose edges are those
connecting the descendants
of v .
Figure 3: Sub tree of Tree T
Derivation Trees
Theorem 1:
∗
Let G=(V,Σ, P, S) be a CFG. Then, S =⇒ α if and only if there
is a derivation tree for G with yield α.
Example: Consider G whose productions are
∗
S → aAS|a, A → SbA|SS|ba. Show that S =⇒ aabbaa and Construct a
derivation tree whose yield is aabbaa.

Derivation Trees
Theorem 1:
∗
∗
Case 1:
S =⇒ aAS =⇒ aSbAS =⇒ aabAS =⇒ a2 bbaS =⇒ aabbaa

Derivation Trees
Theorem 1:
∗
∗
Case 1:
Case 2:
S =⇒ aAS =⇒ aAa =⇒ aSbAa =⇒ aSbbaa =⇒ aabbaa

Derivation Trees
Theorem 1:
∗
∗
Case 1:
Case 2:
S =⇒ aAS =⇒ aAa =⇒ aSbAa =⇒ aSbbaa =⇒ aabbaa
Case 3:
S =⇒ aAS =⇒ aSbAS =⇒ aSbAa =⇒ aabAa =⇒ aabbaa

Derivation Trees
∗
Left most derivation: A derivation A =⇒ w is called
left-most derivation, if we apply production only to the left
most variable at every step.
∗
Right most derivation: A derivation A =⇒ w is a right most
derivation, if we apply production to right most variable at
each step.
Theorem
∗
If A =⇒ w in G , then there is a left most derivation of w .

Derivation Trees
Example: Let G be the grammar S → 0B|1A, A → 0|0S|1AA, B → 1|1S|0BB.
For the string 00110101, find:
the leftmost derivation
the rightmost derivation
The derivation tree

Derivation Trees
The derivation tree
Leftmost derivation:
S =⇒ 0B =⇒ 00BB =⇒ 001B =⇒ 0011S =⇒ 02 12 0B =⇒
02 12 01S =⇒ 02 12 010B =⇒ 02 12 0101

Derivation Trees
The derivation tree
S =⇒ 0B =⇒ 00BB =⇒ 001B =⇒ 0011S =⇒ 02 12 0B =⇒
02 12 01S =⇒ 02 12 010B =⇒ 02 12 0101
Rightmost derivation:
S =⇒ 0B =⇒ 00BB =⇒ 00B1S =⇒ 00B10B =⇒ 02 B101S =⇒
02 B1010B =⇒ 02 B10101 =⇒ 02 110101

Derivation Trees
The derivation tree
S =⇒ 0B =⇒ 00BB =⇒ 001B =⇒ 0011S =⇒ 02 12 0B =⇒
02 12 01S =⇒ 02 12 010B =⇒ 02 12 0101
Rightmost derivation:
S =⇒ 0B =⇒ 00BB =⇒ 00B1S =⇒ 00B10B =⇒ 02 B101S =⇒
02 B1010B =⇒ 02 B10101 =⇒ 02 110101
Derivation tree:

Ambiguous Grammar
Ambiguity in CFG
In books selected information is given.

Ambiguous Grammar
Ambiguity in CFG
In books selected information is given.

A terminal string w ∈ L(G ) is ambiguous if there exist two or
more derivation trees for ’w ’ (or there exist two or more left
most derivation of w ).
G = ({S}, {a, b, +, ∗}, P, S), where P consists of
Example:
S → S + S|S ∗ S|a|b. We have two derivation trees for a+a*b:
S =⇒ S + S =⇒ a + S =⇒ a + S ∗ S =⇒ a + a ∗ S =⇒ a + a ∗ b
S =⇒ S ∗ S =⇒ S + S ∗ S =⇒ a + S ∗ S =⇒ a + a ∗ S =⇒ a + a ∗ b

Ambiguous Grammar
Ambiguity in CFG
Example:
If G is grammar S → SbS|a. Show that the given grammar is
ambigious.

Ambiguous Grammar
Ambiguity in CFG
Example:
ambigious.
For w = abababa

Ambiguous Grammar
Ambiguity in CFG
Example:
ambigious.
For w = abababa

Ambiguous Grammar
Ambiguity in CFG
Example:
ambigious.
For w = abababa
Thus, G is ambiguous.

Simplification Forms
Simplification of CFG
We eliminate following in order to simplify a grammar:

Useless variables
Unit productions
Null Productions

Eliminating Useless Variables
Those variables which are not deriving any terminal string and
which are not reachable are known as Useless Variables.
Example: S → AB
A → a|B
B → b|C
C → aC
D→b

Example: S → AB
A → a|B
B → b|C
C → aC
D→b
C is not deriving any terminal, C is not deriving any terminal
=⇒ useless variable, ∴ remove C

Example: S → AB
A → a|B
B → b|C
C → aC
D→b
S → AB, A → a|B, B → b, D → b
D is not included in S =⇒ remove D

Example: S → AB
A → a|B
B → b|C
C → aC
D→b
S → AB, A → a|B, B → b, D → b
D is not included in S =⇒ remove D
∴ S → AB, A → a|B, B → b

Eliminating Unit Productions
Production of the form A → B is known as Unit Production


Example: S → A, A → B, B → C , C → D, D → a
appears as chainlike process


Example: S → A, A → B, B → C , C → D, D → a
appears as chainlike process
Instead S → a will serve the purpose
∴ required grammar is S → a

Example:S → Aa|B, B → A|bb, A → a|bc|B


Starting from last to first
A → B is a unit production, replace B by its R.H.S.


A → a|bc|A|bb
B → a|bc|A|bb
S → Aa|a|bc|A|bb


A → a|bc|A|bb
B → a|bc|A|bb
S → Aa|a|bc|A|bb
Now, remove unit productions
A → a|bc|bb
B → a|bc|bb
S → Aa|bc|a|bb


A → a|bc|A|bb
B → a|bc|A|bb
S → Aa|a|bc|A|bb
Now, remove unit productions
A → a|bc|bb
B → a|bc|bb
S → Aa|bc|a|bb
Now, S does not has B, =⇒ remove B
S → Aa|bc|a|bb
A → a|bc|bb

Eliminating Null Productions
Any production of the form A → ϵ is called Null Production.

Example: S → aAb, A → aAb|ϵ

Eliminating Null Productions
Any production of the form A → ϵ is called Null Production.

Example: S → aAb, A → aAb|ϵ
Replace A with ϵ in each production containing A and add it
to grammar without ϵ
S → aAb|ab
A → aAb|ab

Simplifying CFG
Example: Construct reduced grammar equivalent to grammar

G whose productions are:
S → AB|CA, B → BC |AB, A → a, C → aB|b

Simplifying CFG

Here, B is not deriving any terminals ∴ remove B

Simplifying CFG

S → CA, A → a, C → b
∴ New Grammar G ′ = ({S, A, C }, {a, b}, P, S)

Simplifying CFG

S → CA, A → a, C → b
∴ New Grammar G ′ = ({S, A, C }, {a, b}, P, S)
Question: Find the reduced grammar equivalent to G .
S → aAa, A → bBB, B → ab, C → aB

Normal Forms (CNF and GNF)
Normal forms of CFG
Chomsky Normal Form

Greibach Normal Form

Chomsky Normal Form
A CFG is in Chomsky normal form if all productions are of the

form:
A → BC or A → a and S → ∧ if ∧ ∈ L(G )
where A,B,C are variables and a is a terminal. When ∧ is in L(G ),
we assume that S does not appear on the R.H.S. of any
production.

Chomsky Normal Form

form:
production.
Example: The Grammar in the form:
S → AS|a, A → SA|b

Chomsky Normal Form

form:
production.
Example: The Grammar in the form:
S → AS|a, A → SA|b
Reduction to Chomsky normal form
1 Elimination of null productions and unit productions
2 Elimination of terminals on R.H.S.
3 Restricting the number of variables on R.H.S.

Chomsky Normal Form
Example: Convert the grammar G with Productions as:

S → ABa, A → aab, B → Ac to chomsky normal form

Chomsky Normal Form

Let us assume few new variables:
X → a, Y → b, Z → c

Chomsky Normal Form

X → a, Y → b, Z → c
gives S → ABX , A → XXY , B → AZ

Chomsky Normal Form

X → a, Y → b, Z → c
Now, Assuming Q → XX , P → AB

Chomsky Normal Form

X → a, Y → b, Z → c
gives, S → PX , A → QY , B → AZ , X → a, Y → b, Z → c,
Q → XX , P → AB

Chomsky Normal Form

X → a, Y → b, Z → c
gives, S → PX , A → QY , B → AZ , X → a, Y → b, Z → c,
Q → XX , P → AB
Convert the given grammar to CNF
S → aSb |ab
S → aAB |Bb
A→a,B→b
S → bA |aB
A → bAA |aS |a
B → aBB |bS |b


A CFG is said to be in Greibach Normal form, if all the
productions have the form A → aX (or A → a when X is ∧),
where a ∈ Σ and X ∈ V ∗ (X may be ∧) and S → ∧ if
∧ ∈ L(G ) and S does not appear on the R.H.S. of any
production
Example: S → aAB|bBB|bB|a
A → aA|bB|b, B → b
Lemma 1:
Let G = (V , Σ, P, S) be a CFG. Let A → Bγ be an A-production
in P. Let the B-productions be B → β1 |β2 | . . . |βk . Define
P1 = (P − {A → Bγ}) ∪ {A → βi γ|1 ≤ i ≤ k}. Then
G1 = (V , Σ, P1 , S) is a context-free grammar equivalent to G.


Lemma 2:
Let G = (V , Σ, P, S) be a CFG. Let the set of A-productions be
A → Aα1 |Aα2 | . . . |Aαr |β1 |β2 | . . . |βs | (βi ’s do not start with A).
Let Z be a new variable. Let G1 = (V ∪ {Z }, Σ, P1 , S), where P1
is defined as follows:
1. The set of A-productions in P1 are
A → β1 |β2 | . . . |βs
A → β1 Z |β2 Z | . . . |βs Z
2. The set of Z -productions in P1 are
Z → α1 |α2 | . . . |αr
Z → α1 Z |α2 Z | . . . |αr Z
3. The productions for the other variables are as in P.
Then G1 is a CFG and equivalent to G .


Reduction to Greibach normal form
1 Elimination of null productions and unit productions
2 Elimination of terminals on R.H.S. except the first leftmost terminal.
3 Make all production starting with a terminal if not.
Example: Convert the grammar G into equivalent GNF:

S → abSb|aa
Solution: Let A → a, B → b
∴ S → aBSB|aA, A → a, B → b
Convert the grammar S → ab |aS |aaS into GNF
Solution: Let B → b, A → a, S → aB |aS |aAS
Exercise:
1 Convert the grammar S → AA|a, A → SS|b into GNF.
2 Convert the grammar S → AB, A → BS|b, B → SA|a into GNF.
3 Convert the grammar E → E + T |T , T → T ∗ F |F , F → (E )|a into
GNF.

Pumping Lemma for Context Free Language

Let L be an infinite context free language. Then, there exists some
positive integer n such that:
1 Every z ∈ L with |z| ≥ n can be written as uvwxy for some
strings u, v , w , x, y .
2 |vx| ≥ 1
3 |vwx ≤ n
4 uv k wx k y ∈ L for all k ≥ 0
Application: We use the pumping lemma to show that a language
L is not a context free language.
Procedure: We assume that L is context-free. By applying the
pumping lemma we get a contradiction. The procedure can be
carried out by using the following steps:
Step 1 Assume L is context-free. Let n be the natural number
obtained by using the pumping lemma.


Step 2 Choose z ∈ L so that |z| ≥ n. Write z = uvwxy using the
pumping lemma.
Step 3 Find a suitable k so that uv k wx k y ∈
/ L. This is a
contradiction, and so L is not context-free.


Ques: Show that the language
L={an b n c n : n ≥ 0} is not context free.


Solution: Let L be Context free
Let w be a string in L
For n=4, string becomes aaaabbbbcccc


By Pumping Lemma, w=uvxyz
w=aaaabbbbcccc


w=aaaabbbbcccc
Case 1: If vxy contain only a, b or c, then on pumping. It won’t be
in L
Case 2: If string contains any two either ab or bc, then pumped
string will contain ak b l c m with k ̸= l ̸= m or it will not be in the
order, so does not belong to L


w=aaaabbbbcccc
in L
∴ L is not context free.


w=aaaabbbbcccc
in L
∴ L is not context free.
Show that following L are not Context free
1 L={ww : w ∈ {a, b}∗}
2 L={an b j : n = j 2 }
3 L= {an! : n ≥ 0}

Ques: Show that L = {ap |p is a prime } is not a context-free
language


language
Solution:
1 Let L be Context free, Let w be a string in L


language
Solution:
2 Let n be the natural number obtained by using the pumping

lemma.


language
Solution:

lemma.
3 Let p be a prime number greater than n, Then z = ap ∈ L.
We can write z = uvwxy .


language
Solution:

lemma.
4 Prove for some k that uv k wx k y ∈
/ L means |uv k wx k y | is not
prime.


language
Solution:

lemma.
4 Prove for some k that uv k wx k y ∈
/ L means |uv k wx k y | is not
prime.
5 By pumping lemma, uv 0 wx 0 y = uwy ∈ L. So uxy | is a prime
number, say q.


language
Solution:

lemma.
4 Prove for some k that uv k wx k y ∈ / L means |uv k wx k y | is not
prime.
number, say q.
6 Let |vx| = r . Then, |uv q wx q y | = q + qr .


language
Solution:

lemma.
prime.
number, say q.
7 As q(1 + r ) is not a prime, means uv q wx q y ∈/ L.


language
Solution:

lemma.
prime.
number, say q.
7 As q(1 + r ) is not a prime, means uv q wx q y ∈/ L.

8 This is a contradiction. Therefore, L is not context-free.
Show that following L are not Context free

1 L={ww : w ∈ {a, b}∗ }
2 L={an b j : n = j 2 }
3 L= {an! : n ≥ 0}

Decision Algorithms
Decision Algorithms
Some decision algorithms for context-free languages and regular

sets.
1 Algorithm for deciding whether a context free language L is
empty.
2 Algorithm for deciding whether a context-free language L is
finite.
3 Algorithm for deciding whether a regular language L is empty.
4 Algorithm for deciding whether a regular language L is infinite.

Linear Grammar
Linear Grammar
A grammar in which atmost one variable can occur on right
side of any production without restriction on the size of this
grammar, is known as Linear Grammar.
Right Linear Grammar- A grammar G = (V .T , P, S) is said
to be right linear, if all the productions are of the form:
A → xB, A → x
where A, B ∈ V , x ∈ T ∗
Left Linear Grammar- A grammar is said to be left linear if all
the productions are of the form:
A → Bx, A → x
where A, B ∈ V , x ∈ T ∗
Linear Grammar- A grammar is said to be linear grammar if
all the productions are of the form:
A → vBw , A → w
where A, B ∈ V ; v , w ∈ T ∗
Linear Grammar
Linear Grammar
A regular grammar is always linear but not all linear grammars
are regular.
A regular grammar is one that is either right linear or left
linear
In a regular grammar, atmost one variable appears on right
side of any production. Further, that variable must
consistently be either on rightmost or leftmost symbol of right
side of any production.
Example: G1 = ({S}, {a, b}, P1 , S) where P1 given as
S → abS|a is right linear.
Example: G2 = ({S, S1 , S2 }, {a, b}, P2 , S) with productions
S → S1 ab, S1 → S1 ab, S1 → S2 , S2 → a is left linear

Linear Grammar
Linear Grammar
G = ({S, A, B}, {a, b}, P, S) with productions
S → A, A → aB|∧, B → Ab is not regular
∵ even if each production is right linear or left linear, but
grammar itself is neither right linear nor left linear ∴ not
regular

Linear Grammar
Linear Grammar
1 Construct a finite automata that accepts the language

generated by grammar
V0 → aV1 , V1 → abV0 |b
2 Construct a right linear grammar for L(aab ∗ a)
3 Convert the following regular expression into equivalent
regular grammar
(a + b)∗ a
a∗ +b+b ∗

Pushdown Automata
Pushdown Automata
Figure 4: Model of Pushdown Automata
A Non-deterministic Pushdown Automata is a 7-tuple

(Q, Σ, τ, δ, q0 , Z0 , F )
where , Q= finite non-empty set of states
Σ= finite non-empty set of input symbols
τ = finite non-empty set of pushdown symbols
q0 = initial state
Z0 = initial symbol on pushdown store
F = set of final states
δ =⇒ Q × (Σ ∪ {∧}) × τ → Q × τ ∗
Pushdown Automata
Pushdown Automata
δ =⇒ Q × (Σ ∪ {∧}) × τ → Q × τ ∗
Each move of the control unit is determined by the current
input symbol as well as by the symbol currently on the top of
the stack.
The result of the move is a new state of control unit and a
change in the top of the stack.
Instantaneous Description (ID) Let A = (Q, Σ, τ, δ, q0 , Z0 , F ) be
a pda. An instantaneous description (ID) is (q, w , α), where
q ∈ Q, w ∈ Σ∗ and α ∈ τ ∗ .
An initial ID is (q o, w , Z0 ). This means that initially the pda
is in the initial state q0 , the input string to be processed is w
and the PDS has only one symbol, namely Z0 .
In an ID (q, ∧, Z ), In this case the pda makes a ∧-move.

Pushdown Automata
Pushdown Automata
A move relation, denoted by ⊢ between IDs is defined as
(q, a1 a2 . . . an , Z1 Z2 . . . Zm ) ⊢ (q ′ , a2 . . . an , βZ2 . . . Zm )
if δ(q, a1 , Z1 ) = (q ′ , β)
if (q1 , x, α) ⊢∗ (q2 , ∧, β) then for every y ∈ Σ∗ ,
(q1 , xy , α) ⊢∗ (q2 , y , β)
Conversely, if (q1 , xy , α) ⊢∗ (q2 , y , β) for some y ∈ Σ∗ , then
(q1 , x, α) ⊢∗ (q2 , ∧, β)
if (q1 , x, α) ⊢∗ (q2 , ∧, β) then for every γ ∈ τ ∗ ,
(q1 , x, αγ) ⊢∗ (q2 , ∧, βγ)

Pushdown Automata
NPDA: Example
Consider a NPDA as under:

Q = {q0 , q1 , q2 , q3 }, Σ = {a, b}
τ = {a, Z0 }, Z0 , F = {q3 } and
δ(q0 , a, Z0 ) = (q0 , aZ0 )
δ(q0 , a, a) = (q0 , aa)
δ(q0 , b, a) = (q1 , ∧)
δ(q1 , b, a) = (q1 , ∧)
δ(q1 , ∧, Z0 ) = (qf , Z0 )
What can we say about the action of this automaton?

Pushdown Automata
Language accepted by a PDA

Acceptance of input strings by pda is of two way:
1 Acceptance by Final State
2 Acceptance by Null Store
Let M =(Q, Σ, τ, δ, q0 , Z0 , F ) be a non-deterministic push-down
automata. The language accepted by M is the set
L(M) = {w ∈ Σ∗ |(q0 , w , Z0 )⊢∗M (q ′ , Λ, α)}
where q ′ ∈ F and α ∈ τ ∗
Example: Construct a NPDA for the language
L = {w ∈ {a, b}∗ |na (w ) = nb (w )}
Solution: Q = {q0 , qf }, Σ = {a, b}, τ = {a, b, Z }, F = {qf }
Let M= {Q, Σ, τ, δ, q0 , Z , F }
δ(q0 , a, Z ) = (q0 , aZ )
δ(q0 , b, Z ) = (q0 , bZ )
δ(q0 , a, a) = (q0 , aa)

Pushdown Automata

δ(q0 , b, b) = (q0 , bb)
δ(q0 , a, b) = (q0 , Λ)
δ(q0 , b, a) = (q0 , Λ)
δ(q0 , Λ, Z ) = (qf , Z )
Let us assume w = baab to process
(q0 , baab, Z ) ⊢
(q0 , aab, bZ ) ⊢
(q0 , ab, Z ) ⊢
(q0 , b, aZ ) ⊢
(q0 , Λ, Z ) ⊢
(qf , Λ, Z )

Pushdown Automata
Language accepted by PDA
Let A =(Q, Σ, τ, δ, q0 , Z0 , F ) be a non-deterministic push-down

automata. The language accepted by null store or empty store A is
the set N(A) = {w ∈ Σ∗ |(q0 , w , Z0 )⊢∗A (q, Λ, Λ)}
where q ∈ Q
Theorem
If A = (Q, Σ, τ, δ, q0 , Z0 , F ) is a pda accepting L by empty store.
we can find a pda B = (Q ′ , Σ, τ ′ , δ ′ , q0′ , Z0 , F ′ ) accepting L by final
state: i.e. L = N(A) = T (B).
Theorem
If A = (Q, Σ, τ, δ, q0 , Z0 , F ) accepts L by final state, we can find a
pda B accepting L by empty store: i.e. L = T (A) = N(B).

Pushdown Automata

Question: Construct a NPDA for accepting the language
L={ww R : w ∈ {a, b}+ }

Pushdown Automata

L={ww R : w ∈ {a, b}+ }
Solution: M=(Q,Σ, τ , δ, q0 , z, F)
where Q= {q0 , q1 , q2 }, Σ={a,b}
τ = {a,b,z}, F={q2 }

Pushdown Automata

L={ww R : w ∈ {a, b}+ }
where Q= {q0 , q1 , q2 }, Σ={a,b}
τ = {a,b,z}, F={q2 }
δ(q0 , a, a) = (q0 , aa),

Pushdown Automata

L={ww R : w ∈ {a, b}+ }
where Q= {q0 , q1 , q2 }, Σ={a,b}
τ = {a,b,z}, F={q2 }
δ(q0 , a, a) = (q0 , aa), δ(q0 , b, a) = (q0 , ba)

Pushdown Automata

L={ww R : w ∈ {a, b}+ }
where Q= {q0 , q1 , q2 }, Σ={a,b}
τ = {a,b,z}, F={q2 }
δ(q0 , a, a) = (q0 , aa), δ(q0 , b, a) = (q0 , ba)
δ(q0 , a, b) = (q0 , ab),

Pushdown Automata

L={ww R : w ∈ {a, b}+ }
where Q= {q0 , q1 , q2 }, Σ={a,b}
τ = {a,b,z}, F={q2 }
δ(q0 , a, a) = (q0 , aa), δ(q0 , b, a) = (q0 , ba)
δ(q0 , a, b) = (q0 , ab), δ(q0 , b, b) = (q0 , bb)

Pushdown Automata

L={ww R : w ∈ {a, b}+ }
where Q= {q0 , q1 , q2 }, Σ={a,b}
τ = {a,b,z}, F={q2 }
δ(q0 , a, a) = (q0 , aa), δ(q0 , b, a) = (q0 , ba)
δ(q0 , a, b) = (q0 , ab), δ(q0 , b, b) = (q0 , bb)
δ(q0 , a, z) = (q0 , az),

Pushdown Automata

L={ww R : w ∈ {a, b}+ }
where Q= {q0 , q1 , q2 }, Σ={a,b}
τ = {a,b,z}, F={q2 }
δ(q0 , a, a) = (q0 , aa), δ(q0 , b, a) = (q0 , ba)
δ(q0 , a, b) = (q0 , ab), δ(q0 , b, b) = (q0 , bb)
δ(q0 , a, z) = (q0 , az), δ(q0 , b, z) = (q0 , bz)

Pushdown Automata

L={ww R : w ∈ {a, b}+ }
where Q= {q0 , q1 , q2 }, Σ={a,b}
τ = {a,b,z}, F={q2 }
δ(q0 , a, a) = (q0 , aa), δ(q0 , b, a) = (q0 , ba)
δ(q0 , a, b) = (q0 , ab), δ(q0 , b, b) = (q0 , bb)
δ(q0 , a, z) = (q0 , az), δ(q0 , b, z) = (q0 , bz)
For middle:

Pushdown Automata

L={ww R : w ∈ {a, b}+ }
where Q= {q0 , q1 , q2 }, Σ={a,b}
τ = {a,b,z}, F={q2 }
δ(q0 , a, a) = (q0 , aa), δ(q0 , b, a) = (q0 , ba)
δ(q0 , a, b) = (q0 , ab), δ(q0 , b, b) = (q0 , bb)
δ(q0 , a, z) = (q0 , az), δ(q0 , b, z) = (q0 , bz)
For middle:
δ(q0 , Λ, a) = (q1 , a),

Pushdown Automata

L={ww R : w ∈ {a, b}+ }
where Q= {q0 , q1 , q2 }, Σ={a,b}
τ = {a,b,z}, F={q2 }
δ(q0 , a, a) = (q0 , aa), δ(q0 , b, a) = (q0 , ba)
δ(q0 , a, b) = (q0 , ab), δ(q0 , b, b) = (q0 , bb)
δ(q0 , a, z) = (q0 , az), δ(q0 , b, z) = (q0 , bz)
For middle:
δ(q0 , Λ, a) = (q1 , a), δ(q0 , Λ, b) = (q1 , b)

Pushdown Automata

L={ww R : w ∈ {a, b}+ }
where Q= {q0 , q1 , q2 }, Σ={a,b}
τ = {a,b,z}, F={q2 }
δ(q0 , a, a) = (q0 , aa), δ(q0 , b, a) = (q0 , ba)
δ(q0 , a, b) = (q0 , ab), δ(q0 , b, b) = (q0 , bb)
δ(q0 , a, z) = (q0 , az), δ(q0 , b, z) = (q0 , bz)
For middle:
δ(q0 , Λ, a) = (q1 , a), δ(q0 , Λ, b) = (q1 , b)
For matching w R against contents of stack

Pushdown Automata

L={ww R : w ∈ {a, b}+ }
where Q= {q0 , q1 , q2 }, Σ={a,b}
τ = {a,b,z}, F={q2 }
δ(q0 , a, a) = (q0 , aa), δ(q0 , b, a) = (q0 , ba)
δ(q0 , a, b) = (q0 , ab), δ(q0 , b, b) = (q0 , bb)
δ(q0 , a, z) = (q0 , az), δ(q0 , b, z) = (q0 , bz)
For middle:
δ(q0 , Λ, a) = (q1 , a), δ(q0 , Λ, b) = (q1 , b)
δ(q1 , a, a) = (q1 , Λ) ,

Pushdown Automata

L={ww R : w ∈ {a, b}+ }
where Q= {q0 , q1 , q2 }, Σ={a,b}
τ = {a,b,z}, F={q2 }
δ(q0 , a, a) = (q0 , aa), δ(q0 , b, a) = (q0 , ba)
δ(q0 , a, b) = (q0 , ab), δ(q0 , b, b) = (q0 , bb)
δ(q0 , a, z) = (q0 , az), δ(q0 , b, z) = (q0 , bz)
For middle:
δ(q0 , Λ, a) = (q1 , a), δ(q0 , Λ, b) = (q1 , b)
δ(q1 , a, a) = (q1 , Λ) , δ(q1 , b, b) = (q1 , Λ)

Pushdown Automata

L={ww R : w ∈ {a, b}+ }
where Q= {q0 , q1 , q2 }, Σ={a,b}
τ = {a,b,z}, F={q2 }
δ(q0 , a, a) = (q0 , aa), δ(q0 , b, a) = (q0 , ba)
δ(q0 , a, b) = (q0 , ab), δ(q0 , b, b) = (q0 , bb)
δ(q0 , a, z) = (q0 , az), δ(q0 , b, z) = (q0 , bz)
For middle:
δ(q0 , Λ, a) = (q1 , a), δ(q0 , Λ, b) = (q1 , b)
δ(q1 , a, a) = (q1 , Λ) , δ(q1 , b, b) = (q1 , Λ)
Finally, δ(q1 , Λ, z) = (q2 , z)

Pushdown Automata

L={ww R : w ∈ {a, b}+ }
where Q= {q0 , q1 , q2 }, Σ={a,b}
τ = {a,b,z}, F={q2 }
δ(q0 , a, a) = (q0 , aa), δ(q0 , b, a) = (q0 , ba)
δ(q0 , a, b) = (q0 , ab), δ(q0 , b, b) = (q0 , bb)
δ(q0 , a, z) = (q0 , az), δ(q0 , b, z) = (q0 , bz)
For middle:
δ(q0 , Λ, a) = (q1 , a), δ(q0 , Λ, b) = (q1 , b)
δ(q1 , a, a) = (q1 , Λ) , δ(q1 , b, b) = (q1 , Λ)
Let the String assumed be ’abba’:
(q0 , abba, z)

Pushdown Automata

L={ww R : w ∈ {a, b}+ }
where Q= {q0 , q1 , q2 }, Σ={a,b}
τ = {a,b,z}, F={q2 }
δ(q0 , a, a) = (q0 , aa), δ(q0 , b, a) = (q0 , ba)
δ(q0 , a, b) = (q0 , ab), δ(q0 , b, b) = (q0 , bb)
δ(q0 , a, z) = (q0 , az), δ(q0 , b, z) = (q0 , bz)
For middle:
δ(q0 , Λ, a) = (q1 , a), δ(q0 , Λ, b) = (q1 , b)
δ(q1 , a, a) = (q1 , Λ) , δ(q1 , b, b) = (q1 , Λ)
(q0 , abba, z) ⊢ (q0 , bba, az)

Pushdown Automata

L={ww R : w ∈ {a, b}+ }
where Q= {q0 , q1 , q2 }, Σ={a,b}
τ = {a,b,z}, F={q2 }
δ(q0 , a, a) = (q0 , aa), δ(q0 , b, a) = (q0 , ba)
δ(q0 , a, b) = (q0 , ab), δ(q0 , b, b) = (q0 , bb)
δ(q0 , a, z) = (q0 , az), δ(q0 , b, z) = (q0 , bz)
For middle:
δ(q0 , Λ, a) = (q1 , a), δ(q0 , Λ, b) = (q1 , b)
δ(q1 , a, a) = (q1 , Λ) , δ(q1 , b, b) = (q1 , Λ)
(q0 , abba, z) ⊢ (q0 , bba, az) ⊢ (q0 , ba, baz)

Pushdown Automata

L={ww R : w ∈ {a, b}+ }
where Q= {q0 , q1 , q2 }, Σ={a,b}
τ = {a,b,z}, F={q2 }
δ(q0 , a, a) = (q0 , aa), δ(q0 , b, a) = (q0 , ba)
δ(q0 , a, b) = (q0 , ab), δ(q0 , b, b) = (q0 , bb)
δ(q0 , a, z) = (q0 , az), δ(q0 , b, z) = (q0 , bz)
For middle:
δ(q0 , Λ, a) = (q1 , a), δ(q0 , Λ, b) = (q1 , b)
δ(q1 , a, a) = (q1 , Λ) , δ(q1 , b, b) = (q1 , Λ)
(q0 , abba, z) ⊢ (q0 , bba, az) ⊢ (q0 , ba, baz) ⊢ (q1 , ba, baz)

Pushdown Automata

L={ww R : w ∈ {a, b}+ }
where Q= {q0 , q1 , q2 }, Σ={a,b}
τ = {a,b,z}, F={q2 }
δ(q0 , a, a) = (q0 , aa), δ(q0 , b, a) = (q0 , ba)
δ(q0 , a, b) = (q0 , ab), δ(q0 , b, b) = (q0 , bb)
δ(q0 , a, z) = (q0 , az), δ(q0 , b, z) = (q0 , bz)
For middle:
δ(q0 , Λ, a) = (q1 , a), δ(q0 , Λ, b) = (q1 , b)
δ(q1 , a, a) = (q1 , Λ) , δ(q1 , b, b) = (q1 , Λ)
⊢ (q1 , a, az)
Pushdown Automata

L={ww R : w ∈ {a, b}+ }
where Q= {q0 , q1 , q2 }, Σ={a,b}
τ = {a,b,z}, F={q2 }
δ(q0 , a, a) = (q0 , aa), δ(q0 , b, a) = (q0 , ba)
δ(q0 , a, b) = (q0 , ab), δ(q0 , b, b) = (q0 , bb)
δ(q0 , a, z) = (q0 , az), δ(q0 , b, z) = (q0 , bz)
For middle:
δ(q0 , Λ, a) = (q1 , a), δ(q0 , Λ, b) = (q1 , b)
δ(q1 , a, a) = (q1 , Λ) , δ(q1 , b, b) = (q1 , Λ)
⊢ (q1 , a, az) ⊢ (q1 , Λ, z)
Pushdown Automata

L={ww R : w ∈ {a, b}+ }
where Q= {q0 , q1 , q2 }, Σ={a,b}
τ = {a,b,z}, F={q2 }
δ(q0 , a, a) = (q0 , aa), δ(q0 , b, a) = (q0 , ba)
δ(q0 , a, b) = (q0 , ab), δ(q0 , b, b) = (q0 , bb)
δ(q0 , a, z) = (q0 , az), δ(q0 , b, z) = (q0 , bz)
For middle:
δ(q0 , Λ, a) = (q1 , a), δ(q0 , Λ, b) = (q1 , b)
δ(q1 , a, a) = (q1 , Λ) , δ(q1 , b, b) = (q1 , Λ)
⊢ (q1 , a, az) ⊢ (q1 , Λ, z) ⊢ (q2 , z)
Pushdown Automata
1 Construct a NPDA that accepts the language

L={an b m : n≥0, n̸=m}
2 Find NPDA on Σ={a,b,c} that accepts the language
L={w1 cw2 : w1 , w2 ∈ {a, b}∗ , w1 ̸= w2 R }

Relationship between PDA and CFL
CFG to PDA
Theorem
If L is a context-free language, then we can construct a pda A
accepting L by empty store, i.e. L = N(A).
Construction of pda A Let L = L(G ), where G = (V , Σ, P, S) is a

context-free grammar. We construct a pda A as
A = ({q}, Σ, V ∪ Σ, δ, q, S, ϕ), where δ is defined by the following
rules:
R1 For every A → α in P, δ(q, ∧, A) = {(q, α)}
R2 For every a in Σ, δ(q, a, a) = {(q, ∧)}

CFG to PDA
Construct a PDA that accepts the language generated by the
grammar with productions
S → aSA|a, A → bB, B → b
Solution: Step-1 The given productions are:
S → aSA|a
A → bB
B→b
δ is defined by the following rules:
S-productions
δ(q, ∧, S) = {(q, aSA), (q, a)}
A-productions
δ(q, ∧, A) = {(q, bB)}
B-productions
δ(q, ∧, B) = {(q, b)}
Productions for Σ

CFG to PDA
δ(q, a, a) = {(q, ∧)}
δ(q, b, b) = {(q, ∧)}
Appearance of Λ on top of stack implies completion of
derivation and PDA is put to final state by
δ(q, Λ, Z ) = (qf , Λ)

CFG to PDA
Question: Consider the grammar
S → aA, A →aABC |bB |a, B →b, C →c

CFG to PDA
Solution: Putting Start Symbol on stack
δ(q0 , Λ, Z ) = (q1 , SZ )

CFG to PDA
δ(q0 , Λ, Z ) = (q1 , SZ )
Final Production: δ(q1 , Λ, Z ) = (qf , Z )

CFG to PDA
δ(q0 , Λ, Z ) = (q1 , SZ )
Now, according to the productions

CFG to PDA
δ(q0 , Λ, Z ) = (q1 , SZ )
δ(q1 , a, S) = (q1 , A),

CFG to PDA
δ(q0 , Λ, Z ) = (q1 , SZ )
δ(q1 , a, S) = (q1 , A), δ(q1 , a, A) = (q1 , ABC ),

CFG to PDA
δ(q0 , Λ, Z ) = (q1 , SZ )
δ(q1 , a, S) = (q1 , A), δ(q1 , a, A) = (q1 , ABC ),
δ(q1 , b, A) = (q1 , B),

CFG to PDA
δ(q0 , Λ, Z ) = (q1 , SZ )
δ(q1 , a, S) = (q1 , A), δ(q1 , a, A) = (q1 , ABC ),
δ(q1 , b, A) = (q1 , B), δ(q1 , a, A) = (q1 , Λ),

CFG to PDA
δ(q0 , Λ, Z ) = (q1 , SZ )
δ(q1 , a, S) = (q1 , A), δ(q1 , a, A) = (q1 , ABC ),
δ(q1 , b, A) = (q1 , B), δ(q1 , a, A) = (q1 , Λ), δ(q1 , b, B) = (q1 , Λ),

CFG to PDA
δ(q0 , Λ, Z ) = (q1 , SZ )
δ(q1 , a, S) = (q1 , A), δ(q1 , a, A) = (q1 , ABC ),
δ(q1 , c, C ) = (q1 , Λ)

CFG to PDA
δ(q0 , Λ, Z ) = (q1 , SZ )
δ(q1 , a, S) = (q1 , A), δ(q1 , a, A) = (q1 , ABC ),
δ(q1 , c, C ) = (q1 , Λ)
Let the derivation be
S → aA → aaABC → aaaBC → aaabC → aaabc

CFG to PDA
δ(q0 , Λ, Z ) = (q1 , SZ )
δ(q1 , a, S) = (q1 , A), δ(q1 , a, A) = (q1 , ABC ),
δ(q1 , c, C ) = (q1 , Λ)
Therefore, the sequence of moves by M for the processing of
”aaabc” is:

CFG to PDA
δ(q0 , Λ, Z ) = (q1 , SZ )
δ(q1 , a, S) = (q1 , A), δ(q1 , a, A) = (q1 , ABC ),
δ(q1 , c, C ) = (q1 , Λ)
”aaabc” is:
(q0 , aaabc, Z )

CFG to PDA
δ(q0 , Λ, Z ) = (q1 , SZ )
δ(q1 , a, S) = (q1 , A), δ(q1 , a, A) = (q1 , ABC ),
δ(q1 , c, C ) = (q1 , Λ)
”aaabc” is:
(q0 , aaabc, Z ) ⊢ (q1 , aaabc, SZ )

CFG to PDA
δ(q0 , Λ, Z ) = (q1 , SZ )
δ(q1 , a, S) = (q1 , A), δ(q1 , a, A) = (q1 , ABC ),
δ(q1 , c, C ) = (q1 , Λ)
”aaabc” is:
(q0 , aaabc, Z ) ⊢ (q1 , aaabc, SZ ) ⊢ (q1 , aabc, AZ )

CFG to PDA
δ(q0 , Λ, Z ) = (q1 , SZ )
δ(q1 , a, S) = (q1 , A), δ(q1 , a, A) = (q1 , ABC ),
δ(q1 , c, C ) = (q1 , Λ)
”aaabc” is:
⊢ (q1 , abc, ABCZ )

CFG to PDA
δ(q0 , Λ, Z ) = (q1 , SZ )
δ(q1 , a, S) = (q1 , A), δ(q1 , a, A) = (q1 , ABC ),
δ(q1 , c, C ) = (q1 , Λ)
”aaabc” is:
⊢ (q1 , abc, ABCZ ) ⊢ (q1 , bc, BCZ )

CFG to PDA
δ(q0 , Λ, Z ) = (q1 , SZ )
δ(q1 , a, S) = (q1 , A), δ(q1 , a, A) = (q1 , ABC ),
δ(q1 , c, C ) = (q1 , Λ)
”aaabc” is:
⊢ (q1 , abc, ABCZ ) ⊢ (q1 , bc, BCZ ) ⊢ (q1 , c, CZ )

CFG to PDA
δ(q0 , Λ, Z ) = (q1 , SZ )
δ(q1 , a, S) = (q1 , A), δ(q1 , a, A) = (q1 , ABC ),
δ(q1 , c, C ) = (q1 , Λ)
”aaabc” is:
⊢ (q1 , abc, ABCZ ) ⊢ (q1 , bc, BCZ ) ⊢ (q1 , c, CZ ) ⊢ (q1 , Λ, Z )

CFG to PDA
δ(q0 , Λ, Z ) = (q1 , SZ )
δ(q1 , a, S) = (q1 , A), δ(q1 , a, A) = (q1 , ABC ),
δ(q1 , c, C ) = (q1 , Λ)
”aaabc” is:
⊢ (q1 , abc, ABCZ ) ⊢ (q1 , bc, BCZ ) ⊢ (q1 , c, CZ ) ⊢ (q1 , Λ, Z )
⊢ (qf , Λ, Z )
CFG to PDA
Question Construct a PDA ’A’ equivalent to the following Context
free grammar:
S → 0BB, B → 0S |1S |0.
Test whether 010000 is in N(A).

CFG to PDA
free grammar:
S → 0BB, B → 0S |1S |0.
Solution: Let A =({q},{0,1},{S,B,0,1},δ,q,S,ϕ)

CFG to PDA
free grammar:
S → 0BB, B → 0S |1S |0.
δ is defined by following rules:
δ(q, Λ, Z ) = (q, SZ )

CFG to PDA
free grammar:
S → 0BB, B → 0S |1S |0.
δ(q, Λ, Z ) = (q, SZ )
δ(q, 0, S) = (q, BB)

CFG to PDA
free grammar:
S → 0BB, B → 0S |1S |0.
δ(q, Λ, Z ) = (q, SZ )
δ(q, 0, S) = (q, BB)
δ(q, 0, B) = (q, S)

CFG to PDA
free grammar:
S → 0BB, B → 0S |1S |0.
δ(q, Λ, Z ) = (q, SZ )
δ(q, 0, S) = (q, BB)
δ(q, 0, B) = (q, S)
δ(q, 1, B) = (q, S)

CFG to PDA
free grammar:
S → 0BB, B → 0S |1S |0.
δ(q, Λ, Z ) = (q, SZ )
δ(q, 0, S) = (q, BB)
δ(q, 0, B) = (q, S)
δ(q, 1, B) = (q, S)
δ(q, 0, B) = (q, Λ)

CFG to PDA
free grammar:
S → 0BB, B → 0S |1S |0.
δ(q, Λ, Z ) = (q, SZ )
δ(q, 0, S) = (q, BB)
δ(q, 0, B) = (q, S)
δ(q, 1, B) = (q, S)
δ(q, 0, B) = (q, Λ)
δ(q, Λ, Z ) = (qf , Λ)

CFG to PDA
free grammar:
S → 0BB, B → 0S |1S |0.
δ(q, Λ, Z ) = (q, SZ )
δ(q, 0, S) = (q, BB)
δ(q, 0, B) = (q, S)
δ(q, 1, B) = (q, S)
δ(q, 0, B) = (q, Λ)
δ(q, Λ, Z ) = (qf , Λ)
Let the derivation be:
S → 0BB → 01SB → 010BBB → 010000

CFG to PDA
free grammar:
S → 0BB, B → 0S |1S |0.
δ(q, Λ, Z ) = (q, SZ )
δ(q, 0, S) = (q, BB)
δ(q, 0, B) = (q, S)
δ(q, 1, B) = (q, S)
δ(q, 0, B) = (q, Λ)
δ(q, Λ, Z ) = (qf , Λ)
S → 0BB → 01SB → 010BBB → 010000
Acceptability of 010000:

CFG to PDA
free grammar:
S → 0BB, B → 0S |1S |0.
δ(q, Λ, Z ) = (q, SZ )
δ(q, 0, S) = (q, BB)
δ(q, 0, B) = (q, S)
δ(q, 1, B) = (q, S)
δ(q, 0, B) = (q, Λ)
δ(q, Λ, Z ) = (qf , Λ)
S → 0BB → 01SB → 010BBB → 010000
(q,010000,Z)

CFG to PDA
free grammar:
S → 0BB, B → 0S |1S |0.
δ(q, Λ, Z ) = (q, SZ )
δ(q, 0, S) = (q, BB)
δ(q, 0, B) = (q, S)
δ(q, 1, B) = (q, S)
δ(q, 0, B) = (q, Λ)
δ(q, Λ, Z ) = (qf , Λ)
S → 0BB → 01SB → 010BBB → 010000
(q,010000,Z) ⊢ (q,010000,SZ)

CFG to PDA
free grammar:
S → 0BB, B → 0S |1S |0.
δ(q, Λ, Z ) = (q, SZ )
δ(q, 0, S) = (q, BB)
δ(q, 0, B) = (q, S)
δ(q, 1, B) = (q, S)
δ(q, 0, B) = (q, Λ)
δ(q, Λ, Z ) = (qf , Λ)
S → 0BB → 01SB → 010BBB → 010000
(q,010000,Z) ⊢ (q,010000,SZ) ⊢ (q,10000,BB)

CFG to PDA
free grammar:
S → 0BB, B → 0S |1S |0.
δ(q, Λ, Z ) = (q, SZ )
δ(q, 0, S) = (q, BB)
δ(q, 0, B) = (q, S)
δ(q, 1, B) = (q, S)
δ(q, 0, B) = (q, Λ)
δ(q, Λ, Z ) = (qf , Λ)
S → 0BB → 01SB → 010BBB → 010000
(q,010000,Z) ⊢ (q,010000,SZ) ⊢ (q,10000,BB) ⊢ (q,0000,SB)

CFG to PDA
free grammar:
S → 0BB, B → 0S |1S |0.
δ(q, Λ, Z ) = (q, SZ )
δ(q, 0, S) = (q, BB)
δ(q, 0, B) = (q, S)
δ(q, 1, B) = (q, S)
δ(q, 0, B) = (q, Λ)
δ(q, Λ, Z ) = (qf , Λ)
S → 0BB → 01SB → 010BBB → 010000
(q,010000,Z) ⊢ (q,010000,SZ) ⊢ (q,10000,BB) ⊢ (q,0000,SB) ⊢
(q,000,BBB)
CFG to PDA
free grammar:
S → 0BB, B → 0S |1S |0.
δ(q, Λ, Z ) = (q, SZ )
δ(q, 0, S) = (q, BB)
δ(q, 0, B) = (q, S)
δ(q, 1, B) = (q, S)
δ(q, 0, B) = (q, Λ)
δ(q, Λ, Z ) = (qf , Λ)
S → 0BB → 01SB → 010BBB → 010000
(q,010000,Z) ⊢ (q,010000,SZ) ⊢ (q,10000,BB) ⊢ (q,0000,SB) ⊢
(q,000,BBB) ⊢ (q, 00,BB)
CFG to PDA
free grammar:
S → 0BB, B → 0S |1S |0.
δ(q, Λ, Z ) = (q, SZ )
δ(q, 0, S) = (q, BB)
δ(q, 0, B) = (q, S)
δ(q, 1, B) = (q, S)
δ(q, 0, B) = (q, Λ)
δ(q, Λ, Z ) = (qf , Λ)
S → 0BB → 01SB → 010BBB → 010000
(q,010000,Z) ⊢ (q,010000,SZ) ⊢ (q,10000,BB) ⊢ (q,0000,SB) ⊢
(q,000,BBB) ⊢ (q, 00,BB) ⊢ (q,0,B)
CFG to PDA
free grammar:
S → 0BB, B → 0S |1S |0.
δ(q, Λ, Z ) = (q, SZ )
δ(q, 0, S) = (q, BB)
δ(q, 0, B) = (q, S)
δ(q, 1, B) = (q, S)
δ(q, 0, B) = (q, Λ)
δ(q, Λ, Z ) = (qf , Λ)
S → 0BB → 01SB → 010BBB → 010000
(q,010000,Z) ⊢ (q,010000,SZ) ⊢ (q,10000,BB) ⊢ (q,0000,SB) ⊢
(q,000,BBB) ⊢ (q, 00,BB) ⊢ (q,0,B) ⊢ (q,Λ,Z)
CFG to PDA
free grammar:
S → 0BB, B → 0S |1S |0.
δ(q, Λ, Z ) = (q, SZ )
δ(q, 0, S) = (q, BB)
δ(q, 0, B) = (q, S)
δ(q, 1, B) = (q, S)
δ(q, 0, B) = (q, Λ)
δ(q, Λ, Z ) = (qf , Λ)
S → 0BB → 01SB → 010BBB → 010000
(q,010000,Z) ⊢ (q,010000,SZ) ⊢ (q,10000,BB) ⊢ (q,0000,SB) ⊢
(q,000,BBB) ⊢ (q, 00,BB) ⊢ (q,0,B) ⊢ (q,Λ,Z) ⊢ (qf , Λ)
PDA to CFG
Theorem
If A = (Q, Σ, τ, δ, q0 , Z0 , F ) is a pda then there exists a
context-free grammar G such that L(G ) = N(A).
Construction of G for CFG

We define G = (V , Σ, P, S), where
V = {S} ∪ {[q, Z , q ′ ]|q, q ′ ∈ Q, Z ∈ τ } i.e. any element of V is
either the new symbol S acting as the start symbol for G or an
ordered triple whose first and third elements are states and the
second element is a pushdown symbol. The productions in P are
induced by moves of pda as follows:
R1 S-productions are given by S → [q0 , Z0 , q] for every q ∈ Q.
R2 Each transition erasing a pushdown symbol given by
δ(q, a, Z ) = (q ′ , Λ) induces the production [q, Z , q ′ ] → a

PDA to CFG
R3 Each transition not erasing a pushdown symbol giving by
δ(q, a, Z ) = (q1 , Z1 Z2 . . . Zm ) induces the production
[q, Z , q ′ ] → a[q1 , Z1 , q2 ][q2 , Z2 , q3 ] . . . [qm , Zm , q ′ ], where each
of the states q ′ , q2 , . . . , qm can be any state in Q

PDA to CFG
1 S → [q0 , Z0 , qi ]

PDA to CFG
1 S → [q0 , Z0 , qi ]
2 δ(q, a, Z )= (q ′ , Λ)

PDA to CFG
1 S → [q0 , Z0 , qi ]
2 δ(q, a, Z )= (q ′ , Λ)
[q, Z , q ′ ] → a

PDA to CFG
1 S → [q0 , Z0 , qi ]
2 δ(q, a, Z )= (q ′ , Λ)
[q, Z , q ′ ] → a
3 δ(q, Λ, Z )= (q ′ , Λ)

PDA to CFG
1 S → [q0 , Z0 , qi ]
2 δ(q, a, Z )= (q ′ , Λ)
[q, Z , q ′ ] → a
3 δ(q, Λ, Z )= (q ′ , Λ)
[q, Z , q ′ ] → Λ

PDA to CFG
1 S → [q0 , Z0 , qi ]
2 δ(q, a, Z )= (q ′ , Λ)
[q, Z , q ′ ] → a
3 δ(q, Λ, Z )= (q ′ , Λ)
[q, Z , q ′ ] → Λ
4 δ(q, a, Z ) = (q ′ , b)

PDA to CFG
1 S → [q0 , Z0 , qi ]
2 δ(q, a, Z )= (q ′ , Λ)
[q, Z , q ′ ] → a
3 δ(q, Λ, Z )= (q ′ , Λ)
[q, Z , q ′ ] → Λ
4 δ(q, a, Z ) = (q ′ , b)
[q, Z , qi ] → a[q ′ , b, qi ]

PDA to CFG
1 S → [q0 , Z0 , qi ]
2 δ(q, a, Z )= (q ′ , Λ)
[q, Z , q ′ ] → a
3 δ(q, Λ, Z )= (q ′ , Λ)
[q, Z , q ′ ] → Λ
4 δ(q, a, Z ) = (q ′ , b)
[q, Z , qi ] → a[q ′ , b, qi ]
5 δ(q, a, Z ) = (q ′ , bX )

PDA to CFG
1 S → [q0 , Z0 , qi ]
2 δ(q, a, Z )= (q ′ , Λ)
[q, Z , q ′ ] → a
3 δ(q, Λ, Z )= (q ′ , Λ)
[q, Z , q ′ ] → Λ
4 δ(q, a, Z ) = (q ′ , b)
[q, Z , qi ] → a[q ′ , b, qi ]
5 δ(q, a, Z ) = (q ′ , bX )
[q, Z , qi ] → a[q ′ , b, . . .][. . . , X , qi ]

PDA to CFG
1 S → [q0 , Z0 , qi ]
2 δ(q, a, Z )= (q ′ , Λ)
[q, Z , q ′ ] → a
3 δ(q, Λ, Z )= (q ′ , Λ)
[q, Z , q ′ ] → Λ
4 δ(q, a, Z ) = (q ′ , b)
[q, Z , qi ] → a[q ′ , b, qi ]
5 δ(q, a, Z ) = (q ′ , bX )
[q, Z , qi ] → a[q ′ , b, . . .][. . . , X , qi ]
6 δ(q, a, Z ) = (q ′ , bXY )

PDA to CFG
1 S → [q0 , Z0 , qi ]
2 δ(q, a, Z )= (q ′ , Λ)
[q, Z , q ′ ] → a
3 δ(q, Λ, Z )= (q ′ , Λ)
[q, Z , q ′ ] → Λ
4 δ(q, a, Z ) = (q ′ , b)
[q, Z , qi ] → a[q ′ , b, qi ]
5 δ(q, a, Z ) = (q ′ , bX )
[q, Z , qi ] → a[q ′ , b, . . .][. . . , X , qi ]
6 δ(q, a, Z ) = (q ′ , bXY )
[q, Z , qi ] = a[q ′ , b, . . .][. . . , X , . . .][. . . , Y , qi ]

PDA to CFG
Question: Construct a Context free grammar G which accepts
N(A), where A=({q0 , q1 },{a,b},{Z0 ,Z}, δ, q0 , Z0 , ϕ) and δ is given
by:
δ(q0 , b, Z0 ) = (q0 , ZZ0 ), δ(q0 , Λ, Z0 ) = (q0 , Λ)
δ(q0 , b, Z ) = (q0 , ZZ ), δ(q0 , a, Z ) = (q1 , Z )
δ(q1 , b, Z ) = (q1 , Λ), δ(q1 , a, Z0 ) = (q0 , Z0 )

PDA to CFG
by:
δ(q0 , b, Z0 ) = (q0 , ZZ0 ), δ(q0 , Λ, Z0 ) = (q0 , Λ)
δ(q0 , b, Z ) = (q0 , ZZ ), δ(q0 , a, Z ) = (q1 , Z )
δ(q1 , b, Z ) = (q1 , Λ), δ(q1 , a, Z0 ) = (q0 , Z0 )
Solution: Let G=(VN , {a, b}, P, S)

PDA to CFG
by:
δ(q0 , b, Z0 ) = (q0 , ZZ0 ), δ(q0 , Λ, Z0 ) = (q0 , Λ)
δ(q0 , b, Z ) = (q0 , ZZ ), δ(q0 , a, Z ) = (q1 , Z )
δ(q1 , b, Z ) = (q1 , Λ), δ(q1 , a, Z0 ) = (q0 , Z0 )
VN = {S, [q0 , Z0 , q0 ], [q0 , Z0 , q1 ], [q1 , Z0 , q0 ], [q1 , Z0 , q1 ],
[q0 , Z , q0 ], [q0 , Z , q1 ], [q1 , Z , q0 ], [q1 , Z , q1 ]}

PDA to CFG
by:
δ(q0 , b, Z0 ) = (q0 , ZZ0 ), δ(q0 , Λ, Z0 ) = (q0 , Λ)
δ(q0 , b, Z ) = (q0 , ZZ ), δ(q0 , a, Z ) = (q1 , Z )
δ(q1 , b, Z ) = (q1 , Λ), δ(q1 , a, Z0 ) = (q0 , Z0 )
[q0 , Z , q0 ], [q0 , Z , q1 ], [q1 , Z , q0 ], [q1 , Z , q1 ]}
The Productions are:
Initial: S → [q0 , Z0 , q0 ], [q0 , Z0 , q1 ]

PDA to CFG
by:
δ(q0 , b, Z0 ) = (q0 , ZZ0 ), δ(q0 , Λ, Z0 ) = (q0 , Λ)
δ(q0 , b, Z ) = (q0 , ZZ ), δ(q0 , a, Z ) = (q1 , Z )
δ(q1 , b, Z ) = (q1 , Λ), δ(q1 , a, Z0 ) = (q0 , Z0 )
[q0 , Z , q0 ], [q0 , Z , q1 ], [q1 , Z , q0 ], [q1 , Z , q1 ]}
Initial: S → [q0 , Z0 , q0 ], [q0 , Z0 , q1 ]
For δ(q0 , b, Z0 ) = (q0 , ZZ0 )

PDA to CFG
by:
δ(q0 , b, Z0 ) = (q0 , ZZ0 ), δ(q0 , Λ, Z0 ) = (q0 , Λ)
δ(q0 , b, Z ) = (q0 , ZZ ), δ(q0 , a, Z ) = (q1 , Z )
δ(q1 , b, Z ) = (q1 , Λ), δ(q1 , a, Z0 ) = (q0 , Z0 )
[q0 , Z , q0 ], [q0 , Z , q1 ], [q1 , Z , q0 ], [q1 , Z , q1 ]}
Initial: S → [q0 , Z0 , q0 ], [q0 , Z0 , q1 ]
For δ(q0 , b, Z0 ) = (q0 , ZZ0 )
[q0 Z0 . . .] → b[q0 Z . . .][. . . Z0 . . .]
[q0 Z0 . . .] → b[q0 Z . . .][. . . Z0 . . .]
[q0 Z0 . . .] → b[q0 Z . . .][. . . Z0 . . .]
[q0 Z0 . . .] → b[q0 Z . . .][. . . Z0 . . .]
PDA to CFG
by:
δ(q0 , b, Z0 ) = (q0 , ZZ0 ), δ(q0 , Λ, Z0 ) = (q0 , Λ)
δ(q0 , b, Z ) = (q0 , ZZ ), δ(q0 , a, Z ) = (q1 , Z )
δ(q1 , b, Z ) = (q1 , Λ), δ(q1 , a, Z0 ) = (q0 , Z0 )
[q0 , Z , q0 ], [q0 , Z , q1 ], [q1 , Z , q0 ], [q1 , Z , q1 ]}
Initial: S → [q0 , Z0 , q0 ], [q0 , Z0 , q1 ]
For δ(q0 , b, Z0 ) = (q0 , ZZ0 )
[q0 Z0 q0 ] → b[q0 Zq0 ][q0 Z0 q0 ]
[q0 Z0 q0 ] → b[q0 Zq1 ][q1 Z0 q0 ]
[q0 Z0 q1 ] → b[q0 Zq0 ][q0 Z0 q1 ]
[q0 Z0 q1 ] → b[q0 Zq1 ][q1 Z0 q1 ]
PDA to CFG
For δ(q0 , ∧, Z0 ) = (q0 , ∧)

[q0 Z0 q0 ] → ∧

PDA to CFG
For δ(q0 , ∧, Z0 ) = (q0 , ∧)

[q0 Z0 q0 ] → ∧
(q0 , b, Z ) = (q0 , ZZ )
[q0 Z . . .] → b[q0 Z . . .][. . . Z . . .]
[q0 Z . . .] → b[q0 Z . . .][. . . Z . . .]
[q0 Z . . .] → b[q0 Z . . .][. . . Z . . .]
[q0 Z . . .] → b[q0 Z . . .][. . . Z . . .]

PDA to CFG
For δ(q0 , ∧, Z0 ) = (q0 , ∧)

[q0 Z0 q0 ] → ∧
(q0 , b, Z ) = (q0 , ZZ )
[q0 Zq0 ] → b[q0 Zq0 ][q0 Zq0 ]
[q0 Zq0 ] → b[q0 Zq1 ][q1 Zq0 ]
[q0 Zq1 ] → b[q0 Zq0 ][q0 Zq1 ]
[q0 Zq1 ] → b[q0 Zq1 ][q1 Zq1 ]

PDA to CFG
For δ(q0 , ∧, Z0 ) = (q0 , ∧)

[q0 Z0 q0 ] → ∧
(q0 , b, Z ) = (q0 , ZZ )
[q0 Zq0 ] → b[q0 Zq0 ][q0 Zq0 ]
[q0 Zq0 ] → b[q0 Zq1 ][q1 Zq0 ]
[q0 Zq1 ] → b[q0 Zq0 ][q0 Zq1 ]
[q0 Zq1 ] → b[q0 Zq1 ][q1 Zq1 ]
For (q0 , a, Z ) = (q1 , Z )

PDA to CFG
For δ(q0 , ∧, Z0 ) = (q0 , ∧)

[q0 Z0 q0 ] → ∧
(q0 , b, Z ) = (q0 , ZZ )
[q0 Zq0 ] → b[q0 Zq0 ][q0 Zq0 ]
[q0 Zq0 ] → b[q0 Zq1 ][q1 Zq0 ]
[q0 Zq1 ] → b[q0 Zq0 ][q0 Zq1 ]
[q0 Zq1 ] → b[q0 Zq1 ][q1 Zq1 ]
For (q0 , a, Z ) = (q1 , Z )
[q0 Z . . .] → a[q1 Z . . .]
[q0 Z . . .] → a[q1 Z . . .]

PDA to CFG
For δ(q0 , ∧, Z0 ) = (q0 , ∧)
[q0 Z0 q0 ] → ∧
(q0 , b, Z ) = (q0 , ZZ )
[q0 Zq0 ] → b[q0 Zq0 ][q0 Zq0 ]
[q0 Zq0 ] → b[q0 Zq1 ][q1 Zq0 ]
[q0 Zq1 ] → b[q0 Zq0 ][q0 Zq1 ]
[q0 Zq1 ] → b[q0 Zq1 ][q1 Zq1 ]
For (q0 , a, Z ) = (q1 , Z )
[q0 Zq0 ] → a[q1 Zq0 ]
[q0 Zq1 ] → a[q1 Zq1 ]

PDA to CFG
For δ(q0 , ∧, Z0 ) = (q0 , ∧)
[q0 Z0 q0 ] → ∧
(q0 , b, Z ) = (q0 , ZZ )
[q0 Zq0 ] → b[q0 Zq0 ][q0 Zq0 ]
[q0 Zq0 ] → b[q0 Zq1 ][q1 Zq0 ]
[q0 Zq1 ] → b[q0 Zq0 ][q0 Zq1 ]
[q0 Zq1 ] → b[q0 Zq1 ][q1 Zq1 ]
For (q0 , a, Z ) = (q1 , Z )
[q0 Zq0 ] → a[q1 Zq0 ]
[q0 Zq1 ] → a[q1 Zq1 ]
For δ(q1 , b, Z ) = (q1 , ∧)
[q1 , Z , q1 ] → b

PDA to CFG
For δ(q0 , ∧, Z0 ) = (q0 , ∧)
[q0 Z0 q0 ] → ∧
(q0 , b, Z ) = (q0 , ZZ )
[q0 Zq0 ] → b[q0 Zq0 ][q0 Zq0 ]
[q0 Zq0 ] → b[q0 Zq1 ][q1 Zq0 ]
[q0 Zq1 ] → b[q0 Zq0 ][q0 Zq1 ]
[q0 Zq1 ] → b[q0 Zq1 ][q1 Zq1 ]
For (q0 , a, Z ) = (q1 , Z )
[q0 Zq0 ] → a[q1 Zq0 ]
[q0 Zq1 ] → a[q1 Zq1 ]
For δ(q1 , b, Z ) = (q1 , ∧)
[q1 , Z , q1 ] → b
For δ(q1 , a, Z0 ) → (q0 , Z0 )
[q1 , Z0 , . . .] → a[q0 Z0 . . .]
[q1 , Z0 , . . .] → a[q0 Z0 . . .]

PDA to CFG
For δ(q0 , ∧, Z0 ) = (q0 , ∧)
[q0 Z0 q0 ] → ∧
(q0 , b, Z ) = (q0 , ZZ )
[q0 Zq0 ] → b[q0 Zq0 ][q0 Zq0 ]
[q0 Zq0 ] → b[q0 Zq1 ][q1 Zq0 ]
[q0 Zq1 ] → b[q0 Zq0 ][q0 Zq1 ]
[q0 Zq1 ] → b[q0 Zq1 ][q1 Zq1 ]
For (q0 , a, Z ) = (q1 , Z )
[q0 Zq0 ] → a[q1 Zq0 ]
[q0 Zq1 ] → a[q1 Zq1 ]
For δ(q1 , b, Z ) = (q1 , ∧)
[q1 , Z , q1 ] → b
For δ(q1 , a, Z0 ) → (q0 , Z0 )
[q1 , Z0 , q0 ] → a[q0 Z0 q0 ]
[q1 , Z0 , q1 ] → a[q0 Z0 q1 ]

PDA to CFG
1 Let M=({q0 , q1 },{a,b},{a,Z0 }, δ, q0 , Z0 , ϕ)

where productions are
δ(q0 , a, Z0 ) = (q0 , aZ0 )
δ(q0 , a, a) = (q0 , aa)
δ(q0 , b, a) = (q1 , ∧)
δ(q1 , b, a) = (q1 , ∧)
δ(q1 , ∧, Z0 ) = (q1 , ∧)
Find grammar G.
2 Find a context free grammar that generates the language
accepted by NPDA
M=({q0 , q1 },{a,b},{A,Z},δ,q0 ,Z,{q1 }) with transitions
δ(q0 , a, Z ) = (q0 , AZ )
δ(q0 , b, A) = (q0 , AA)
δ(q0 , a, A) = (q1 , Λ)

PDA to CFG
Example: Construct a PDA accepting {an b m an |m, n ≥ 1} by null
store. Construct the corresponding CFG accepting the same set.

PDA to CFG
Solution: The PDA ’A’ accepting {an b m an |m, n ≥ 1} is defined as

PDA to CFG
A=({q0 , q1 },{a,b},{a,Z0 }, δ, q0 , Z0 , ϕ)

PDA to CFG
A=({q0 , q1 },{a,b},{a,Z0 }, δ, q0 , Z0 , ϕ)
where δ is defined by:
δ(q0 , a, Z0 ) = (q0 , aZ0 )

PDA to CFG
A=({q0 , q1 },{a,b},{a,Z0 }, δ, q0 , Z0 , ϕ)
δ(q0 , a, Z0 ) = (q0 , aZ0 )
δ(q0 , a, a) = (q0 , aa)

PDA to CFG
A=({q0 , q1 },{a,b},{a,Z0 }, δ, q0 , Z0 , ϕ)
δ(q0 , a, Z0 ) = (q0 , aZ0 )
δ(q0 , a, a) = (q0 , aa)
δ(q0 , b, a) = (q1 , a)

PDA to CFG
A=({q0 , q1 },{a,b},{a,Z0 }, δ, q0 , Z0 , ϕ)
δ(q0 , a, Z0 ) = (q0 , aZ0 )
δ(q0 , a, a) = (q0 , aa)
δ(q0 , b, a) = (q1 , a)
δ(q1 , b, a) = (q1 , a)

PDA to CFG
A=({q0 , q1 },{a,b},{a,Z0 }, δ, q0 , Z0 , ϕ)
δ(q0 , a, Z0 ) = (q0 , aZ0 )
δ(q0 , a, a) = (q0 , aa)
δ(q0 , b, a) = (q1 , a)
δ(q1 , b, a) = (q1 , a)
δ(q1 , a, a) = (q1 , ∧)

PDA to CFG
A=({q0 , q1 },{a,b},{a,Z0 }, δ, q0 , Z0 , ϕ)
δ(q0 , a, Z0 ) = (q0 , aZ0 )
δ(q0 , a, a) = (q0 , aa)
δ(q0 , b, a) = (q1 , a)
δ(q1 , b, a) = (q1 , a)
δ(q1 , a, a) = (q1 , ∧)
δ(q1 , ∧, Z0 ) = (q1 , ∧)

PDA to CFG
A=({q0 , q1 },{a,b},{a,Z0 }, δ, q0 , Z0 , ϕ)
δ(q0 , a, Z0 ) = (q0 , aZ0 )
δ(q0 , a, a) = (q0 , aa)
δ(q0 , b, a) = (q1 , a)
δ(q1 , b, a) = (q1 , a)
δ(q1 , a, a) = (q1 , ∧)
δ(q1 , ∧, Z0 ) = (q1 , ∧)
Let the required grammar G=(VN , {a, b}, P, S)

PDA to CFG
A=({q0 , q1 },{a,b},{a,Z0 }, δ, q0 , Z0 , ϕ)
δ(q0 , a, Z0 ) = (q0 , aZ0 )
δ(q0 , a, a) = (q0 , aa)
δ(q0 , b, a) = (q1 , a)
δ(q1 , b, a) = (q1 , a)
δ(q1 , a, a) = (q1 , ∧)
δ(q1 , ∧, Z0 ) = (q1 , ∧)
VN =
(S, [q0 Z0 q0 ], [q0 Z0 q1 ], [q1 Z0 q0 ], [q1 Z0 q1 ], q0 aq0 ], [q0 aq1 ], [q1 aq0 ], [q1 aq1 ])

PDA to CFG
A=({q0 , q1 },{a,b},{a,Z0 }, δ, q0 , Z0 , ϕ)
δ(q0 , a, Z0 ) = (q0 , aZ0 )
δ(q0 , a, a) = (q0 , aa)
δ(q0 , b, a) = (q1 , a)
δ(q1 , b, a) = (q1 , a)
δ(q1 , a, a) = (q1 , ∧)
δ(q1 , ∧, Z0 ) = (q1 , ∧)
VN =
(S, [q0 Z0 q0 ], [q0 Z0 q1 ], [q1 Z0 q0 ], [q1 Z0 q1 ], q0 aq0 ], [q0 aq1 ], [q1 aq0 ], [q1 aq1 ])
...

Exercise
1 What do you understand by LL(k) grammar? Explain with a

suitable example.
2 What do you understand by Parsing? How Top-Down Parsing
is different from Bottom-Up Parsing? Explain with suitable
example.
3 What is left factoring? How is it different from Left recursion?
4 Construct a PDA accepting the set of ll even-length
palindromes over {a,b} by the empty store.

Questions?
+91 9911375598, akyadav1@amity.edu
Thank you

Module 2

Uploaded by

Copyright:

Available Formats

Module 2

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Module 2

Uploaded by

Copyright:

Available Formats

Context Free Grammars and Pushdown

Amity School of Engineering and Technology

December 21, 2022

Sub-topic Learning Objective Learning Outcomes

Dr. A K Yadav CFG and PDA December 21, 2022 2/63

Dr. A K Yadav CFG and PDA December 21, 2022 3/63

Context Free Grammar

Finite Automata accepts all regular languages.

Dr. A K Yadav CFG and PDA December 21, 2022 4/63

A Context-free grammar is a 4-tuple (Vn , Σ, P, S)

Dr. A K Yadav CFG and PDA December 21, 2022 5/63

Contruct a CFG generating all integers (with sign).

Dr. A K Yadav CFG and PDA December 21, 2022 6/63

Contruct a CFG generating all integers (with sign).

Dr. A K Yadav CFG and PDA December 21, 2022 6/63

Contruct a CFG generating all integers (with sign).

Dr. A K Yadav CFG and PDA December 21, 2022 6/63

Dr. A K Yadav CFG and PDA December 21, 2022 7/63

Yield of Derivation Tree:is a

Subtree of a Derivation Tree

Dr. A K Yadav CFG and PDA December 21, 2022 9/63

Dr. A K Yadav CFG and PDA December 21, 2022 9/63

Dr. A K Yadav CFG and PDA December 21, 2022 9/63

Dr. A K Yadav CFG and PDA December 21, 2022 9/63

Dr. A K Yadav CFG and PDA December 21, 2022 10/63

Dr. A K Yadav CFG and PDA December 21, 2022 11/63

Dr. A K Yadav CFG and PDA December 21, 2022 11/63

Dr. A K Yadav CFG and PDA December 21, 2022 11/63

Dr. A K Yadav CFG and PDA December 21, 2022 11/63

In books selected information is given.

Dr. A K Yadav CFG and PDA December 21, 2022 12/63

In books selected information is given.

Dr. A K Yadav CFG and PDA December 21, 2022 12/63

Dr. A K Yadav CFG and PDA December 21, 2022 13/63

Dr. A K Yadav CFG and PDA December 21, 2022 13/63

Dr. A K Yadav CFG and PDA December 21, 2022 13/63

Dr. A K Yadav CFG and PDA December 21, 2022 13/63

We eliminate following in order to simplify a grammar:

Dr. A K Yadav CFG and PDA December 21, 2022 14/63

Eliminating Useless Variables

Dr. A K Yadav CFG and PDA December 21, 2022 15/63

Eliminating Useless Variables

Dr. A K Yadav CFG and PDA December 21, 2022 15/63

Eliminating Useless Variables

Dr. A K Yadav CFG and PDA December 21, 2022 15/63

Eliminating Useless Variables

Dr. A K Yadav CFG and PDA December 21, 2022 15/63

Eliminating Unit Productions

Production of the form A → B is known as Unit Production

Dr. A K Yadav CFG and PDA December 21, 2022 16/63

Eliminating Unit Productions

Production of the form A → B is known as Unit Production

Dr. A K Yadav CFG and PDA December 21, 2022 16/63

Eliminating Unit Productions

Production of the form A → B is known as Unit Production

Dr. A K Yadav CFG and PDA December 21, 2022 16/63

Eliminating Unit Productions

Example:S → Aa|B, B → A|bb, A → a|bc|B

Dr. A K Yadav CFG and PDA December 21, 2022 17/63