Let L be the language of all strings of the form 0n 12n Wher

Let L be the language of all strings of the form 0^n 1^2n. Where n greaterthanorequalto 1. Prove that L is not regular.

Solution

Prove by contradition.

Bye definition of Regular language.

et LL be a regular language. Then there exists an integer p1p1 (depending only on LL) such that every string ww in LL of length at least pp (pp is called the \"pumping length\") can be written as w=xyzw=xyz (i.e., ww can be divided into three substrings), satisfying the following conditions:

.Here,let k be pumping lenght iven by pumping lemma.

Let w=0^n1^2n

Now = consider the various cases to split w into xyz with |xy|n and |y|>1.
Since |xy|<k no matter how we split w, x will consist of only 0\'s and so will y.
Lets assume |x|=s and |y|=k. We need to consider ALL the options, that is all the possible s,k such that s0,n1 and s+kn. FOR THIS LL the proof for all these cases is the same, but in general it might be different.
take i=0 and consider xy^iz=xz. this word is NOT in LL since it is of the form 0^nk 1^ 2n (no matter what s and n were), and since n1, this word is not in LL and we reach a contradiction.
Thus, our assumption is incorrect, and LL is not regular.

let n=1,then L=011.
n=3 -->000111111 this let x=0,y=001 |xy|<=3 and |y|>1.here s lenght(x)=1 and k:lenght(y)=3 ,s+k =4 is notless than or equal to 3(i.e).so not regular