dixita.kagathara@darshan.ac.in

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

1

Topics to be covered

• Why pushdown Automata?
• Definition: PDA
• Acceptance by PDA
• Design PDA
• CFG to PDA
• PDA to CFG
• Intersection and complement of CFL
• Pumping lemma for CFG

​

Unit – 4 : Pushdown Automata, CFL & NCFL

Darshan Institute of Engineering & Technology

2

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

2

Why Pushdown Automata?

Unit – 4 : Pushdown Automata, CFL & NCFL

Darshan Institute of Engineering & Technology

3

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

3

Why Pushdown Automata?

Not Possible??

a

b

Unit – 4 : Pushdown Automata, CFL & NCFL

Darshan Institute of Engineering & Technology

4

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

4

Pushdown Automata

• A pushdown Automata is essentially a finite Automata with a stack data structure.

​

​

​

​

​

​

​

• A PDA can write an unbounded no. of symbols on the stack and read these symbols later.
• Writing a symbol on to the stack is called “PUSH” operation.
• Removing a symbol off the stack is called “POP” operation.

​

Finite Stack Control

Input

Accept | Reject

Stack

Unit – 4 : Pushdown Automata, CFL & NCFL

Darshan Institute of Engineering & Technology

5

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

5

Definition of PDA

Unit – 4 : Pushdown Automata, CFL & NCFL

Darshan Institute of Engineering & Technology

6

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

6

Acceptance by PDA

Unit – 4 : Pushdown Automata, CFL & NCFL

Darshan Institute of Engineering & Technology

7

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

7

Deterministic PDA

Unit – 4 : Pushdown Automata, CFL & NCFL

Darshan Institute of Engineering & Technology

8

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

8

Applications of PDA

• A pushdown automata is a way to implement a context free grammar.
• PDA is used in parser design for syntactic analysis.

Unit – 4 : Pushdown Automata, CFL & NCFL

Darshan Institute of Engineering & Technology

9

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

9

Design DPDA for L={aⁿbⁿ|a,b ∈ Ʃ, n≥0}

aⁿbⁿ

If n=3 then

a³b³

= a a a b b b

Unit – 4 : Pushdown Automata, CFL & NCFL

Darshan Institute of Engineering & Technology

10

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

10

How to Represent PDA?

a, z₀|az₀

a, a | aa

b, a | ^

Input symbol, stack symbol | PUSH/POP

FIRST 2 SYMBOLS OF THE STACK

^

Unit – 4 : Pushdown Automata, CFL & NCFL

Darshan Institute of Engineering & Technology

11

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

11

Design DPDA for L={aⁿbⁿ|a,b ∈ Ʃ, n≥0}

a, z₀|az₀

^,z₀ | z₀

a, a | aa

b, a | ^

b, a | ^

^,z₀ | z₀

Unit – 4 : Pushdown Automata, CFL & NCFL

Darshan Institute of Engineering & Technology

12

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

12

Design DPDA for same no. of a’s & b’s.

a, z₀|az₀

a, a | aa

b, z₀|bz₀

b, b | bb

a, b|^

b, a|^

^,z₀ | z₀

Unit – 4 : Pushdown Automata, CFL & NCFL

Darshan Institute of Engineering & Technology

13

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

13

Design PDA for {aⁿb^n+m c^m | n,m>=1}

aⁿ b^n+m c^m

​

= aⁿ bⁿ b^m c^m

​

If n=2 and m=3 then

​

= a² b² b³ c³

​

= aa bb bbb ccc

​

Unit – 4 : Pushdown Automata, CFL & NCFL

Darshan Institute of Engineering & Technology

14

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

14

Design PDA for {aⁿb^n+m c^m | n,m>=1}

a, a| aa

a, z₀| az₀

b, a| ^

b, a| ^

b, z₀| bz₀

b, b| bb

Unit – 4 : Pushdown Automata, CFL & NCFL

Darshan Institute of Engineering & Technology

15

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

15

Design PDA for {aⁿb^n+m c^m | n,m>=1}

c, b| ^

c, b| ^

^, z₀| z₀

Unit – 4 : Pushdown Automata, CFL & NCFL

Darshan Institute of Engineering & Technology

16

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

16

Exercise: Design PDA

1. Design PDA for aⁿbⁿc^md^m , n,m>=1
2. Design PDA for aⁿb^mc^mdⁿ , n,m>=1
3. Design PDA for a^n+mbⁿc^m , n,m>=1

​

​

Unit – 4 : Pushdown Automata, CFL & NCFL

