Ana səhifə

1. Prove that L = {0

Yüklə 22 Kb.
ölçüsü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.

Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur © 2016
rəhbərliyinə müraciət