0
State and prove pumping lemma for context free languages.

Mumbai university > Comp > SEM 4 > TCS

Marks: 10M

Year: Dec 2015

0

Step 1 :

Assume Language L is a regular language.

Step 2: Example

• n=1 ;∣ abc ∣ = 3

• n=2 ; ∣ aabbcc ∣ = 6

• n=3 ;∣ aaabbbccc ∣ = 9

Step 3:

• Let L be a regular language and z be word in L such that,

• | z | = n + n + n ≥ n

∣ z ∣ = 3n ≥ n

• z = uvw , where ∣ u v∣ ≥ n and 1 ≤ ∣ v ∣ ≤ n such that for every string generated by ∣ uviw ∣,

i ≥ 0 should exist in L.

i = 2;∣ uv2w ∣ = ∣ uvw ∣ + ∣ v ∣

1 ≤ ∣ v ∣ ≤ n

• Adding all side by ∣ uvw ∣,

1 + ∣ uvw ∣ ≤ ∣ uvw ∣ + ∣ v ∣ ≤ n + ∣ uvw ∣

1 + ∣ z ∣ ≤ ∣ uv2w ∣ ≤ n + ∣ z ∣

1 + 3n ≤ ∣ uv2w ∣ ≤ n + 3n

3n ≥ ∣ uv2w ∣ ≥ 4n + 1

n = 1 ; 3 ≥ ∣ uv2w ∣ ≥ 5n = 1;

⇓⇓

$4$

in between 3 and 5 , the value 4 comes and

n = 2; 6 ≥ ∣ uv2w ∣ ≥ 9

⇓⇓

7,8

in between 6 and 9 , the value 7 and 8 comes.

Step 4:

Since string length 4, 7, 8 doesn't exist in language L

∴ ∴ Our assumption is wrong.

∴ ∴L is not regular language