FOR FREE MATERIALS

Example:

Q. Prove $\mathbf{L}\mathbf{ }\mathbf{=}\mathbf{ }\mathbf{\{}{\mathbf{a}}^{\mathbf{n}}{\mathbf{b}}^{\mathbf{n}}\mathbf{ }\mathbf{|}\mathbf{ }\mathbf{n}\mathbf{ }\mathbf{\ge }\mathbf{ }\mathbf{0}\mathbf{\}}$ -- it is not regular by pumping lemma.

Solutions: 

Let us assume DFA of the above language has m state (still we know for this language DFA is not possible). 

Actually we assume  ${\mathbf{a}}^{\mathbf{n}}{\mathbf{b}}^{\mathbf{n}}\mathbf{ }\mathbf{|}\mathbf{ }\mathbf{n}\mathbf{ }\mathbf{\ge }\mathbf{ }\mathbf{0}$ a regular language with m state DFA.

Now we take a string of this given language and check pumping lemma.

Let $\mathbf{\omega }\mathbf{ }\mathbf{=}\mathbf{ }{\mathbf{a}}^{\mathbf{3}}{\mathbf{b}}^{\mathbf{3}}$ (aaabbb) |ω| = 6 so, |ω| ≥ m now we decompose it at xyz as 

Here ω ∊ L, |xy| = 4 so, |xy| ≤ m and y > 0 both are satisfied.

Here we want to prove it,

Now we check that all string that accepts pumping lemma is belongs to L or not:

Now check xz ∊ L satisfy because $\frac{\mathbf{aa}}{\mathbf{x}}\mathbf{ }\frac{\mathbf{bb}}{\mathbf{z}}$ it belongs to ${\mathbf{a}}^{\mathbf{n}}{\mathbf{b}}^{\mathbf{n}}\mathbf{ }\mathbf{\left(}\mathbf{L}\mathbf{\right)}$.

Also xyz ∊ L because  $\frac{\mathbf{aa}}{\mathbf{x}}\mathbf{ }\frac{\mathbf{ab}}{\mathbf{y}}\mathbf{ }\frac{\mathbf{bb}}{\mathbf{z}}$ also belongs to ${\mathbf{a}}^{\mathbf{n}}{\mathbf{b}}^{\mathbf{n}}\mathbf{ }\mathbf{\left(}\mathbf{L}\mathbf{\right)}$.

Another case ${\mathbf{xy}}^{\mathbf{2}}\mathbf{z}\mathbf{ }\mathbf{\in }\mathbf{L}$?

From the above string, it is clear that it is violating the pumping lemma. 

So,  $\mathbf{L}\mathbf{ }\mathbf{=}\mathbf{ }\mathbf{\{}{\mathbf{a}}^{\mathbf{n}}{\mathbf{b}}^{\mathbf{n}}\mathbf{ }\mathbf{|}\mathbf{ }\mathbf{n}\mathbf{ }\mathbf{\ge }\mathbf{ }\mathbf{0}\mathbf{\}}$ violet pumping lemma, so it is not Regular Language.

We can also prove this language by general way :

Let n number of states.

When we put i = 0 then it will be,

 If we put i = 2 then it will be,

So, ${\mathbf{a}}^{\mathbf{n}}{\mathbf{b}}^{\mathbf{n}}\mathbf{ }$violet pumping lemma so, it is not a Regular Language.