Pumping Lemma For Regular Set | TOC

Pumping Lemma

Pumping means jump | loop

Pumping lemma for regular set is used to find whether a given language is regular or not .

If language is regular than finite automata of that language is possible otherwise not.

If language is regular than finite auotmata of that language is possible otherwise not.

Example: aⁿbⁿ | n≧1

^{Here first we check whether it is regular or not.}

^{For this we can not construct finite automata so this string is not regular.}

        aⁿbⁿ | n≧1

Suppose we take a string which is acceptable

        a a b b

Suppose x is string were 

        x ∈ L

than break x into three points.

        x= uvw

V^m  It shows how many times loop will execute.

 

suppose m=3 for above string then we get 

    (a aaa bb) ∉ L 

OR

suppose m=2 for above string than we get

    (aa abab bb) ∉ L 

Note : we can not take V as a Null.

    V ∉ ε

Note : 

If length of string is 1 than maximum state = 2

If length of string is 2 than maximum state = 3

If length of string is 3 than maximum state = 4

---

---

---

If length of string is ∞ than maximum state= Finite

*Because for  ∞ no finite automata will be constructed.

 

Theorem: State and proof pumping lemma.

Proof:

Statement for Pumping lemma for regular set.

Suppose L is a regular language there is an integer (N) so that for every x ∈ L

with |x|≤ N there are three string u,v,w.

So that x=uvw and 

Condition are:

    Condition 1: |uv|≤ N

    Condition 2: |v|>0

    Condition 3: For any m ≥0 , UV^m ∈ L

 

Consider a Automata

     M = (Q , Σ , δ , q₀ , F)

which accept L

and suppose that Q have N number of elements.

(here indexing start from 0 so there has N+1 states)

For any  x ∈ L with  |x|≥N

and x= a₁ , a₂ , a₃ ----- a_ny than

States are represented as 

q₀

q₁ =  δ(q₀,a₁) 

q₂ =  δ(q₀,a₁a₂) =  δ(q₁,a₂)

q₃ = δ(q₀,a₁a₂a₃) = δ(q₁,a₂a₃) = δ(q₂,a₃)

-----

-----

q_n = δ(q₀,a₁a₂a₃ --- , a_ny) 

since  y is include in x so we take y here

From this representation of state it is clear that some state exist twice.

Example:

In above figure for string a we take maximum 2 states in figure a.

But if 1=2 then , we merge these two state into single state in figure b.

    If q_i=q_i+p   where 0 ≤ i < i+p ≤ N

Note :

     i ≥ 0 means initial state.

     i < i+p means any state except initial state.

We will find out which two states are similar or equal.

than,

    δ(q₀,a₁a₂a₃ --- ,a_i)= q_i

    δ(q_i,a_i+1,a_i+2,.....,a_i+p)= q_i+p= q_i

    δ(a_i+p+1,a_i+p+2,.....,a_ny)= q_i+p= q_f ∈ F 

To simplify let

    a₁a₂ −−−− a_i = u

    a_i+1 a_i+2 −−−− a_i+p = v

    a_i+p+1 a_i+p+2 −−−− a_ny = w

Than transition diagram for finite automata is

Since  δ(q_i,v) = q_i  than 

         δ(q_i,v^m) = q_i 

where m ≥ 0

therefore it follow that

    δ^*(q₀ , uv^mw) = q_f

_where q_f ∈ F  and m ≥ 0

    and uv^mw ∈ L  Hence Proved

STEPS FOR PROVIDING A LANGUAGE NON REGULAR :

STEP 1: Assume L is regular and N is number of state of corresponding finite automata.

STEP 2: Choose a string x such as that

    |x| ≥ N

use pumping lemma to write

    x=uvw  such that

    |uv| ≤ 0

STEP 3: Find a suitable integer (i) such that

    u vⁱ w ∉ L this contradict our assumption hence N is non regular.