Darshan Institute of Engineering & Technology

17

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

17

Design PDA for palindrome with middle symbol c.

• Design a PDA for following CFG.

S🡪aSa/bSb/c

• Design PDA for L={xcx^r/x∈{a,b}*}. The string in L are odd length palindromes over {a,b}
• Strings accepted in the language are:
• aba c aba
• aaa c aaa
• bab c bab
• ab c ba

​

Unit – 4 : Pushdown Automata, CFL & NCFL

Darshan Institute of Engineering & Technology

18

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

18

Design PDA for palindrome with middle symbol c.

a b a c a b a

Unit – 4 : Pushdown Automata, CFL & NCFL

Darshan Institute of Engineering & Technology

19

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

19

Design PDA for palindrome with middle symbol c.

a, z₀|az₀

a, a | aa

b, z₀|bz₀

b, b | bb

b, a | ba

a, b | ab

Unit – 4 : Pushdown Automata, CFL & NCFL

Darshan Institute of Engineering & Technology

20

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

20

Design PDA for palindrome with middle symbol c.

c,b | b

c,a | a

c,z₀ | z₀

a, z₀|az₀

a, a | aa

b, z₀|bz₀

b, b | bb

b, a | ba

a, b | ab

Unit – 4 : Pushdown Automata, CFL & NCFL

Darshan Institute of Engineering & Technology

21

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

21

Design PDA for palindrome with middle symbol c.

b, b | ^

a, a | ^

^,z₀ | z₀

c,b | b

c,a | a

c,z₀ | z₀

a, z₀|az₀

a, a | aa

b, z₀|bz₀

b, b | bb

b, a | ba

a, b | ab

Unit – 4 : Pushdown Automata, CFL & NCFL

Darshan Institute of Engineering & Technology

22

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

22

String Tracing

b, b | ^

a, a | ^

^,z₀ | z₀

c,b | b

c,a | a

c,z₀ | z₀

a, z₀|az₀

a, a | aa

b, z₀|bz₀

b, b | bb

b, a | ba

a, b | ab

Unit – 4 : Pushdown Automata, CFL & NCFL

Darshan Institute of Engineering & Technology

23

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

23

Exercise

Trace the following string:

1. bcb
2. ab
3. acaa

Unit – 4 : Pushdown Automata, CFL & NCFL

Darshan Institute of Engineering & Technology

24

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

24

Design PDA for {aⁱb^jc^k | i,j,k>=1 & j=i or j=k}

a, a| aa

a, z₀| az₀

b, a| ^

b, a| ^

c, z₀| z₀

c, z₀| z₀

Unit – 4 : Pushdown Automata, CFL & NCFL

Darshan Institute of Engineering & Technology

25

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

25

Design PDA for {aⁱb^jc^k | i,j,k>=1 & j=i or j=k}

^, z₀| z₀

a, z₀| z₀

a, z₀| z₀

b, b| bb

b,z₀| bz₀

c, b| ^

c, b| ^

a, a| aa

a, z₀| az₀

b, a| ^

b, a| ^

c, z₀| z₀

c, z₀| z₀

Unit – 4 : Pushdown Automata, CFL & NCFL

Darshan Institute of Engineering & Technology

26

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

26

Design PDA for {aⁱb^jc^k | i,j,k>=1 & j=i or j=k}

^, z₀| z₀

a, z₀| z₀

a, z₀| z₀

b, b| bb

b,z₀| bz₀

c, b| ^

c, b| ^

^, z₀| z₀

J=

j=i

J=

j=k

i=j

Unit – 4 : Pushdown Automata, CFL & NCFL

Darshan Institute of Engineering & Technology

27

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

27

Design DPDA for L={aⁿb²ⁿ|a,b ∈ Ʃ, n≥0}

aⁿb²ⁿ

If n=1 then

a¹b²

= a b b

Unit – 4 : Pushdown Automata, CFL & NCFL

Darshan Institute of Engineering & Technology

28

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

28

Design DPDA for L={aⁿb²ⁿ|a,b ∈ Ʃ, n≥0}

a, z₀|aa

^,z₀ | z₀

a, a | aa

b, a | ^

b, a | ^

^,z₀ | z₀

Unit – 4 : Pushdown Automata, CFL & NCFL

Darshan Institute of Engineering & Technology

29

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

29

Design PDA for even odd length palindrome (Nondeterministic)

a, z₀|az₀

a, a | aa

b, z₀|bz₀

b, b | bb

b, a | ba

a, b | ab

