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

حل تمرین ۱-۳۶

تمرین

فرض کنید {0،1،+،=}=Σ بوده و {x و y و z اعداد باینری بوده و X مجموع y و z است. | ADD = { x = y + z. نشان دهید که ADD منظم نیست.

حل

با استفاده از لم تزریق این مسأله را حل می‌کنیم.
فرض کنیم زبان منظم بوده و بخواهیم لم تزریق را با طول تزریق m بکار ببریم. یک رشته مانند s با طول حداقل m پیدامی کنیم که ما را به تناقض برساند.

S : 2^m =1^m0^m + 0^m1^m

چون

|xy|<m ,|y|>1

در نتیجه y=1^k , k<m

داریم :

w_i=1^m-k1^ik1^m=1^m0^m+0^m1^m

با قرار دادن i = 0 داریم :

s :1 ^2m-k=1^m0^m+0^m1^m

که واضح است s عضو زبان نیست پس زبان نامنظم است.