Can you prove using the pumping lemma that the followint lan

Can you prove using the pumping lemma that the followint languages are non-regular?

L_1 = {0^i 1^j | i > j}. (beta) L_2 = {1^n^2 | n greaterthanorequalto 0}. (gamma) L_3 = {1^n^i | n greathanorequalto 0}.

Solution

Pumping lemma principle :

Assume every word in the given language L (noted word as w here) is in the format xyz & length of |xyz| =n.

                                i.e ) w= xyz  

if the above word satisfies below 3 rules then the given language is regular other wise it is not regular.                                               

                             1. |y|>=1     //length of y greater than or equal to 1

                             2.|xy|<=n

                   3. for all i 0, xy ⁱ z L     

a) L1={0ⁱ1^j   | i>j}

if i=1,j=0 < i then w=0

if i=2,j=1< i then w=001,

if i=3,j=2<0 the w=00011 ,   etc….

Now L1 ={0, 001,00011,0000111,000001111,………}

Apply pumping lemma

Consider w= 00011 (xyz format--à |y|>=1, |xy|<=n (n=|xyz|) )

    Assume       x=00,

y=01,   |y|>=1

z=1

Now Apply pumping lemma 3^rd rule by taking i=2    (for all i 0, xy ⁱ z L )   

Now       W= 00 (01)² 1= 00 0101 1

        (This word does not belongs to L .so the language is not regular )

b) L1={1ⁿ²   | n>=0}

if n=0 then w=1

if n=1 then w=11

if n=2 then w=1111,   etc….

Now L1 ={ 1,11,1111,111111111,………}

Apply pumping lemma

Consider w= 1111 (xyz format--à |y|>=1, |xy|<=n (n=|xyz|) )

    Assume x=1,

y=11,   |y|>=1

z=1

Now Apply pumping lemma 3^rd rule by taking i=2    (for all i 0, xy ⁱ z L )   

Now       W= 1 (11)² 1= 111111

         (This word does not belongs to L .so the language is not regular )

C) L1={1^n!   | n>=0}

if n=0 then w=1

if n=1 then w=1

if n=2 then w=11

if n=3 then w=111111,   etc….

Now L1 ={ 1,11,111111,11111111111111111111111,………}

Apply pumping lemma

Consider w= 111111 (xyz format--à |y|>=1, |xy|<=n (n=|xyz|) )

    Assume       x=111,

y=11,   |y|>=1

z=1

Now Apply pumping lemma 3^rd rule by taking i=2    (for all i 0, xy ⁱ z L )   

Now       W= 111 (11)² 1= 111111 11

         (This word does not belongs to L .so the language is not regular )