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

سوال 1.31 از ویرایش دوم کتاب مقدمه ای بر نظریه محاسبات - مایکل سیپسر

مسئله :

برای هر رشته w=w0w1...wn معکوس رشته به صورت wR نوشته شده و رشته w به صورت برعکس به شکل w=wnwn-1...w0 می باشد. برای زبان A ، معکوس آن به صورت AR = { wR | w ∈ A }0 است . نشان دهید اگر زبان A منظم باشد AR هم منظم است .

پاسخ:

چون زبان A منظم است پس یک NFA مانند N با تعریف (N=(Q,Ʃ,δ,q0,F وجود خواهد داشت که زبان A را می پذیرد . حال با کمک ماشین N یک NFA مانند M با تعریف (M=(Q´´´,qstart,E خواهیم ساخت تا ترانهاده زبان A را تشخیص دهد . ایده ساخت ماشین M به گونه ای خواهد بود که یک حالت جدید با نام qstart اضافه می کنیم و با یک یا چند انتقال تهی به حالات پذیرش ماشین N می رویم . سپس توابع انتقال ماشین N را به گونه ای تغییر می دهیم که هر یال در جهت معکوس ماشین N رفتار کند . در نهایت تنها حالت پذیرش ماشین M همان حالت شروع ماشین N یعنی q0 خواهد بود .

چون به ماشین یک حالت جدید اضافه کرده ایم پس داریم Q´ = {qstart} Q . واضح است که الفبای ترانهاده با خود زبان برابر است پس داریم Ʃ´ = Ʃ . از طرفی طبق توضیحات بالا تنها عضو مجموعه E همان q0 خواهد بود . برای تعریف ریاضی تابع انتقال داریم :

حال ماشین M می تواند ترانهاده زبان A را تشخیص دهد.


حالت کلی ماشین N
حالت کلی ماشین M