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

حل تمرین۱-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 داریمabic є ADD

2.

3.

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



S : 12p =1p1p + 0p0p

S:  

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


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

ac =

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

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

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