Example proofs for pumping lemma #

1 #

Let \(L\) be the set of all strings with an equal number of 0 and 1 over the alphabet {0,1}. i.e. { \(\lambda\) , 01, 10, 0011, 0101, 0110, 1001 …}

Theorem: \(L\) is not regular.

Proof:

For purposes of contradicition assume \(L\) is regular. Because \(L\) is regular there must be a pumping length \(p\) . Consider the string \(0^p 1^p\) which is in \(L\) . The pumping lemma says there exists \(xyz\) . This means that \(x\) and \(y\) are all 0, since \(y\) is not empty \(xz\) fill have fewer 0s than \(xyz\) , but the same number of 1s. This means that \(xz\) has a different number of 0s than 1s, and is therefore not in \(L\) . This contradicts that the pumping lemma says \(xy\) is in \(L\) .

2 #

Let \(L\) be the set of all palindroms over alphabet {0,1}, i.e. { \(\lambda\) , 0, 1, 00, 11, 000, 010, 101, 111, 0000, …}

Theorem: \(L\) is not regular.

Proof:

For purposes of contradicition assume \(L\) is regular. Because \(L\) is regular there must be a pumping length \(p\) . Consider the string \(0^p 1 0^p\) which is in \(L\) . The pumping lemma says there exists \(xyz\) . Since \(|xy| \leq p\) , \(x\) and \(y\) are all 0s. Since \(y\) is not empty, \(xyyz\) will cause more 0s before the 1 than after. The result is not a palindrome so \(xyyz\) is not in \(L\) . This contradicts that the pumping lemma says \(xyyz\) is in \(L\) .