0
State and prove pumping lemma for context free languages.

Mumbai university > Comp > SEM 4 > TCS

Marks: 10M

Year: Dec 2015

0  upvotes
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

0  upvotes
Please log in to add an answer.

Next up

Read More Questions

If you are looking for answer to specific questions, you can search them here. We'll find the best answer for you.

Search

Study Full Subject

If you are looking for good study material, you can checkout our subjects. Hundreds of important topics are covered in them.

Know More