FOR FREE YEAR SOLVED

Example:

Q. $\mathbf{L}\mathbf{ }\mathbf{=}\mathbf{ }\mathbf{\{}{\mathbf{a}}^{{\mathbf{i}}^{\mathbf{2}}}\mathbf{,}\mathbf{ }\mathbf{i}\mathbf{ }\mathbf{\ge }\mathbf{ }\mathbf{1}\mathbf{\}}$ 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.

Now decompose it by xyz with two conditions.

Here,

Now we are going to check,

This time we check for ${\mathbf{xy}}^{\mathbf{2}}\mathbf{z}\mathbf{ }\mathbf{\in }\mathbf{ }\mathbf{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,

Now we can add (n + 1) on left-hand side of $\mathbf{\left|}{\mathbf{xy}}^{\mathbf{2}}\mathbf{z}\mathbf{\right|}$ then we can say,

Now looks at the given language $\mathbf{L}\mathbf{ }\mathbf{=}\mathbf{ }\mathbf{\{}{\mathbf{a}}^{{\mathbf{i}}^{\mathbf{2}}}\mathbf{,}\mathbf{ }\mathbf{i}\mathbf{ }\mathbf{\ge }\mathbf{ }\mathbf{1}\mathbf{\}}$ from language it is clear that every string ω  which belongs to the language is a length of ${\mathbf{i}}^{\mathbf{2}}$ (perfect square). 

So if $\mathbf{\omega }\mathbf{ }\mathbf{=}\mathbf{ }{\mathbf{a}}^{{\mathbf{n}}^{\mathbf{2}}}$ then next string $\mathbf{\omega }\mathbf{ }\mathbf{=}\mathbf{ }{\mathbf{a}}^{{\mathbf{(}\mathbf{n}\mathbf{+}\mathbf{1}\mathbf{)}}^{\mathbf{2}}}$ here ${\mathbf{n}}^{\mathbf{2}}$ and ${\mathbf{(}\mathbf{n}\mathbf{ }\mathbf{+}\mathbf{ }\mathbf{1}\mathbf{)}}^{\mathbf{2}}$ is perfect square.

But length of string ${\mathbf{xy}}^{\mathbf{2}}\mathbf{z}$  is between ${\mathbf{n}}^{\mathbf{2}}$ and ${\mathbf{(}\mathbf{n}\mathbf{ }\mathbf{+}\mathbf{ }\mathbf{1}\mathbf{)}}^{\mathbf{2}}$  i.e. ${\mathbf{n}}^{\mathbf{2}}\mathbf{ }\mathbf{<}\mathbf{ }\mathbf{\left|}{\mathbf{xy}}^{\mathbf{2}}\mathbf{z}\mathbf{\right|}\mathbf{ }\mathbf{<}\mathbf{ }{\mathbf{(}\mathbf{n}\mathbf{ }\mathbf{+}\mathbf{ }\mathbf{1}\mathbf{)}}^{\mathbf{2}}$.

So, it is clear that $\mathbf{\left|}{\mathbf{xy}}^{\mathbf{2}}\mathbf{z}\mathbf{\right|}$ is not perfect square because between two perfect square no perfect square is possible like here ${\mathbf{n}}^{\mathbf{2}}$ and ${\mathbf{(}\mathbf{n}\mathbf{ }\mathbf{+}\mathbf{ }\mathbf{1}\mathbf{)}}^{\mathbf{2}}$ are both perfect squares so,

Like  ${\mathbf{3}}^{\mathbf{2}}\mathbf{ }\mathbf{=}\mathbf{ }\mathbf{9}\mathbf{,}$  ${\mathbf{4}}^{\mathbf{2}}\mathbf{ }\mathbf{=}\mathbf{ }\mathbf{16}$ between 9 and 16 no perfect square is possible.

So,  ${\mathbf{xy}}^{\mathbf{2}}\mathbf{z}$ string violating pumping lemma, so,  $\mathbf{L}\mathbf{ }\mathbf{=}\mathbf{ }\mathbf{\{}{\mathbf{a}}^{{\mathbf{i}}^{\mathbf{2}}}\mathbf{,}\mathbf{ }\mathbf{i}\mathbf{ }\mathbf{\ge }\mathbf{ }\mathbf{1}\mathbf{\}}$ violet pumping lemma and it is not Regular Language.