b,a | a

a,b | b

a,a | a

b, z₀| z₀ z₀

a, z₀| z₀

b,b | b

Unit – 4 : Pushdown Automata, CFL & NCFL

Darshan Institute of Engineering & Technology

30

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

30

Design PDA for even odd length palindrome

^,b | b

^,a | a

^,z₀ | z₀

b,a | a

a,b | b

a,a | a

b,b | b

Unit – 4 : Pushdown Automata, CFL & NCFL

Darshan Institute of Engineering & Technology

31

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

31

Design PDA for even odd length palindrome

b, b | ^

a, a | ^

^,z₀ | z₀

Unit – 4 : Pushdown Automata, CFL & NCFL

Darshan Institute of Engineering & Technology

32

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

32

Design DPDA for grammar S🡪SS|[S]|{S}|˄

[, [|[[

[, { | [{

{, [ | {[

{, { | {{

[, z₀|[z₀

{, z₀|{z₀

Unit – 4 : Pushdown Automata, CFL & NCFL

Darshan Institute of Engineering & Technology

33

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

33

Design DPDA for grammar S🡪SS|[S]|{S}|˄

}, { | ^

], [ | ^

^,z₀ | z₀

{, { | {{

[, [|[[

[, { | [{

{, [ | {[

{, { | {{

[, z₀|[z₀

{, z₀|{z₀

Unit – 4 : Pushdown Automata, CFL & NCFL

Darshan Institute of Engineering & Technology

34

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

34

Design DPDA for grammar S🡪SS|[S]|{S}|˄

}, { | ^

], [ | ^

^,z₀ | z₀

[, [|[[

[, { | [{

{, [ | {[

{, { | {{

[, z₀|[z₀

{, z₀|{z₀

Unit – 4 : Pushdown Automata, CFL & NCFL

Darshan Institute of Engineering & Technology

35

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

35

Design PDA to accept string with more a’s than b’s.

a, a | aa

a, z₀|az₀

b, b | bb

^, a | a

b, a | ^

a, b | ^

b, z₀| bz₀

Unit – 4 : Pushdown Automata, CFL & NCFL

Darshan Institute of Engineering & Technology

36

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

36

Design PDA for twice many a’s as b’s

a, z₀| z₀

b, z₀|yz₀

b, y|yy

a, z₀| xz₀

Unit – 4 : Pushdown Automata, CFL & NCFL

Darshan Institute of Engineering & Technology

37

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

37

Design PDA for twice many a’s as b’s

a, z₀| z₀

a, x| x

b, y|yy

b, z₀|yz₀

b, x|^

b, z₀|yz₀

b, y|yy

a, z₀| xz₀

a, x| xx

Unit – 4 : Pushdown Automata, CFL & NCFL

Darshan Institute of Engineering & Technology

38

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

38

Design PDA for twice many a’s as b’s

a, z₀| z₀

a, x| x

a, y| y

b, a| y

b, y|yy

b, z₀|yz₀

b, x|^

b, z₀|yz₀

b, y|yy

a, z₀| xz₀

a, x| xx

a, y| ^

b, x| ^

Unit – 4 : Pushdown Automata, CFL & NCFL

Darshan Institute of Engineering & Technology

39

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

39

CFG to PDA

Unit – 4 : Pushdown Automata, CFL & NCFL

Darshan Institute of Engineering & Technology

40

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

40

Steps to convert CFG to PDA

• From given CFG G=(V,Σ,S,P), we can construct a PDA.
• The PDA’s δ is given by :
1. For each non terminal A, include a transition

Include a transition δ(q, 𝜖, A)🡪{(q, α)|A🡪 α is a production in G}

• For each terminal a, include a transition

Include a transition δ(q, a, a)🡪{(q, 𝜖)}

​

Unit – 4 : Pushdown Automata, CFL & NCFL

Darshan Institute of Engineering & Technology

41

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

41

Example: CFG to PDA

Find PDA for following grammar:

S🡪0S1 | 00 | 11

The equivalent PDA, M is given by:

δ(q, 𝜖, S)= {(q, 0S1), (q, 00), (q,11)}

​

δ(q, 0, 0)={(q, 𝜖)}

δ(q, 1, 1)={(q, 𝜖)}

​

δ(q, 𝜖, A)🡪{(q, α)|A🡪 α is a production in G

δ(q, a, a)🡪{(q, 𝜖)}

Non Terminal

Terminal

Unit – 4 : Pushdown Automata, CFL & NCFL

Darshan Institute of Engineering & Technology

42

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

42

Exercise: CFG to PDA

1. Given a CFG , G =( {S,A,B},{0,1},P,S) with P as follows:

S 🡪 0B| 1A

A 🡪 0S|1AA|0

B 🡪 1S| 0BB | 1

2. Design a PDA M corresponding to CFG:

I 🡪 a | b | Ia | Ib | I0 | I1

E 🡪 I | E * E | E + E | (E)

Unit – 4 : Pushdown Automata, CFL & NCFL

Darshan Institute of Engineering & Technology

43

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

43

PDA to CFG

Unit – 4 : Pushdown Automata, CFL & NCFL

Darshan Institute of Engineering & Technology

44

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

44

Rule to convert PDA to CFG

1. Add the following production for the start symbol S.

S🡪[q₀ z q_i]

q₀ initial state

z initial stake symbol

qi ∈ Q

2. For each transition of the form δ( q_i, a, B) 🡪(q_j, C)

where q_i, q_j ∈ Q

a ∈ (Ʃ U ^)

B, C ∈ (┌ U ^)

Then for each q∈ Q, add the production

[q_i, B, q]🡪a[q_j, C, q]

Unit – 4 : Pushdown Automata, CFL & NCFL

Darshan Institute of Engineering & Technology

45

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

45

Rule to convert PDA to CFG

3. For transition of the form δ( q_i, a, B) 🡪(q_j,C₁C₂)

where q_i, q_j ∈ Q

a ∈ (Ʃ U ^)

B, C₁, C₂ ∈ (┌ U ^)

Then for each p1, p2 ∈ Q, add the production

[q_i, B, p₁]🡪a[q_j C₁ p₂] [p₂ C₂ p₁]

Unit – 4 : Pushdown Automata, CFL & NCFL

Darshan Institute of Engineering & Technology

46

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

46

Example: PDA to CFG

​

​

​

​

​

​

Step 1: Add the production for the start symbol

S🡪[q z q]

S🡪[q z p]

​

S🡪[q₀ z q_i]

q₀ initial state

z initial stack symbol

qi ∈ Q (all state)

Unit – 4 : Pushdown Automata, CFL & NCFL

Darshan Institute of Engineering & Technology

47

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

47

Example: PDA to CFG

​

​

​

​

​

​

Step 2: Add production for the δ( q, 1, z) 🡪(q ,xz)

[q z q]🡪1[q x q][q z q]

[q z q]🡪1[q x p][p z q]

[q z p]🡪1[q x q][q z p]

[q z p]🡪1[q x p][p z p]

​

[q_i, B, p₁]🡪a[q_j C₁ p₂] [p₂ C₂ p₁]

For transition of the form δ( q_i, a, B) 🡪(q_j,C₁C₂)

where q_i, q_j ∈ Q

a ∈ (Ʃ U ^)

B, C₁, C₂ ∈ (┌ U ^)

Then for each p1, p2 ∈ Q, add the production

[q_i, B, p₁]🡪a[q_j C₁ p₂] [p₂ C₂ p₁]

δ( q_i, a, B) 🡪(q_j,C₁C₂)

P1=q p2=q

P1=q p2=p

P1=p p2=q

P1=p p2=p

​

Unit – 4 : Pushdown Automata, CFL & NCFL

Darshan Institute of Engineering & Technology

48

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

48

Example: PDA to CFG

​

​

​

​

​

​

Step 3: Add production for the δ( q, 1, x) 🡪(q ,xx)

[q x q]🡪1[q x q][q x q]

[q x q]🡪1[q x p][p x q]

[q x p]🡪1[q x q][q x p]

[q x p]🡪1[q x p][p x p]

​

Unit – 4 : Pushdown Automata, CFL & NCFL

Darshan Institute of Engineering & Technology

49

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

49

Example: PDA to CFG

​

​

​

​

​

​

Step 4: Add the production for δ( q, ^, x) 🡪(q ,^)

[q x q]🡪^

​

state

stack

New state

input

Unit – 4 : Pushdown Automata, CFL & NCFL

Darshan Institute of Engineering & Technology

50

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

50

Example: PDA to CFG

​

​

​

​

​

​

Step 5: Add the production for δ( q, 0, x) 🡪(p ,x)

[q x q]🡪0 [p x q]

[q x p]🡪0 [p x p]

​

Each transition of the form δ( q_i, a, B) 🡪(q_j, C)

where q_i, q_j ∈ Q

a ∈ (Ʃ U ^)

B, C ∈ (┌ U ^)

Then for each q∈ Q, add the production

[q_i, B, q]🡪a[q_j, C, q]

δ( q_i, a, B) 🡪(q_j, C)

[q_i, B, q]🡪a[q_j, C, q]

Unit – 4 : Pushdown Automata, CFL & NCFL

Darshan Institute of Engineering & Technology

51

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

51

Example: PDA to CFG

​

​

​

​

​

​

Step 6: Add the production for δ( p, 1, x) 🡪(p ,^)

[p x p]🡪1

​

Unit – 4 : Pushdown Automata, CFL & NCFL

Darshan Institute of Engineering & Technology

52

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

52

Example: PDA to CFG

​

​

​

​

​

​

Step 7: Add the production for δ( p, 0, z) 🡪(q ,z)

[p z q]🡪0 [q z q]

[p z p]🡪0 [q z p]

​

δ( q_i, a, B) 🡪(q_j, C)

[q_i, B, q]🡪a[q_j, C, q]

Unit – 4 : Pushdown Automata, CFL & NCFL

Darshan Institute of Engineering & Technology

53

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

53

Example: PDA to CFG

Step 8: Renaming variable name

The set of production can be written as:

S🡪A|B

A🡪1EA|1FC

B🡪1EB|1FD

E🡪1EE|1FG

F🡪1EF|1FH

E🡪^

E🡪0G

F🡪0H

H🡪1

C🡪0A

D🡪0B

​

​

​

​

​

​

​

​

Step1:

S🡪[q z q]

S🡪[q z p]

Unit – 4 : Pushdown Automata, CFL & NCFL

Darshan Institute of Engineering & Technology

54

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

54

Example: PDA to CFG

Step 9: simplification of grammar

Symbol G is not available on left side of

grammar so, it can be eliminated.

S🡪A|B

A🡪1EA|1FC

B🡪1EB|1FD

E🡪1EE|^

F🡪1EF|1FH|0H

H🡪1

C🡪0A

D🡪0B

​

​

​

​

​

​

​

​

Unit – 4 : Pushdown Automata, CFL & NCFL

Darshan Institute of Engineering & Technology

55

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

55

Intersection and complement of CFL (Non CFL)

Unit – 4 : Pushdown Automata, CFL & NCFL

Darshan Institute of Engineering & Technology

56

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

56

Intersection and complement of CFL

• Theorem:-There are CFLs L1 and L2 so that L1∩ L2 is not a CFL, and there is a CFL L so that L’ is not a CFL.
• We observed that

L= { aⁱb^jc^k| i < j and i < k }

• is not context-free. However, although no PDA can test both conditions i < j and i< k simultaneously, it is easy enough to build two PDAs that test the conditions separately. In other words, although the intersection L of the two languages

L₁ = {a ⁱ b^jc^k | i < j}

and

L₂ = {aⁱb^jc^k | i < k}

• is not a CFL, both languages themselves are.

Unit – 4 : Pushdown Automata, CFL & NCFL

Darshan Institute of Engineering & Technology

57

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

57

Intersection and complement of CFL

• Another way to verify that L₁ is a CFL is to check it is generated by the grammar with productions

S🡪ABC A🡪aAb|˄ B🡪bB|b C🡪cC|˄

• Similarly, L₂is generated by the CFG with productions

S🡪AC A🡪aAc|B B🡪bB|˄ C🡪cC|c

• The second statement in the theorem follows from the first and the formula

L₁∩ L₂ =( L₁’U L₂’)’

• If complements of CFLs were always CFLs, then for any CFLs L₁ and L₂, the language L₁’and L₂’ would be CFLs, so would their union, and so would its complement. We know now that this is not the case.

​

Unit – 4 : Pushdown Automata, CFL & NCFL

Darshan Institute of Engineering & Technology

58

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

58

Pumping lemma for CFG

Unit – 4 : Pushdown Automata, CFL & NCFL

Darshan Institute of Engineering & Technology

59

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

59

Pumping lemma for CFG

• Suppose L is a context-free language. Then there is an integer n so that for every u ∈ L with |u| ≥ n, there are strings v, w, x, y, and z satisfying,

u = vwxyz

|wy| > 0

|wxy| ≤ n

for every m ≥ 0, vw^mxy^mz ∈ L

Unit – 4 : Pushdown Automata, CFL & NCFL

Darshan Institute of Engineering & Technology

60

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

60

End of Unit - 4

Unit – 4 : Pushdown Automata, CFL & NCFL

Darshan Institute of Engineering & Technology

61

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

61