حل تمرین نظریه محاسبات/فصل اول/حل تمرین ۱-۳۶
ظاهر
(تغییرمسیر از حل تمرین نظریه محاسبات/فصل اول/حل تمرین1-36)
حل تمرین ۱-۳۶
تمرین
[ویرایش]فرض کنید {0،1،+،=}=Σ بوده و {x و y و z اعداد باینری بوده و X مجموع y و z است. | ADD = { x = y + z. نشان دهید که ADD منظم نیست.
حل
[ویرایش]با استفاده از لم تزریق این مسأله را حل میکنیم.
فرض کنیم زبان منظم بوده و بخواهیم لم تزریق را با طول تزریق m بکار ببریم.
یک رشته مانند s با طول حداقل m پیدامی کنیم که ما را به تناقض برساند.
S : 2m =1m0m + 0m1m
چون
|xy|<m ,|y|>1
در نتیجه y=1k , k<m
داریم :
wi=1m-k1ik1m=1m0m+0m1m
با قرار دادن i = 0 داریم :
s :1 2m-k=1m0m+0m1m
که واضح است s عضو زبان نیست پس زبان نامنظم است.