21CSC301T

FORMAL LANGUAGE AND AUTOMATA

UNIT 3
Pushdown Automata and Parsing Algorithms
Definition of a Pushdown Automata (PDA)
• The context free languages have a type of automata called
“pushdown automata” (PDA).

• It is an ε-NFA with the addition of a stack.

• The stack can be read, pushed and popped only at the top

• The PDA can remember an infinite amount of information.

• A transition in a PDA is based on its current state, the

input symbol and the symbol at the top of the stack.

• Alternatively, it may make a “spontaneous” transition

using ε as its input instead of an input symbol.

• Pushdown automata recognize all and only context-free

languages.
Definition of a Pushdown Automata (PDA) – cont..
• In one transition, the PDA does the following:

1. Consumes the input symbol.

2. Moves to a new state.

3. Replaces the symbol at the top of stack by a string.

• The string could be ε, which corresponds to a pop of the stack.

• It could be the same symbol that appeared at the top of the stack previously, which
signifies that no change is made to the stack.

• It could also replace the top stack symbol by one other symbol, which in effect changes the
top of the stack but does not push or pop it.

• It could be two or more symbols, which has the effect of (possibly) changing the top
stack symbol, and then pushing one or more new symbols onto the stack.
Formal Definition of Pushdown Automata
A PDA can be formally described as a 7-tuple
P = {Q, ∑, Γ, δ, q0, Z0, F }
where
Q → set of states
∑ → input alphabet
Γ → stack alphabet (symbols that can be present in the stack) δ
→ transition function. It is of the form δ(q,a,X) = (p,γ)
where q → present state p → next state
a → input symbol γ → string that replaces the top of the stack X
→ symbol at the top of the stack
q0 → initial state
Z0 → bottom marker of the stack
F → set of final states
 Instantaneous Descriptions of a PDA
• In a finite automata, the state is the only thing that we need to know about the automaton.

• But, the PDA goes from configuration to configuration, in response to input symbols (sometimes ε).

• The configuration of a PDA involves both the state and the contents of the stack.

• The stack is often the more important part of the total configuration of the PDA at any time.

• Thus, the configuration of a PDA at any time is represented by a triple (𝑞, 𝑤, 𝛾) where.

1. 𝑞 is the present state.

2. 𝑤 is the remaining input.
3. 𝛾 is the stack contents (the top of the stack at the left end of γ and the bottom at the right end).
• Such a triple is called an instantaneous description, or ID of the pushdown automata.
 Turnstile Notation
• For finite automata, the δ notation was sufficient to represent sequences of instantaneous descriptions
through which a finite automaton moved, since the ID for a finite automaton is just its state.

• However, for PDA’s we need a notation that describes changes in the state, the input and stack.

• The ‘turnstile’ notation is used for connecting pairs of IDs that represent one or many moves of a
PDA.

• The turnstile notation is ⊢.

The Languages of a PDA
• The languages of a PDA can be defined in two ways: (We can design PDAs in two ways)

1. Acceptance by Final State – When we finish reading the input, if the PDA is in a final
state, the input will be accepted. The contents of the stack at that time is irrelevant.

2. Acceptance by Empty Stack – When we finish reading the input, if the stack is empty, the
input will be accepted, regardless of the state it is in. That is, the PDA can be in any of the
states at the time of accepting the input. There will be no final states in this design.

• These two methods are equivalent, in the sense that “A language L has a PDA that accepts by final
state if an only if L has a PDA that accepts it by empty stack”.
Example 1 : PDA for the language 0n1n
Example : PDA for the language 0n1n – cont..
Show all reachable IDs from the initial ID for the string 000111
Example 2 : PDA for the language 0n1m0n
Example 2 : PDA for the language 0n1m0n – cont..
Show all reachable IDs from the initial ID for the string 00011000
 Some Preliminary Concepts

Acceptance by Final State and Empty Stack

• Let 𝑃 = (𝑄, ∑, Γ, 𝛿, 𝑞0, 𝑍0, 𝐹) be a PDA. Then

• L(P) is the language accepted by P by final state and

• N(P) is the language accepted by P be empty stack

• PF represents a PDA that accepts by final state

• PN represents a PDA that accepts by empty stack

 Some Preliminary Concepts

Prefix Property

• A language L has the prefix property if there are no two different strings 𝑥 and 𝑦 in L such that 𝑥 is the
prefix of 𝑦

