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

حل تمرین۱-53: تمرین:فرض کنید {0,1,+,=}=∑ و{x و y و z اعداد باینری بوده و X مجموع y و z است. | ADD = { x = y + z. نشان دهید که ADD منظم نیست.

حل: برای حل این سوال از برهان خلف استفاده می کنیم.فرض می کنیم ADDمنظم است ونشان می دهیم که این امر ممکن نمی باشد .

فرض کنیم کهPطول تزریق به دست آمده توسط لم تزریق باشد .به این ترتیب برای هر رشته ی sدر زبان ADDکه طول آن حداقل P باشد ،sرا می

توان به سه جز تقسیم کردیعنی s = abcو این سه جز شرایط زیر را دارند:

1.برای هر i≥0 داریمabⁱc є ADD

2. $1\leq |b|$

3. $|ab|\leq p$

رشته S را به صورت زیر در نظر می گیریم :

S : 1^2p =1^p1^p + 0^p0^p

S: $\underbrace {111111\ldots \ \ldots \ .111_{1}} _{2p}\Rightarrow \overbrace {1111\ldots 1} ^{a}\overbrace {1111\ldots 1} ^{b}\overbrace {1111..11} ^{c}$ 

با توجه به بند 2 در بالا داریم:

$1\leq |b|=>b=1^{k}$

هم چنین در بند 1 داریم:
برای هر i≥0 داریمabⁱc є ADD ، اگر i=0 باشد می توان نوشت :

ac = $\underbrace {11111\ldots \ldots 11111} _{2p-k}$

باتوجه به رابطه بالا باید داشته باشیم که ac є ADD است.یعنی رابطه زیر برقرار است:

$S:1^{(}2p-k)=1^{p}1^{p}+0^{p}0^{p}$

در صورتی که میدانیم رابطه زیر برقرار است ونه رابطه بالا .

$S:1^{2}p=1^{p}1^{p}+0^{p}0^{p}$

بنابراین فرض خلف باطل است ومی توان گفت زبان ADD نامنظم است.