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

ویکی‎کتاب، کتابخانهٔ آزاد
پرش به ناوبری پرش به جستجو

حل تمرین ۱-۳۶

تمرین[ویرایش]

فرض کنید {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 عضو زبان نیست پس زبان نامنظم است.