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

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

مسئله :

برای هر رشته w=w₀w₁...w_n معکوس رشته به صورت w^R نوشته شده و رشته w به صورت برعکس به شکل w=w_nw_n-1...w₀ می باشد. برای زبان A ، معکوس آن به صورت A^R = { w^R | w ∈ A }0 است . نشان دهید اگر زبان A منظم باشد A^R هم منظم است .

پاسخ:

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

چون به ماشین یک حالت جدید اضافه کرده ایم پس داریم Q^´ = {q_start} $\bigcup$ Q . واضح است که الفبای ترانهاده با خود زبان برابر است پس داریم Ʃ^´ = Ʃ . از طرفی طبق توضیحات بالا تنها عضو مجموعه E همان q₀ خواهد بود . برای تعریف ریاضی تابع انتقال داریم :

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