ISI2011-PCB-CS-4a

Question

Let $L$ be the set of strings over $\{0, 1\}$ containing an unequal number of $0$s and $1$s. Prove that

1. $L$ is not regular.
2. $L^2$ is regular.

Comments

@Praveen Saini  sir,

In 2nd case:

L^(2) contain either equal no of 0's or 1's  or  unequal number of 0' or 1's.....which means takes all string except Null string..

plz check ..whether i am right or wrong??

---

I think the assumption that L^2 contains all strings over {0,1} is not correct. I can give one example. Try 010. You can't break it into two parts each containing unequal no of 0's and 1's (note that null string doesn't belong to L). So it doesn't belong to L^2. So are 10101, 1010101 etc.  

For proving, L is not regular, you can use pumping lemma with 0n1m, and m = n!+n, where n is that magic no. Let w = xyz, with |xy| <= n. Our middle string y in this case contains all 0's, and no of 1's does not get impacted by pumping. If length of y is k, then pumping n!/k (this is a whole no) times will make the  no of 0's exactly equal to n!+n.

Answer 1

Lets assume L is regular.

Then there must exist som value p which is the pumping length for L.

lets take a string w  ∊ L and |w|>=p

assume the split of  w=xyz

Now 3 conditions of pumping lemma needs to be satisfied 

1. |xy|<=p
2. |y|>0
3. xy^iz  ∊ L  for i>=0

now take w= 0^p1^p-1  [this string definitely belong to L ]

Now our xy should be limited to first p symbols

lets assume a partition |x|=p-1   and  |y|=1

take i=0   [just remove y]

so,  xy^0z  =  0^p-1  1^p-1   [this str does not belong to L since number of 0 and number of 1 is same ] 

therefore it contradicts our initial assumption of L being regular.

Hence L is not regular.

 

 

Answer 2

i) S ->S₁S₂ | S₂S₃

  S₁ ->0S₁ | 0

  S₂ -> 0S₂1 | ∊

  S₃ ->1S₃ | 1

So, L is not regular

ii) but L² is regular

and L² =(0+1)⁺

So, L² will be regular

Comments

Yes.

---

@srestha 

can you check the grammar once because it is not generating strings like 0001110

---

@chirudeepnamini

I just proved one grammar that contain "unequal number of 0s and 1s" and is non-regular. But it maynot contain each and every grammar which contains "unequal number of 0s and 1s".The question asked to prove by some non regular grammar, but not all.