Here are some pumping lemma examples to look through. The style indicated is how I expect you to do those proofs. Remember there are two things to show: 1) the string you choose is in the language L and 2) there is some value of i for which xy^{i}z L.
**1. Prove that L = {0**^{i} | i is a perfect square} is not a regular language.
**Proof: Assume that L is regular and let m be the integer guaranteed by the pumping lemma. Now, consider the string w = 0**^{m^2}. Clearly w L, so w can be written as w = xyz with |xy| ≤ m and y (or |y| > 0). Consider what happens when i = 2. That is, look at xy^{2}z. Then, we have m^{2} = |w| < |xy^{2}z| ≤ m^{2} +m = m(m + 1) < (m + 1)^{2}. That is, the length of the string xy^{2}z lies between two consecutive perfect squares. This means xy^{2}z L contradicting the assumption that L is regular.
**2. Prove that L = {ww | w {a, b}*} is not regular. **
**Assume L is regular and let m be the integer from the pumping lemma. Choose w = a**^{m}ba^{m}b. Clearly, w L so by the pumping lemma, w = xyz such that |xy| m. |y| > 0 and xy^{i}z L for all i 0. Let p = |y|. Consider what happens when i = 0. The resulting string, xz = a^{m-p}ba^{m}b. Since p 1, the number of a’s in the two runs are not the same, and thus this string is not in L. Therefore L is not regular. |