Question

L = {a r b s | r, s ≥ 0 and s = r 2}. Show that L is not regular using the pumping lemma

Answer 1

Here r, s 0

In order to achieve this language we need to keep count of how many 'a' do we have then only we can count the number of 'b', but we know that final state machine cannot keep count of anything, so this cannot be designed using final state machines and all languages that cannot be designed using final state machines are said to be non-regular.

LET US PROVE THIS USING PUMPING LEMMA

CONDITIONS MUST BE TRUE TO PROVE REGULAR

1. for every i0

2. |Y|>0

3.

Assume that language L is regular

let pumping length = P

therefore, String =

let p = 3

therefore string is = aaabbbbbbbbb

let's divide the string into three parts X, Y and Z

(I've divided the string using different colours)

and then we will check whether or not by considering all ways to divide string into X, Y and Z, if it will not follow this then due to contradiction, the language will not be regular.

to check this we are going to assume i =2.

case 1: The Y is in the 'a' part a a abbbbbbbbb	=> a aa abbbbbbbbb we know that , according to that, , but here a=4 and b = 9 therefore, , this does not lie in our language
case 2: The Y is in the 'b' part aaabb bbbb bbb	=> aaabb bbbbbbbb bbb we know that , according to that, , but here a=3 and b = 13 therefore, , this also does not lie in our language
case 3: The Y is in the 'a' and 'b' part aa abbb bbbbbb	=> aa abbbabbb bbbbbb this is not following the pattern therefore this also does not lie in our language

So we have showed that none of these can satisfy all the 3 pumping conditions at the same time

let us consider the third condition

In case 1, |XY| = 2 (i.e length of XY is 2) and p is 3, therefore |XY| < P (CONDITION SATISFIED)

In case 2, |XY| = 9, and p is 3, therefore |XY| > P (CONDITION NOT SATISFIED)

In case 3, |XY| = 6, and p is 3, therefore |XY| > P (CONDITION NOT SATISFIED)

SO LANGUAGE L CANNOT BE PUMPED, AS IT CONTRADICTED OUR ASSUMPTION THAT LANGUAGE L IS REGULAR.

Hence, we have proved that language L is not regular using pumping lemma.