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

سوال 1.51) x و y دو رشته می باشند و L یک زبان دلخواه می باشد. X و y زمانی توسط L قابل تشخیص اند که رشته ای مثل z وجود داشته باشد که به وسیله آن دقیقا یکی از رشته های xz یا yz عضو L باشند. در غیر این صورت برای هر رشته z که xz عضو L باشد هنگامیکه yz هم عضو L باشد می گوییم x و y توسط زبان L تشخیص داده نمی شوند. اگر x و y توسط زبان L قابل تشخیص نباشند داریم : x ≈L y .نشان دهید که L≈ یک رابطه هم ارزی است.

پاسخ: برای اثبات این مساله باید ثابت کنیم سه خاصیت بازتابی و تقارنی و تعدی برقرار است.

بازتابی:

                                           x ≈L x

چون xz عضو زبان L است پس رابطه ی فوق برقرار است.

تقارنی:

                                       x ≈L y <---> y ≈L x

x و y هر دو توسط زبان L تشخیص داده نمی شوند <---> xz و yz هر دو عضو L می باشند <---> بر اساس خاصیت جابه جایی داریم <---> پس yz و xz عضو L هستند <---> y ≈L x

تعدی:

                                y ≈L m <---> x ≈L m و x ≈L y

x و y هر دو توسط زبان L تشخیص داده نمی شوند پس xz وyz هر دو عضو L می باشند.(1) y و m هر دو توسط زبان L تشخیص داده نمی شوند پس yz وmz هر دو عضو L می باشند.(2) از موارد (1)و(2)نتیجه می گیریم که xzو mz به طور همزمان عضو L می باشند <---> هر دو توسط زبان L قابل تشخیص نیستند <---> x ≈L m