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

۵۲.۱) تئوری Myhill-Nerode.(ارجاع به سوال ۵۱.۱)

فرض کنید L یک زبان و X مجموعه ای از رشته ها باشد. می گوییم X دو به دو توسط L قابل تشخیص است اگر هر دو رشته مجزا در X توسط L قابل تشخیص باشند. L index ماکسیمم تعداد عناصر یک مجموعه است که دو به دو توسط L قابل تشخیص هستند.index می تواند محدود یا نامحدود باشد.

الف)نشان دهید اگر L دارای یک DFA با K state باشد.حداکثر index زبان L برابر K است.

ب)نشان دهید اگر index L محدود و برابر K داشته باشد.با یک DFA که دارایstate K است شناخته می شود.

ج)نتیجه گیری کنید L منظم است اگر و فقط اگر دارای index محدود باشد. علاوه بر این index برابر سایز کوچکترین DFA برای شناخت این زبان است.

الف) این ادعا را با برهان خلف اثبات می کنیم.فرض می کنیم ماشین M یک DFA با state K باشد که L را شناسایی می کند. فرض خلف : index زبان L بزرگتر از K است. این بدین معناست که مجموعه ای با بیش از K عنصر وجود دارد(به عنوان مثال X) که دو به دو توسط L قابل تشخیص هستند.چون L دارای state K است طبق اصل لانه کبوتری X دارای دو رشته مجزا X و Y است به طوری که :

                                                                       (δ(q0,x) = δ(q0,y   

بنا براین (z ∈*∑ δ(q0,YZ) = δ (q0,XZ برای هر ‏‏‏، در این صورت هردو رشته YZوXZ عضو Lهستند یا هر دو متعلق به L نیستند و این با تعریف قابل تشخیص بودن توسط L در تضاد است. پس فرض خلف رد شده و index زبان L حداکثرK است.

ب){X={S1,…,Sk مجموعه ای است که اعضای آن دو به دو توسط L قابل تشخیص هستند.حال برای اثباتDFAای به نام M باK state میسازیم.

                              M=(Q, ∑, δ, q0,F)             
 Q ={q1,…,qk}                                                 
F={qi|si∈L}                                                 
  δ(qi,a)=qj   if  sia ~ sj                                    
sj∈L چرا که اگر   sj ∈ L نباشد آنگاه k + 1 عنصر داریم که دو به دو توسط L قابل تشخیص هستند.     
                                                               

q0=qi،اگر si با تهی هم ارز باشد.                                                          

ج)فرض می کنیم L یک زبان منظم باشد.در این صورت L دارای DFA با state K است طبق (الف) K= index < چون K محدود است index نیز محدود می شود. حال اگر L دارای index محدود K باشد طبق قسمت(ب) با یک DFA شناخته می شود از این رو منظم است.طبق قسمت (ب) DFA دارای دقیقا K state است.این DFA کوچکترین DFA ممکن است چرا که اگرتعداد state ها کمتر باشد طبق قسمت (الف) می توان نشان داد که index از K کوچکتر است و این تناقض است.