FOR FREE YEAR SOLVED

Example:

 

 

Q. L = {ai2, i  1} is not a regular language.

 

Solutions:

 

Initially, we always assume that it is regular language and the machine is DFA.

 

Let n is no. of state at DFA which accepts Language.

 

Satisfying

 

Now decompose it by xyz with two conditions.

 

 

Here,

 

Satisfying

 

Now we are going to check,

 

here we see xyz satisfy.

 

This time we check for xy2z  L .

 

 

So, we can say, 

 

 

Also | x | + | y | + | z | < | x | + 2| y | + | z | hence, | y | > 0 (true) or | y | ≥ 1 and | xy | ≤ n satisfy.

 

Now we can say,

 

 

| xy | ≤  n, | y | > 0 or | y | ≥ 1 then we can say | y | ≤ n because | xy | ≤  n.

 

Then we can say,

 

 It is also true.

  

 

Now we can add (n + 1) on left-hand side of |xy2z| then we can say,

 

 

Now looks at the given language L = {ai2, i  1} from language it is clear that every string ω  which belongs to the language is a length of i2 (perfect square)

 

So if ω = an2 then next string ω = a(n+1)2 here n2 and (n + 1)2 is perfect square.

 

But length of string xy2z  is between n2 and (n + 1)2  i.e. n2 < |xy2z| < (n + 1)2.

 

So, it is clear that |xy2z| is not perfect square because between two perfect square no perfect square is possible like here n2 and (n + 1)2 are both perfect squares so,

 

 

Like  32 = 9,  42 = 16 between 9 and 16 no perfect square is possible.

 

So,  xy2z string violating pumping lemma, so,  L = {ai2, i  1} violet pumping lemma and it is not Regular Language.