حل تمرین نظریه محاسبات-ویرایش دوم/فصل اول/حل تمرین۱-۴۷

اثبات کنید که زبان زیر منظم نیست :

∑ = {1,#} Y={w|w = x1# . . . xk# for k>=0 each xkє 1* , and xk != xj for i != j}

In English, A is the set of all strings consisting of zero or more strings of 1’s separated by #’s such that no two of these strings of 1’s have the same length. For example 1, 1#11#111, 1111##11#1111111 and 111#1111#11111#11111 are in A, but 1#1 and 1#11#111#11 are not.

(a) Let p be a proposed pumping lemma constant for A.

(b) Let u = 1p#1p+1#• • •#12p. Note that we can write u = u0#u1# • • • #uk, where k = p and ui = 1p+i. (c) Let xyz = u such that |y| > 0 and |xy| ≤ p. (d) Let v = xy2z. Note that we can write v = v0#v1# • • • #vk, where k = p, v0 = 1p+|y| and for 1 ≤ i ≤ p, vi = 1p+i. Because 1 ≤ |y| ≤ p, we conclude p + 1 ≤ (p + |y|) ≤ 2p and v0 = vp+|y|. Thus, v !∈ A. (e) A does not satisfy the conditions of the pumping lemma. Therefore, A is not regular.