1. Prove that L = {0
|
|  Yüklə 22 Kb.
|
| 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 xyiz L.
1. Prove that L = {0i | 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 = 0m^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 xy2z. Then, we have m2 = |w| < |xy2z| ≤ m2 +m = m(m + 1) < (m + 1)2. That is, the length of the string xy2z lies between two consecutive perfect squares. This means xy2z 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 = ambamb. Clearly, w L so by the pumping lemma, w = xyz such that |xy| m. |y| > 0 and xyiz L for all i 0. Let p = |y|. Consider what happens when i = 0. The resulting string, xz = am-pbamb. 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. |