• Examples:

• The language 𝐿0𝑛1𝑛 has the prefix property. It is not possible for there to be two strings w=0n1n and
x=0m1m, one of which is a prefix of the other, unless they are the same string

• There are some very simple languages that do not have prefix property. Consider L=0*, the set
of all strings of 0’s. If we take any two strings, one is a prefix of the other
 Deterministic Pushdown Automata

• A PDA is deterministic if there is never a choice of move in any situation.

• These choices are of two kinds:

• If δ(q,a,X) contains more than one pair

• If there is a choice between using a real input symbol, or making a move on ε

• Thus, we define a PDA 𝑃 = (𝑄, ∑, Γ, 𝛿, 𝑞0, 𝑍0, 𝐹) to be deterministic (DPDA) if and only if the following
conditions are met

1. 𝛿(𝑞, 𝑎, 𝑋) has at most one member for any q in Q, a in ∑ or a in ε, and X in Γ

2. If 𝛿(𝑞, 𝑎, 𝑋) is nonempty, for some a in ∑, then δ(q,ε,X) must be empty
 Languages defined by DPDA
• The DPDA’s accept a class of languages that is between the regular languages and the CFLs

• That is, the languages accepted by DPDA’s by final state properly include the regular languages, but are
properly included in the CFL’s

• A language L is N(P) for some DPDA P if and only if L has the prefix property and L is L(𝑃’) for some
DPDA 𝑃’ (That is, for languages without prefix property we can construct a PDA that accepts by empty
stack, but it will not be deterministic)

• The two modes of acceptance – final state and empty stack – are not the same for DPDA’s. Rather,
the languages accepted by empty stack are exactly those of the languages accepted by final state that
have the prefix property.

• All the languages that are accepted by DPDA’s have unambiguous grammars, but all unambiguous
grammars does not have a DPDA

• For instance, the language 𝐿𝑤𝑤𝑟 has an unambiguous grammar S → 0S0 | 1S1 | ε But we cannot
construct a DPDA for the language
Example 1 : DPDA for the language L={0n1n | n≥1}
Formal Definition of the PDA

P = {Q, ∑, Γ, δ, q0, Z0, F }

=( {q0, q1, q2}, {0,1}, {0,Z0}, δ, q0, Z0, {q3} )

where δ is defined as

δ(q0, 0, Z0) = (q0, 0Z0)

δ(q0, 0, 0) = (q0, 00)

δ(q0, 1, 0) = (q1, ε)

δ(q1, 1, 0) = (q1, ε)

δ(q1, ε, Z0) = (q2, ε)

Example 1 : DPDA for the language L={0n1n | n≥1} – cont..
Show all reachable IDs from the initial ID for the string 000111

(q0, 000111, Z0) ⊢ (q0, 00111, 0Z0)

⊢ (q0, 0111, 00Z0)

⊢ (q0, 111, 000Z0)

⊢ (q1, 11, 00Z0)

⊢ (q1, 1, 0Z0)

⊢ (q1, ε, Z0)

⊢ (q2, ε, ε)
Example 2 : DPDAfor the language L={0n1m0n | m,n≥1}
Formal Definition of the PDA

P = {Q, ∑, Γ, δ, q0, Z0, F }

=( {q0, q1, q2, q3}, {0,1}, {0,Z0}, δ, q0, Z0, {q3} )

where δ is defined as

δ(q0, 0, Z0) = (q0, 0Z0)

δ(q0, 0, 0) = (q0, 00)

δ(q0, 1, 0) = (q1, 0)

δ(q1, 1, 0) = (q1, 0)

δ(q1, 0, 0) = (q2, ε)

δ(q2, 0, 0) = (q2, ε)

δ(q2, ε, Z0) = (q3, ε)

Example 2 : DPDA for the language L={0n1m0n | m,n≥1}– cont..
Show all reachable IDs from the initial ID for the string 00011000

(q0, 00011000, Z0) ⊢ (q0, 0011000, 0Z0)

⊢ (q0, 011000, 00Z0)

⊢ (q0, 11000, 000Z0)

⊢ (q1, 1000, 000Z0)

⊢ (q2, 000, 000Z0)

⊢ (q2, 00, 00Z0)

⊢ (q2, 0, 0Z0)

