Sipser Exercise 1.54


(a) The language is not regular.


Proof: Suppose were regular. Let . Observe that is regular. In particular, a regular expression for is .

But, . We show that is non-regular. Suppose it were and let be the pumping length. Take , and . Take , and .

If , then which is not in . If for some , then which is not in . If for some , then which is not in . This contradicts the pumping lemma so is non-regular.

So, we have the the intersection of two regular languages producing a non-regular language, a contradiction. So it must be the case that is not regular.


(b) satisfies the pumping lemma.


Proof: Take the pumping length . We show that every string of length at least 2 can be pumped. Let such that be arbitrary.

Suppose there are no ’s in . Then with . Take where , is the first symbol of and is the rest of (note and ). Then clearly, for any because this simply changes the number of occurrences of the first symbol in (be it or ).

Suppose there is one in . It must come first, so , with . Take where , , and is the rest of (note and ). Then because this simply changes the number of ’s at the beginning of the string.

Suppose there are two ’s in . Then with . Take with , , and is the rest of . Then because this simply alters the amount of ’s in the string, but since it can never be the case that , the restriction that the ’s and ’s must be equal in number is never encountered.

Suppose there are more than two ’s in . Then with and . Take with , , and is the rest of . Then where (that is, the lowest amount of ’s remaining after pumping is 2). Because , this is clearly in .

So satisfies the pumping lemma.