Ana səhifə

# 1. Prove that L = {0

Yüklə 22 Kb.
 tarix 24.06.2016 ö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 ©atelim.com 2016
rəhbərliyinə müraciət