حل تمرین نظریه محاسبات/فصل اول/حل تمرین1-34

حل تمرین 1-34

تمرین

فرض کنید x و y دو رشته و L یک زبان باشد. x و y را تمایز پذیر توسط L گویند اگر رشته هایی مانند z موجود باشند به طوری که فقط یکی از دو رشته xz یا yz عضو L باشند. از طرف دیگر اگر برای هر رشته ی z و xz عضو L رشته ی yz هم عضو L باشد، آن گاه x و y را غیر قابل تمایز توسط L گویند. اگر x و y غیر قابل تمایز توسط L باشند آنها را به صورت x≡Ly می نویسیم. نشان دهید کهL≡ یک رابطه ی هم ارزی است.

حل

بازتابی) برای هر رشته z وxz عضو xz ،L نیز عضو L است پس x≡Lx

تقارنی)اگر برای هر رشته ی z و xz عضو yz ،L هم عضو L باشد،آنگاه می توان نوشت برای هر رشته ی z و yz عضو xz ،L هم عضو L است.پس داریم: x≡Ly → y≡Lx

تعدی)اگر برای هر رشته z و xz عضو yz ،L هم عضو L باشد
و
برای هر رشته ی z و yz عضو KZ ،L هم عضو L باشد.آن گاه می توان نوشت برای هر رشته ی z و xz عضو KZ ، L هم عضو L است. y≡Lk → x≡Lk و x≡Ly
Mashhadi ‏۱۸ آوریل ۲۰۰۹، ساعت ۱۰:۳۶ (UTC)