Show that L = {0n1n | n≥1} is not regular.

Show that L = {0n1n | n≥1} is not regular.

Ans.

    Step-1: Suppose L is regular and we get a contradiction.

Let n be the number of states in FA accepting L.

    Step-2: Let w=0^m1^m. Then |w| = 2m>m. By pumping Lemma we write w = xyz with |xy|≤m and |y|≠0.

    Step-3: We want to find n so that xynz ∉ L for getting a contradiction. The string y can be in any of the following forms :

        Case-1  y has 0's, i.e. y=0k for some k ≥ 1.

        Case-2  y has only 1's, i.e. y=1t for some t ≥ 1.

        Case-3  y has both 0's and 1's, i.e. y=0k1t for same k,t ≥ 1.

    In case 1, we can take n = 0. As xyz = 0m1m, xz = 0m-k.1m.

    As k ≥ 1, m-k ≠ m. So xz ∉ L.

    In case 2, take n=0. As before xz is 0m1m-t and m ≠ m - t.

    So xz ∉ L.

    In case 3, take n=2. As xyz=0m-k.0k1t1m-t

  xy2z = 0m-k 0k 1t 0k 1t 1m-t. As xy2z is not of the form 0n1n, xy2z ∉ L.

Thus in all cases, we get a contradiction.

Therefore, L is not regular.