⊢ (q2, ε, Z0)

⊢ (q3, ε, ε)
Example 3 : DPDAfor the language L = { 0n12n, n≥1 }
Logic for designing the PDA

1. Push all 0’s into the stack

2. For alternate 1’s pop a 0 from the stack

3. When we finish reading the input, if we reach the bottom of the stack, the input is accepted

Pictorial representation of the PDA

Example 4 : DPDAfor the language L = { w|w∈(a+b)*andna(w)=nb(w) K
Logic for designing the PDA

1. When the stack is empty, whatever input symbol we read, we push it into the stack

2. When the symbol at the top of the stack and the input symbol are the same, then push the input
symbol into the stack

3. When the symbol at the top of the stack and the input symbol are the different, then pop the
symbol at the top of the stack

4. When we finish reading the input, if we reach the bottom of the stack, the input is accepted

Pictorial representation of the PDA

Example 5 : DPDAfor the language that accepts strings of well formed
parenthesis. Consider the parenthesis as (, ), [, ], {, K
Logic for designing the PDA

1. Push all left parenthesis into the stack

2. When we read a right parenthesis, if the top of the stack has a matching left parenthesis, then pop
the symbol at the top of the stack

3. When we finish reading the input, if we reach the bottom of the stack, accept the input.

Pictorial representation of the PDA

Example 6 : DPDA for the language L = {0n1m+n0m| n,m ≥1 K
Sample strings: Logic in simple words

n=2, m=3 0011111000 1. Push the 0’s in the front into the stack
n=3, m=5 0001111111100000 2. For every 1 we read, if there is a 0 in the stack
Logic for designing the PDA then pop it

1. Push n 0’s into the stack 3. Push the remaining 1’s into the stack

2. For n 1’s, pop n 0’s from the stack 3. For every 0, if there is a 1 in the stack, pop it

3. Push m 1’s into the stack 4. When we finish reading the input, if the stack is
empty, accept the input
4. For m 1’s, pop m 0’s from the stack
Example 7 : DPDAfor the language L={ambmcn | m,n≥1}
Example 8 : DPDA for the language L={anbm | n<m and m,n≥1}
Logic for designing the PDA

1. Push all a’s into the stack

2. For every b we read, pop one a from the stack

3. If the stack becomes empty and if there are b’s left over in the input, then, consume all the
input and accept the input

Pictorial Representation of the PDA

Example 9 : DPDA for the language L={ambncndm | m,n≥1}

Logic for designing the PDA

1. Push all a’s into the stack

2. Push all b’s into the stack

3. For every c we read, pop one b from the stack

4. For every d we read, pop one a from the stack

5. On consuming all the input if we reach the end of the stack, accept the input

Pictorial Representation of the PDA

Example 10 : DPDAfor the language L = { wcwR | w∈(0+1)*and c isthe centermarker
Sample Strings

01101c10110, 110c011

All palindrome strings of 0’s and 1’s with c in the middle The

CFG for the language is S → 0S0 | 1S1 | c

Logic for designing the PDA

1. Push all the input symbols (both 0’s and 1’s) into the stack till we read c

2. On reading c, skip it and move to another state

3. Then for every input, if the input symbol matches the symbol at the top of the stack, pop the
symbol at the top of the stack

4. When we finish reading the input, if we reach the bottom of the stack, the input is accepted
Example 10 : DPDAfor the language L = { wcwR | w∈(0+1)*and c isthe centermarker–
cont..
Example 11 : DPDA for the language L={a2nbn | n≥1}
 Example 12 : DPDA for the language L = {0n1m+n1m| n,m ≥1 K
Logic
• Push all 0’s into the stack
• On reading 1, if there is a 0 in the stack pop it.
(By this time, we have consumed 𝑛 1’s. Now we should have 1𝑚1𝑚 , that is, 2𝑚 number of 1’s
remaining in the input, that is, even number of 1’s in the input)
• To check if we have even number of 1’s, repeat the following until we consume all the input:
1. Push a 1 into the stack
2. Pop 1 from the stack
• At the end of the input, if the stack is empty, accept the input
Pictorial representation of the PDA
 Non Deterministic Pushdown Automata (NPDA)

• A Non Deterministic Pushdown Automata can have a choice of move.

• We consider a PDA as non deterministic, if any of the following conditions is satisfied

1. 𝛿(𝑞, 𝑎, 𝑋) has more than one member for any q in Q, a in ∑ or a in ε, and X in Γ

2. 𝛿(𝑞, 𝑎, 𝑋) and δ(q,ε,X) are nonempty
• A NPDA is used to generate a language that a DPDA cannot generate

• NPDA is more powerful than a DPDA

Example 1 : NPDAfor the language 𝐿𝑤𝑤𝑟 = { 𝑤𝑤𝑅 | 𝑤 ∈ (0 + 1) ∗ }
• This language is often referred to as “𝑤 − 𝑤 − 𝑟𝑒𝑣𝑒𝑟𝑠𝑒𝑑”
• It is the even-length palindromes over the alphabet ∑ = { 0, 1 }

Logic
• State q0 represents a “guess” that we have not yet seen the
middle of the input, that is, the end of w. So, in
state q0, we read symbols and store them on the stack
• At any time, we may guess that we have seen the middle,
that is, the end of w. At this time, w will be on
the stack, with the right end of w at the top. We signify
this choice by spontaneously going to state q1
• Once in state q1, we compare input symbols with the
symbol at the top of the stack. If they match, we pop the
stack and proceed
• If the stack is empty on reaching the end of the input,
accept the input
Example 1 : NPDAfor the language 𝐿𝑤𝑤𝑟 = { 𝑤𝑤𝑅 | 𝑤 ∈ (0 + 1) ∗ } – cont..
Example 1 : NPDAfor the language 𝐿𝑤𝑤𝑟 = { 𝑤𝑤𝑅 | 𝑤 ∈ (0 + 1) ∗ } – cont..
Example 2 : NPDA for the language
|
𝐿 = {𝑎 𝑏 | 𝑛 ≥ 1} 𝑈 {𝑎 𝑏 𝑛 ≥ 1}
𝑛 𝑛 𝑛 2𝑛

Formal Definition of the PDA

P = {Q, ∑, Γ, δ, q0, Z0, F }
=( {q0, q1, q2, q3, q4}, {a,b}, {a,Z0}, δ, q0, Z0, {q4} )
where δ is defined as
δ(q0, a, Z0) = (q0, aZ0)
δ(q0, a, a) = (q0, aa)
δ(q0, b, a) = { (q1, ε), (q2, a) }
δ(q1, b, a) = (q1, ε)
δ(q1, ε, Z0) = (q4, ε)
δ(q2, b, a) = (q3, ε)
δ(q3, b, a) = (q2, a)
δ(q3, ε, Z0) = (q4, ε)
Example 3 : NPDAfor the language
𝐿 = {aibjckdl| 𝑖 == 𝑘 𝑜𝑟 𝑗 == 𝑙 }

δ(q0, a, Z0) = { (q1, aZ0 ), (q2, Z0) }

 Some Languages which are not context free

• L = {𝑎𝑛𝑏𝑛𝑐𝑛 | 𝑛 ≥ 1}

• L = 𝑎𝑖𝑏𝑗𝑐𝑘𝑑𝑙 𝑖 == 𝑘 𝑎𝑛𝑑 𝑗 == 𝑙}
 Equivalence of PDA’s and CFG’s

• The languages defined by PDA’s are exactly the context-free languages

• The following three classes of languages are all the same:

1. The context free languages, i.e., the languages defined by CFG’s

2. The languages that are accepted by final state by some PDA

3. The languages that are accepted by empty stack by some PDA

 From PDA’s to CFGs

• The construction of an equivalent grammar uses variables each of which represents an “event”
consisting of

1. The net popping of some symbol X from the stack, and

2. A change in state from some p at the beginning to q when X has finally been replaced by ε on the
stack

• We represent such a variable (non-terminal) by the composite symbol [𝑝𝑋𝑞]. This sequence of
characters is our way of describing one non-terminal.
 Steps in converting a PDA to CFG

• Let S be the start symbol

• For all 𝑞𝑖 ∈ 𝑄, add a production rule 𝑺 → [𝒒𝟎𝒁𝟎𝒒𝒊]. If the PDA contains n number of states, there will
be n number of productions from the start symbol

• For the δ function 𝛿 𝑞, 𝑎, 𝑌 = (𝑟, 𝜀) where 𝑞, 𝑟 ∈ 𝑄, 𝑎 ∈ σ 𝑎𝑛𝑑 𝑌 ∈ Γ, add the production rule [𝒒𝒀𝒓] → 𝒂

• For the transition function 𝛿 𝑞, 𝑎, 𝑌 = (𝑟, 𝑌1𝑌2 … . 𝑌𝑘) where 𝑞, 𝑟 ∈ 𝑄, 𝑎 ∈ σ 𝑎𝑛𝑑 𝑌1𝑌2 … . 𝑌𝑘 ∈ Γ, then
for each choice of 𝑞1, 𝑞2, … . , 𝑞𝑘 ∈ 𝑄, add production 𝒒𝒀𝒒𝒌 → 𝒂 𝒒𝒀𝟏𝒒𝟏 𝒒𝟏𝒀𝟐𝒒𝟐 … . . [𝒒𝒌−𝟏𝒀𝒌𝒒𝒌]
 Example 1
Formulate a Context Free Grammar to represent the
language defined by the Pushdown Automata given
below:

P=({p,q},{0,1},{X, Z0},δ,q,Z0) where δ is

defined as

δ(q,1,Z0)={(q,XZ0)}

δ(q,1,X)={(p,XX)}

δ(q,0,X)={(p,X)}

δ(q,ℇ,X)={(q,ℇ)}

δ(p,1,X)={(p,ℇ)}

δ(p,0,Z0)={(q,Z0)}
 Example 2
Formulate a Context Free Grammar to represent the language defined by the Pushdown Automata given below:

M=({q0,q1},{0,1},{X,Z0},δ, q0,Z0) where δ is defined as

δ(q0,0,Z0)={(q0,XZ0)}
δ(q1,1,X)={(q1,ℇ)}
δ(q0,0,X)={(q0,XX)}
δ(q1,ℇ,X)={(q1,ℇ)}
δ(q0,1,X)={(q1,ℇ)}
δ(q1,ℇ,Z0)={(q1,ℇ)}
 Example 3
Formulate a Context Free Grammar to represent the language defined by the Pushdown Automata given below:

M=({q0,q1},{0,1},{Z0,X},δ, q0,Z0) where δ is defined as

δ(q0,1,Z0)={(q0,XZ0)}
δ(q0,1,X)={(q0,XX)}
δ(q0,0,X)={(q1,X)}
δ(q1,ℇ, Z0)={(q0,ℇ)}
δ(q1,1,X)={(q1,ℇ)}
δ(q1,0,Z0)={(q0, Z0)}
 Example 4
Formulate a Context Free Grammar to represent the language defined by the Pushdown Automata given below:

M=({s0,s1},{0,1},{X,Z0},δ, s0, Z0) where δ is

defined as
δ(s0,1,Z0)={(s0,XZ0)}
δ(s0,1,X)={(s0,XX)}
δ(s0,0,X)={(s1,X)}
δ(s0, ε,X)={(s0, ε)}
δ(s1,1,X)={(s1, ε)}
δ(s1,0,Z0)={(s0, Z0)}
 Example 5
Formulate a Context Free Grammar to represent the language defined by the Pushdown Automata given below:
M=({s0,s1},{a,b},{Z0,a},δ,s0,Z0,ϕ) where δ is defined as

δ(s0,a,Z0)={(s0,aZ0)}

δ(s0,a,a)={(s0,aa)}

δ(s0,b,a)={(s1,ℇ)}

δ(s1,b,a)={(s1,ℇ)}

δ(s1,ℇ,Z0)={(s1,ℇ)}
 Example 6
Formulate a Context Free Grammar to represent the language defined by the Pushdown Automata given
below:

M=({q},{i,e},{Z},δ,q,Z) where δ is defined as

δ(q,i,Z)={(q,ZZ)}

δ(q,e,Z)={(q,ℇ)}
 Steps to convert a Grammar to Pushdown Automata
Given a CFG G, we construct a PDA that simulates the leftmost derivations of G

Let G=(V,T,Q,S) be a CFG. Construct the PDA P that accepts L(G) by empty stack as follows:

𝑃 = ( 𝑞 , 𝑇, 𝑉 ∪ 𝑇, 𝛿, 𝑞, 𝑆)
Note 1− The PDA will have only one state {q}.
Note 2 − The start symbol of CFG will be the bottom marker of the stack in the PDA.
Note 3 − All terminals and non-terminals of the CFG will be the stack symbols of the PDA and all the
terminals of the CFG will be the input symbols of the PDA.
Note 4 – The transitions of the PDA are defined as:

1. For each variable A,

𝛿 𝑞, 𝜀, 𝐴 = 𝑞, 𝛽 𝐴 → 𝛽 𝑖𝑠 𝑎 𝑝𝑟𝑜𝑑𝑢𝑐𝑡𝑖𝑜𝑛 𝑜𝑓 𝐺 }

2. For each terminal a, 𝛿 𝑞, 𝑎, 𝑎 = { 𝑞, 𝜀 }

 Example 1
Convert the given grammar to a PDA 𝛿 𝑞, 𝜀, 𝐸 = 𝑞, 𝐸 + 𝑇 , 𝑞, 𝑇
𝛿 𝑞, 𝜀, 𝑇 = 𝑞, 𝑇 ∗ 𝐹 , 𝑞, 𝐹
𝛿 𝑞, 𝜀, 𝐹 = 𝑞, (𝐸) , 𝑞, 𝐼
( ) 𝛿 𝑞, 𝜀, 𝐼 = 𝑞, 𝐼𝑎 , 𝑞, 𝐼𝑏 , 𝑞, 𝐼0 , 𝑞, 𝐼1 , 𝑞, 𝑎 , (𝑞, 𝑏)
𝛿 𝑞, +, + = {(𝑞, 𝜀)}
𝛿 𝑞, −, − = {(𝑞, 𝜀)}
𝛿 𝑞, (, ( = {(𝑞, 𝜀)}
𝑃 = ( 𝑞 , ∑, Γ, 𝛿, 𝑞0, 𝑍0) 𝛿 𝑞, ), ) = {(𝑞, 𝜀)}
𝛿 𝑞, 𝑎, 𝑎 = {(𝑞, 𝜀)}
That is, 𝑃 = ( 𝑞 , +,∗, , , 𝑎, 𝑏, 0,1 , 𝛿 𝑞, 𝑏, 𝑏 = {(𝑞, 𝜀)}
𝐸, 𝑇, 𝐹, 𝐼, +,∗, , , 𝑎, 𝑏, 0,1 , 𝛿, 𝑞, 𝑆)
𝛿 𝑞, 0,0 = {(𝑞, 𝜀)}
𝛿 𝑞, 1,1 = {(𝑞, 𝜀)}
 Example 2
Convert the given grammar to a PDA 𝛿 𝑞, 𝜀, 𝑆 = 𝑞, 𝐴𝐵
𝛿 𝑞, 𝜀, 𝐴 = 𝑞, 𝑎𝐴𝑏 , 𝑞, 𝜀
𝛿 𝑞, 𝜀, 𝐵 = 𝑞, 𝑐𝐵𝑑 , 𝑞, 𝜀
𝛿 𝑞, 𝑎, 𝑎 = {(𝑞, 𝜀)}
𝛿 𝑞, 𝑏, 𝑏 = {(𝑞, 𝜀)}
𝛿 𝑞, 𝑐, 𝑐 = {(𝑞, 𝜀)}

𝑃 = ( 𝑞 , ∑, Γ, 𝛿, 𝑞0, 𝑍0) 𝛿 𝑞, 𝑑, 𝑑 = {(𝑞, 𝜀)}

That is, 𝑃 = ( 𝑞 , 𝑎, 𝑏, 𝑐, 𝑑 , 𝑆, 𝐴, 𝐵, 𝑎, 𝑏, 𝑐, 𝑑 ,
𝛿, 𝑞, 𝑆)
 Example 3 Sample Input:
01010
Convert the given grammar to a PDA
Leftmost Derivation:
S ⇒ 0S0
⇒ 01S10
⇒ 01010
Simulation of the PDA:
(q, 01010, S) ⊢ (q, 01010, 0S0 )
𝑃 = ( 𝑞 , ∑, Γ, 𝛿, 𝑞0, 𝑍0) ⊢ (q, 1010, S0 )
⊢ (q, 1010, 1S10 )
⊢ (q, 010, S10 )
⊢ (q, 010, 010 )
𝛿 𝑞, 𝜀, 𝑆 = 𝑞, 0𝑆1 , 𝑞, 1𝑆1 , 𝑞, 0 , 𝑞, 1 , (𝑞, 𝜀) ⊢ (q, 10, 10 )
𝛿 𝑞, 0,0 = {(𝑞, 𝜀)} ⊢ (q, 0, 0 )
𝛿 𝑞, 1,1 = {(𝑞, 𝜀)} ⊢ (q, ε, ε )
PUMPINGLEMMAFORREGULARLANGUAGES

Pumping Lemma

• Let N be a regular language. Then there exists a constant n such that for every string w in L such that
|w|≥n, we can break w into three strings w=xyz such that

1. y ≠ ε

2. |xy| ≤ n

3. xykz ∈ L for all k≥0 (Repeating y any number of times or deleting y keeps the resulting string in
the same language)
PUMPINGLEMMAFOR CONTEXT FREE LANGUAGES

Pumping Lemma

• Let L be a context free language. Then there exists a constant n such that if 𝑧 is any string in L
such that |𝑧| ≥ 𝑛, then we can write 𝑧 = 𝑢𝑣𝑤𝑥𝑦 subject to the following conditions

1. 𝑣𝑥 ≠ 𝜀
2. |𝑣𝑤𝑥| ≤ 𝑛
3. 𝑢𝑣𝑖𝑤𝑥𝑖𝑦 ∈ 𝐿 for all 𝑖 ≥ 0 (That is, the two strings 𝑣 and 𝑥 may be pumped any number of
times, including 0, and the resulting string will still be a member of L)
 case (i) vwx has no 2’s
PUMPINGLEMMA– Example 1
Therefore, v and x consists of only 0’s and 1’s
Show that the language 𝑳 = {𝟎𝒏𝟏𝒏𝟐𝒏|𝒏 ≥ 𝟏} is
not context free Put 𝑖 = 0 in 𝑢𝑣𝑖𝑤𝑥𝑖𝑦. We get the string 𝑢𝑤𝑦.

The string 𝑢𝑤𝑦 will have n number of 2’s but

Assume that the given language is context free
fewer than n 0’s and 1’s.
Let us take the string 𝒛 = 𝟎𝒏𝟏𝒏𝟐𝒏 where n is the
Therefore, 𝑢𝑤𝑦 ∉ 𝐿 which is a contradiction
constant of pumping lemma.
case (ii) vwx has no 0’s
By pumping lemma, we can write 𝒛 = 𝟎𝒏𝟏𝒏𝟐𝒏 =
𝒖𝒗𝒘𝒙𝒚 such that Therefore, v and x consists of only 1’s and 2’s

Put 𝑖 = 0 in 𝑢𝑣𝑖𝑤𝑥𝑖𝑦. We get the string 𝑢𝑤𝑦.

1. 𝑣𝑥 ≠ 𝜀
The string uwy will have n number of 0’s but
2. |𝑣𝑤𝑥| ≤ 𝑛
fewer than n 1’s and 2’s.
3. 𝑢𝑣𝑖𝑤𝑥𝑖𝑦 ∈ 𝐿 for all 𝑖 ≥ 0 Therefore, 𝑢𝑤𝑦 ∉ 𝐿 which is a contradiction
The string 𝑣𝑤𝑥 cannot have all the three In both the cases, we arrive at a contradiction. Hence,
symbols 0’s, 1’s and 2’s because |𝑣𝑤𝑥| ≤ 𝑛
the given language is not context free
 case (i) vwx consists of only one symbol For
PUMPINGLEMMA– Example 2
example, assume vwx consists of only 0’s Put 𝑖
Show that the language = 0 in 𝑢𝑣𝑖𝑤𝑥𝑖𝑦. We get the string 𝑢𝑤𝑦.
𝑳 = {𝟎𝒊𝟏𝒋𝟐𝒊𝟑𝒋|𝒊 ≥ 𝟏, 𝒋 ≥ 𝟏} is not context free The string 𝑢𝑤𝑦 will have n number of 1’s, 2’s and
3’s but fewer than n 0’s.
Assume that the given language is context free
Therefore, the number of 0’s and 2’s do not match.
Let us take the string 𝒛 = 𝟎𝒏𝟏𝒏𝟐𝒏𝟑𝒏 where n is Therefore, 𝑢𝑤𝑦 ∉ 𝐿 which is a contradiction
the constant of pumping lemma.
By pumping lemma, we can write case (ii) vwx has two symbols

𝒛 = 𝟎𝒏𝟏𝒏𝟐𝒏𝟑𝒏 = 𝒖𝒗𝒘𝒙𝒚 such that For example, assume vwx has only 0’s and 1’s
Put 𝑖 = 0 in 𝑢𝑣𝑖𝑤𝑥𝑖𝑦. We get the string 𝑢𝑤𝑦.
1. 𝑣𝑥 ≠ 𝜀
The string uwy will have n number of 2’s and 3’s
2. |𝑣𝑤𝑥| ≤ 𝑛 but fewer than n 0’s and 1’s.

3. 𝑢𝑣𝑖𝑤𝑥𝑖𝑦 ∈ 𝐿 for all 𝑖 ≥ 0 The number of 0’s and 2’s will not match and the no
of 1’s and 3’s will not match
The string 𝑣𝑤𝑥 cannot have all the symbols 0’s, Therefore, 𝑢𝑤𝑦 ∉ 𝐿 which is a contradiction
1’s, 2’s and 3’s because |𝑣𝑤𝑥| ≤ 𝑛
In both the cases, we arrive at a contradiction. Hence,
It can have at most two symbols the given language is not context free
 case (i) vwx has no c’s
PUMPINGLEMMA– Example 3
𝒂𝒊𝒃𝒋𝒄𝒌 𝒊 < 𝒋 < 𝒌} is Therefore, v and x consists of only a’s and b’s
Show that the language 𝑳 =
not context free Put 𝑖 = 3 in 𝑢𝑣𝑖𝑤𝑥𝑖𝑦. We get the string 𝑢𝑣3𝑤𝑥3𝑦.

Assume that the given language is context free The string 𝑢𝑣3𝑤𝑥3𝑦 will have at least (n+2) a’s and
Let us take the string 𝒛 = 𝒂𝒏𝒃𝒏+𝟏𝒄𝒏+𝟐 where n is the b’s, which is not less than the number of c’s
constant of pumping lemma. Therefore,𝑢𝑣3𝑤𝑥3𝑦 ∉ 𝐿 which is a contradiction case
By pumping lemma, we can write (ii) vwx has no a’s
𝒛 = 𝒂𝒏𝒃𝒏+𝟏𝒄𝒏+𝟐 = 𝒖𝒗𝒘𝒙𝒚 such that Therefore, v and x consists of only b’s and c’s
1. 𝑣𝑥 ≠ 𝜀 Put 𝑖 = 0 in 𝑢𝑣𝑖𝑤𝑥𝑖𝑦. We get the string 𝑢𝑤𝑦.
2. |𝑣𝑤𝑥| ≤ 𝑛 The string 𝑢𝑤𝑦 will have some b’s and c’s missing.
3. 𝑢𝑣𝑖𝑤𝑥𝑖𝑦 ∈ 𝐿 for all 𝑖 ≥ 0 Therefore, 𝒂𝒊𝒃𝒋𝒄𝒌 | 𝒊 < 𝒋 < 𝒌 is not satisfied and
The string 𝑣𝑤𝑥 cannot have all the three symbols 𝑢𝑤𝑦 ∉ 𝐿 which is a contradiction
a’s, b’s and c’s because |𝑣𝑤𝑥| ≤ 𝑛
In both the cases, we arrive at a contradiction.
𝑣𝑤𝑥 can have at most twos symbols
Hence, the given language is not context free
PUMPINGLEMMA– Example 4
Show that the language 𝑳 = {𝒂𝒑|𝒑 𝒊𝒔 𝒑𝒓𝒊𝒎𝒆} is
not context free

Assume that the given language is context free

Let us take the string 𝒛 = 𝒂𝒑 where p is prime

and p>n where n is the constant of pumping
lemma.

By pumping lemma, we can write

𝒛 = 𝒂𝒑 = 𝒖𝒗𝒘𝒙𝒚 such that

1. 𝑣𝑥 ≠ 𝜀
2. |𝑣𝑤𝑥| ≤ 𝑛

3. 𝑢𝑣𝑖𝑤𝑥𝑖𝑦 ∈ 𝐿 for all 𝑖 ≥ 0

Put i=0 in 𝑢𝑣𝑖𝑤𝑥𝑖𝑦 . We get the string 𝑢𝑤𝑦

By pumping lemma, 𝑢𝑤𝑦 ∈ 𝐿