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

حل تمرین۱-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\le |b|$

3. $|ab|\le p$

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

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

S: $\underset{2p}{\underbrace{111111\dots \dots .111_1}}\Rightarrow \stackrel{a}{\overbrace{1111\dots 1}}\stackrel{b}{\overbrace{1111\dots 1}}\stackrel{c}{\overbrace{1111..11}}$ 

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

$1\le |b|=>b=1^k$

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

ac = $\underset{2p-k}{\underbrace{11111\dots \dots 11111}}$

باتوجه به رابطه بالا باید داشته باشیم که 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 نامنظم است.