Question: State and prove pumping lemma for context free languages.
0

Mumbai university > Comp > SEM 4 > TCS

Marks: 10M

Year: Dec 2015

ADD COMMENTlink
modified 3.3 years ago  • written 3.3 years ago by gravatar for Pooja Joshi Pooja Joshi740
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

ADD COMMENTlink
written 3.3 years ago by gravatar for Pooja Joshi Pooja Joshi740
Please log in to add an answer.