Check for Regular language and Pumping lemma

1. If a language is finite, then it is always regular.

2. If a language is infinite, it may or may not be regular. If an infinite language has to be accepted by Finite Automata, there must be some type of loop.

for Infinite language, we use the Pumping lemma Test.

Pumping lemma Test: 

  1. It is a negative test. It means if a language is regular, it must satisfy Pumping lemma Test but if a language satisfied pumping lemma test it need not be regular always.
  2. It a language does not satisfy pumping lemma test, it can't be regular.
  3. Pumping lemma is used to prove some of the languages are not regular. 

Theory:-

If A is regular language, then A has a pumping length P such that, any string S

where |S|>= P can be divided into three parts S= XYZ such that following condition satisfied:-

1.)  |XY| <= P

2.)   XYiZ  ∈ A for every i>=0

3.)   |Y| > 0

To prove a language is not regular using Pumping lemma, please follow the following steps:

We use prove by contradiction method.

-->  Assume  A is regular.

-->  It has to have a pumping length P.

-->  All string longer than P can be pumped.

-->  Now find a string S in A such that |S| >= P.

-->  Then consider all the possible way that S can be divided into X,Y,Z.

-->  Show that XYiZ ∉A.

--> Show that none of the three property can't be satisfied by any combination XYZ.

Example:

1. L = an b / n>1

Solution:

let us assume L is Regular ,then it has to have a pumping length P. let assume

P =7

S= aPbP =  a7b= aaaaaaabbbbbbb  ∈ L

Divide  the string S in three parts 

                 aa     aaaa     abbbbbbb   

                  X          Y                 Z

and |XY| <= 7

Now, XYiZ let assume i=2

Now if you pump Y , following string will be formed

       aaaaaaaaaaabbbbbbb ∉ L

But earlier we assumed L as regular, This contradicts our assumption, So  L is not Regular.

 

Contributor's Info

Created:
0Comment