Mumbai University > Computer Engineering > Sem 4 > Theoretical Computer Science

Marks: 10M

Year: Dec 2016

Pumping Lemma

Let L be a regular language and let Z be a word of L such that |z|>=n,

Where n is the minimum number of DFA states required for recognizing L, then we can write z=uvw

Where |uv|<=n and 1<=|v|<=n.

Such that all strings of the form

uv^iw for i>=0 would belong to L.

Proof:

Let L be a regular language

Let z=0^i 1^i |z|>=i

Where i is a P.L constant

Then as per P.L,

We write z=uvw

Where |uv|<=i and 1<=|v|<=i

Such that all strings of the form

uv^iw for i>=0 would belong to L.

i=2, | uv^2w |=|uvw|+|v|

1<=|v|<=i

Add |uvw| on all the sides

1+2i<=| uv^2w |<=i+2i

2i<| uv^2w |<3i+1

Now,

0^n 1^n

n=1 |01|=2 i=1

n=2 |0011|=4 2<| uv^2w |<4

Therefore, L cannot contains any string of length 3,

L is not regular