به نام خدا

قضیه شرح میدهد که : حریف باید با انتخاب عدد n بازی را شروع کند ،سپس شما رشته w را که متعلق به زبان بوده و طولش بیشتر از n باشد پیده می‌کنید؛حریف حالا باید رشته w را به نحو مناسبی به xyz‌ تجزیه کند؛ و در آخر، شما پیروزمندانه عدد i‌را مطرح می‌کنید بطوریکه xyz متعلق به زبان نباشد. اگر شما یک استراتژی برای برد داشته باشید ، هر چقدر هم که حریف خوب بازی کند، باز شما می‌توانید منظم  نبودن L ‌را ثابت کنید.

از این قضیه نتیجه می‌گیریم که هیچ یک از دو زبان فوق منظم نیستند.

مثال 2-4-2: زبان L={aⁱbⁱ : i>=0} منظم نیست، زیرا اگر منظم باشد باید قضیه 1-3-2 با به کاربردن عدد n برای آن صادق باشد.توجه کنید که رشته w=aⁿbⁿ ∈L . بر طبق قضیه می‌توان نوشت: w=xyz به طوری که |xy|≤n و y≠e (یعنی y=aⁱ ,i>0)، اما xz=a^n-ibⁿ∉L)) و این بر خلاف قضیه است.

مثال 3-4-2: زبان {n عدد اول است : aⁿ} =L منظم نیست.برای اثبات منظم نبودن آن ، x,y,z را به طوری که درد قضیه 1-4-2 مشخص شده است ،‌در نظر بگیرید. x=a^p , y=a^q , z=a^r  که در آنها p,r≥0 , q>0 . بر طبق قضیه ،‌xyⁿz∈L به ازای هر n≥0 ، یعنی:p+nq+r به ازای هر n≥0 عدد اول است. اما این غیر ممکن است، مثلا اگر n=p+2q+r+2 ، در نتیجه p+nq+r= (q+1)(p+2q+r) که حاصلضرب دو عدد طبیعی بزرگتر از 1 است.

مثال 4-4-2: گاهی اوقات از بسته بودن ویژگیها برای نشان دادن منظم نبودن یک زبان استفاده میشود. بعنوان مثال : { w تعداد مساوی aو b‌دارد:‌w∈{a,b}* }=L ، منظم نیست.، زیرا اگر L ‌ واقعا منظم باشد، پس باید L∩a*b* هم منظم باشد(بر طبق قانون بسته بودن تحت اشتراک؛قضیه(e) 1-3-2 را به یاد آورید.). اما زبان اخیر، دقیقا {aⁿbⁿ: n≥0} است که قبلا منظم نبودن آن را نشان داده ایم.

در واقع ،‌قضیه 1-4-2 می‌تواند در روشهای مختلف به نحو مؤثری به کار گرفته شود.(در تمرین 11-4-2 یکی از آن روشها را ببینید.)

تمرینهای بخش 4-2

1-4-2: یک تصاعد حسابی مجموعه {p+qⁿ : n=0,1,2,…} است که در آن p,q∈N.

(a)    (آسان) نشان دهید که اگر L⊆{a}* و {n: aⁿ∈L} یک تصاعد حسابی باشد ، L منظم است.

(b)   نشان دهید که اگر L⊆{a}* و {n: aⁿ∈L} ، اجتماع تعدادی تصاعد حسابی متناهی باشد ، L منظم است.

(c)    (سخت‌تر) نشان دهید که اگر L⊆{a}* منظم باشد، پس {n: aⁿ∈L} اجتماعی از تصاعدهای حسابی متناهی است.(این تمرین معکوس قسمت (b) است.)

(d)   نشان دهید که اگر ∑ یک الفبا بوده و L⊆∑*  منظم باشد،‌پس {|w|: w∈L} اجتماعی از تعدادی تصاعد حسابی متناهی است.(راهنمایی: از قسمت c استفاده کنید.)

2-4-2:‌D={0,1} و T=D*D*D را در نظر بگیرید.جمع صحیح دو عدد در منطق باینری می‌توان به صورت رشته‌ای در T*‌تصور شود،اگر T را به صورت ستونهای عمودی در نظر بگیریم. مثلا

می‌تواند به صورت رشته زیر و با چهار نماد تصویر شود:

نشن دهید که مجموعه همه رشته‌های متعلق به T* که جمع صحیحی را نشان می‌دهند ،‌ یک زبان منظم است.

3-4-2: نشان دهید هر یک  از زبانهای زیر منظم هستند یا نه؟

منطق دهدهی برای یک عدد، عددی است که به روش متداول نوشته می‌شود‌: به صورت رشته‌ای روی الفبای {0,1,…,9} .مثلا در منطق دهدهی عدد 13 رشته‌ای به طول 2 است. در منطق یکتایی فقط نماد I‌استفاده می‌شود، مثلا عدد 5 در منطق یکتایی به صورت IIIII‌ نشان داده می‌شود.

(a)    {w در منطق یکتایی بوده و مضربی از 7 است : w }.

(b)   { w در منطق دهدهی بوده و مضربی از 7 است : w }.

(c)    {w‌ نمایش یکتایی عدد n  است به طوری که جفت p , p+2 وجود داشته باشند و هر دو عدد اول بوده و از n‌ بزرگتر باشند.}

(d)   {w نمایش یکتایی ⁿ10 است به ازای n≥1 : w}

(e)    {w نمایش دهدهی ⁿ10 است به ازای n≥1 : w}

(f)     {w‌ دنباله ارقام دهدهی است که در بسط 7/1 ظاهر می‌شوند.مثلا 5714 یک دنباله است زیرا 0.14285714285714=7/1: w}

(e)    4-4-2: ثابت کنید {aⁿba^mba^m+n : n,m≥1} منظم نیست.

4-5-2: با استفاده از قضیه پامپینگ و بسته بودن تحت اشتراک نشان دهید که زبانهای زیر نامنظم هستند.

(a)    {ww^R : w∈{a,b}*}

(b)   {ww : w∈{a,b}*}

(c)    {ww : w∈{a,b}*} w نشان‌دهنده رشته w‌ است به طوری که در w هر  a‌با b و بالعکس جایگزین شده‌اند.

6-4-2: رشته x  روی الفبای {(,)} متوازن نامیده میشود هر گاه شرایط زیر را داشته باشد:

(i)               در هر پیشوند x‌ تعداد ")" ها کمتر از تعداد "(" نباشد.

(ii)             تعداد")" ها در x مساوی تعداد "(" ها باشد.

یعنی  xمتوازن است اگر بتواند از یک عبارت محاسباتی صحیح و با حذف کردن متغیرها،عددها و عملگرها از آن ، بدست آید. (فصل بعدی را برای یک تعریف کاملتر ببینید.) نشان دهید مجموعه همه رشته‌های متوازن در {(,)}* منظم نیست.

7-4-2: نشان دهید برای هر ماشین متناهی قطعی M={K,∑,& ,s,F} ، M یک زبان متناهی را می‌پذیرد اگر و فقط اگر M رشته‌ای با طول بیشتر یا مساوی |K|‌و کمتر از 2|K| را بپذیرد.

8-4-2: کدام یک از عبارات زیر صحیح هستند؟ در هر مورد پاسختان را توضیح دهید.( در هر مورد الفبای ∑ مفروض است.)

(a)    هر زیرمجموعه‌ای از یک زبان منظم، منظم است.

(b)   هر زبان منظمی یک زیرمجموعه خاص منظم دارد.

(c)    اگر L منظم باشد،پس {xy: x∈L , y∉L} هم منظم است.

(d)   {w: w=w^R} منظم است.

(e)    اگر L زبان منظمی باشد، {w:w∈L , w^R∈L} هم منظم است.

(f)     اگر C مجموعه‌ای از زبانهای منظم باشد، در نتیجه ~C هم زبان منظمی است.

(g)    {xyz^R: x,y∈∑*} منظم است.

9-4-2: نظریه ماشین متناهی دونواره در تمرین 5-1-2 تعریف شده است. نشان دهید که {(aⁿb , a^mb^p): n,m,p>0

 , n=p or  n=m} توسط هیچ ماشین متناهی دونواره قطعی پذیرفته نمی‌شود.(راهنمایی:‌فرض کنید این مجموعه توسط حداقل یک ماشین متناهی قطعی دونواره پذیرفته شده ایت. پس M‌ به ازای هر n ،  (aⁿb,aⁿ+1bⁿ)را می‌پذیرد. حالا توسط آرگومانهای پامپینگ نشان دهید که M به ازای هر n≥0,q>0،(aⁿb,aⁿ⁺¹b^n+q) را هم می‌پذیرد و این یک تناقض است.) بر طبق تمرین 9-3-2 ماشین متناهی غیرقطعی همواره نمی‌تواند به ماشین قطعی معادل تبدیل شود. و بر طبق تمرین 5-1-2 مجموعه پذیرفته شده توسط ماشین متناهی قطعی دونواره تحت اجتماع بسته نیست.

10-4-2: ماشین متناهی دو-هد ، ماشین متناهی‌ای است بادونوار که میتوانند به طور مستقل، فقط از چپ به راست و روی نوار ورودی، حرکت کنند.زیرا در یک ماشین متناهی دونواره(تمرین 5-1-2)، مجموعه حالت به دو بخش تقسیم می‌شود؛ هر بخش به خواندن و حرکت کردن یکی از هدهای نوار مربوط است.یک رشته در صورتی پذیرفته می‌شود که هر دو هد، با هم، در انتهای رشته و در یکی از حالات نهایی متوقف شوند. ماشین متناهی با دو هد می‌تواند قطعی یا غیر قطعی باشد.با استفاده از دیاگرام حالت برای نشان دادن طراحی خود ، نشان دهید که زبانهای زیر توسط ماشین متناهی دوهده پذیرفته می‌شوند.برای کدام موارد می‌توان ماشین قطعی ساخت؟

(a)  {aⁿbⁿ : n>=0}

(b) {wcw: w∈ {a,b}*}

(c)  {a¹ba²ba³b…ba^kb: k≥1}

11-4-2: این تمرین ورژن قویتری از قضیه پامپینگ 1-4-2را معرفی می‌کند.هدف ساختن قسمت پامپ شده با بیشترین طول ممکن است. M={K,∑,&,s,F}را به عنوان یک ماشین متناهی قطعی و  w‌را به عنوان رشته‌ای متعلق به L(M) با حداقل طول |k| در نظر بگیرید.نشن دهید رشته‌های x,y,z وجود دارند به طوری که به ازای هرn≥0 ، w=xyz, |y|≥(|w|-|k|+1)/|k| , xyⁿz∈L(M) .

12-4-2: D={0,1} و T+D*D*D را در نظر بگیرید.همچنین یک ضرب صحیح در منطق باینری می‌تواند به عنوان رشته‌ای متعلق به T* نشان داده شود.برای مثال: ضرب 50=10*5 یا

میتواند به صورت رشته‌ای با 6 نماد به صورت زیر تصویر شود:

نشان دهید که همه رشته‌های متعلق به T* که ضرب صحیحی را نشان میدهند، منظم نیست.(راهنمایی: ضرب (2n+1)(2n+1) را در نظر بگیرید.)

13-4-2: L⊆∑* را به عنوان یک زبان و Ln={x∈L: |x|≤n} را در نظر بگیرید.تراکم L‌ تابع dL(n)=|Ln| می‌باشد.

(a)    تراکم (a∪b)* چیست؟

(b)   تراکم ab*ab*ab*a‌ چیست؟

(c)    تراکم (ab∪aab)* چیست؟

(d)   نشان دهید که تراکم هر زبان منظم ، از بالا توسط عبارت چند جمله‌ای و از پایین توسط عبارت نمایی محدود شده است.(تابعی از 2^cn به ازای حداقل یک n) به عبارت دیگر، تراکم زبانهای منظم نمی‌تواند تابعی از یک نرخ رشد متوسط مثل nlogn‌باشد.(راهنمایی : ‌یک ماشین متناهی قطعی پذیرنده L‌ را درنظر بگیرید و همه دورها- مسیرهای بسته بدون نود تکراری- در دیاگرام حالت این ماشین را بیابید.چه اتفاقی می‌افتد اگر هیچ کدام از دورها نود مشترکی نداشته باشند؟چه اتفاقی می‌افتد اگر دو دور با نود مشترک وجود داشته باشند؟)

5-2: کمینه‌سازی وضعیت‌ها

در بخش گذشته ، تردید ما در مورد  اینکه ماشین متناهی قطعی مدل ضعیفی از کامپیوترهاست،تایید شد: بسیاری از محاسبات پیش پا افتاده،مثل مقایسه تعداد aها و bها در یک رشته، با ماشین متناهی انجام پذیر نیست.اگرچه، ماشینهای متناهی به عنوان یک مدل پایه‌ای برای کامپیوترها و الگوریتمها مفید هستند. در این خصوص، توانایی کمینه‌سازی تعداد وضعیتهای ماشین متناهی قطعی مفروض،‌یعنی تعریف یک ماشین متناهی قطعی معادل با کمترین تعداد وضعیت ، مهم است.مفاهیم و نتایج لازم برای یافتن الگوریتم کمینه‌سازی وضعیت را بسط میدهیم.

شکل 19-2

در یک ماشین متناهی قطعی داده شده،‌ممکن است راه ساده‌ای برای حذف حالتهای مختلف وجود داشته باشد.مثلا بیایید ماشین متناهی قطعی شکل19-2 ، پذیرنده زبان L={(ab∪ba)* را در نظر بگیریم.(بررسی آن مشکل نیست.) به حالت q₇‌ توجه کنید.واضح است که این وضعیت قابل دسترسی نیست؛زیراهیچ مسیری در دیاگرام وضعیت ماشین ،‌از حالت آغازین به آن وجود ندارد. این ساده‌ترین نوع بهینه‌سازی است که می‌تواند در مورد هر ماشین متناهی قطعی پیاده‌سازی شود: همه وضعیتهای غیر قابل دسترسی و همه انتقالهای ورودی و خروجی آنها را حذف کن.در واقع،‌این بهینه‌یازی به طور ضمنی در تبدیل ماشین متناهی غیر قطعی به ماشین متناهی قطعی معادش ، انجام میشود. (مثال 4-2-2 را به یاد آورید.) : همه وضعیتهایی که(از مجموعه وضعیتهای ماشین اصلی) از وضعیت آغازین ماشین بدست آمده قابل دسترسی نبودند را حذف کردیم.

تشخیص وضعیتهای قابل دسترسی در زمان چند جمله‌ای آسان است،‌زیرا مجموعه وضعیتهای قابل دسترسی میتوانند به صورت بستار  {s}‌تحت رابطه  }به ازای a∈∑ ،{(p,q): &(p,a)=q  ، تعریف شوند.بنابراین،‌مجموعه وضعیتهای قابل دسترسی می‌توانند توسط الگوریتم زیر محاسبه شوند:

R:={s}

تا  وقتی که وضعیتی مانند p∈R , a∈∑ وجود دارد به طوری که  &(p,a)∉R انجام بده:

&(p,a) را به R‌ اضافه کن.

بهرحال، ماشین باقی‌متنده پس از حذف وضعیتهای غیر قابل دسترس(شکل 20-2) هنوز هم وضعیتهایی بیشتر از نیاز واقعی خود دارد.مثلا ، وضعیتهای q₄,q₆ معادل هستند، و بنابراین می‌توانند در یک وضعیت ادغان شمند.معنی این سخن چیست؟ دو وضعیت را معادل می‌نامیم اگر هر دو وضعیت، منجر به پذیرش رشته‌های دقیقا یکسانی شوند.

تعریف بعدی ما درباره رابطه تشابه بین رشته‌هایی در زبان است که "سرنوشت مشترکی" دارند.

تعریف 1-5-2: L⊆∑* , x,y∈∑* را به عنوان یک زبان در نظر بگیرید.می‌گوییم x,y در رابطه با زبان L معادل هستند، با نماد x≈_Ly نمادگذاری می‌کنیم، اگر به ازای همه z∈∑* ، این رابطه درست باشد: xy∈L‌اگر و فقط اگر yz∈L . توجه کنید که ‍‍≈ یک رابطه هم‌ارزی است. به عبارت دیگر، x≈_Ly اگر یا هر دو رشته در L باشند یا هیچکدام در L‌ نباشند.و علاوه بر این حاصل الحاق هر رشته ثابتی به x,y دو رشته است که یا هر دو رشته در L هستند یا هیچکدام در L‌ نیستند.

مثال 1-5-2 : اگر x  یک رشته باشد در حالی که زبان  L‌توسط مفهومی درک شده است، کلاس هم‌ارزی مرتبط با L و وابسته به x‌را با نماد [x] نشان میدهیم.برای مثال، برای زبان L=(ab∪ba)*‌پذیرفته شده توسط ماشین شکل 20-2، به آسانی دیده می‌شود که _L≈ چهار کلاس هم‌ارزی دارد:

(1) [e] = L,

(2) [a] = La,

(3) [b] = Lb,

(4) [aa] = L(aa∪bb)∑*.

در (1)،‌برای هر رشته x∈L، شامل x=e ، zهایی که xz∈L را می‌سازند، دقیقا اعضای L  هستند. در (2) هر x∈La به یک z‌ به فرم  bL‌نیاز دارد تا xz‌ متعلق به L باشد. به طور مشابه، برای (3) zها به فرم aL‌ هستند. در نهایت در (4) هیچ zای وجود ندارد که بتواند رشته‌ای با یک پیشوند متعلق به L(aa∪bb) را به L بازگرداند.به عبارت دیگر، همه رشته‌های مجموعه (1) وضعیت یکسانی، در رابطه با متعلق بودن به L‌ دارند؛ و مجموعه‌های (2) و (3) و (4) هم همینطور.در آخر، به آسانی دیده می‌شود که این چهار کلاس ، کلاسهای هم‌ارزی *∑ هستند.بنابراین آنها کلاسهای هم‌ارزی _L≈ هستند.

توجه کنید که ‍_L≈ در رابطه با رشته‌های مرتبط با یک زبان است و نه رشته‌های مرتبط با یک ماشین. ماشین، رابطه دیگری ارائه می‌دهد که تا حدودی کمتر اصولی است و بعداً تشریح می‌شود.

تعریف2-5-2: M={K,∑,&,s,F}را به عنوان یک ماشین متناهی قطعی در نظر بگیرید.می‌گوییم دورشته x,y∈∑* در M هم‌ارز هستند ، و این رابطه را با ننماد x~_My نشان می‌دهیم، اگر هر دوی آنها دقیقاً از در اشتقاق M‌ از یک وضعیت به وضعیت مشابهی برسند. به طور رسمی‌تر، x~_My اگر یک وضعیت q‌وجود داشته باشد به طوری که (s,x)Ⱶ_M*(q,e) و (s,y) Ⱶ_M*(q,e).

‍~_M هم یک رابطه هم‌ارزی است. کلاسهای هم‌ارزی آن می‌توانند توسط وضعیتهای M‌شناسایی شوند.- با آن وضعیتها که از s‌ قابل دسترسی هستند و بنابراین حداقل یک رشته در کلاس هم‌ارزی مرتبط دارند. کلاس هم‌ ارزی مرتبط با وضعیت q  از M ‌را بانماد Eq ‌ نشان می‌دهیم.

مثال 1-5-2:(ادامه) مثلا برای ماشین M شکل 20-2 ، کلاسهای هم‌ارزی اینها هستند: (زبان پذیرفته شده توسط M ،L=(ab∪ba)*‌ است.)

(1) Eq₁ = (ba)* ,

(2) Eq₂ = La ∪ a ,

(3) Eq₃ = abL ,

(4) Eq₄ = b(ab)* ,

(5) Eq₅ = L(bb ∪ aa)∑* ,

(6) Eq₆ = abLb.

‌از طرف دیگر هر کدام از آنها قسمتی از ∑* را شکل می‌دهند.

این دو رابطه هم‌ارزی مهم،‌یکی وابسته به زبان و دیگری وابسته به ماشین، به شکل زیر مرتبط می‌شوند:

قضیه 1-5-2: برای هر ماشین متناهی قطعی M={K,∑,&,s,F} و هر رشته x,y∈∑* ، اگر x~_My،‌در نتیجه x≈_L(M)y.

اثبات: برای هر رشته x∈∑*،‌ q(x)∈K ‌را به صورت وضعیت منحصر به فردی در نظر بگیرید به طوری که (s,x) Ⱶ_M*(q(x),e). توجه کنید که برای هر x,z∈∑* ،‌xz∈L(M) اگر و فقط اگر به ازای یک f∈F داشته باشیم: (q(x),Z) Ⱶ_M*(f,e). حالا اگر x~_My ،‌پس با توجه به تعریف ~_M، q(x)=q(y) و بنابراین  x~_My‌به طور ضمنی به نتیجه زیر اشاره می‌کند: { به ازای همه z∈∑* ، xz∈L(M) ‌ اگر و فقط اگر yz∈L(M) } که همان x≈_L(M)y‌ است.

برای بیان واضحتر قضیه 1-5-2 می‌توانیم بگوییم که ~_M‌ اصلاح‌شده _L(M)‌≈ است. به طور کلی،‌میگوییم:‌رابطه هم‌ارزی ~‌ اصلاح‌شده ≈ ‌است به ازای همه x,y‌ها، x~y‌ به طور ضمنی نشان‌دهنده x≈y هم باشد.اگر ~‌ اصلاح‌شده ≈ ‌است، پس هر کلاس هم‌ارزی ~‌حداقل در یک کلاس هم‌ارزی ≈ ‌وجود دارد. یعنی،‌هر کلاس هم‌ارزی ≈‌اجتماعی از یک یا چند رابطه هم‌ارزی ~‌ است.مثلا رابطه هم‌ارزی‌ای که هر دو شهر واقع در یک استان ایالات متحده را با هم مرتبط میکند، اصلاح‌شده رابطه هم‌ارزی‌ای است که هر دو شهر واقع در یک ایالت را با هم مرتبط میکند.

مثال 1-5-2: (ادامه) بعنوان مثالی بهتر،‌کلاس هم‌ارزی ~_M‌  برای ماشین شکل 20-2، با توجه به این مفهوم،‌کلاس هم ‌ارزی _L(M) ≈  را ،‌دقیقاً‌همانطور که در قضیه 1-5-2 پیش‌بینی شده،‌اصلاح کرده است. مثلاً کلاسهای Eq₅ و [aa] با هم منطبقند در حالی که کلاسهای Eq₁‌و Eq₃‌هر دو زیرمجموعه‌های [e]‌ هستند.

قضیه 1-5-2 ضمناً‌به مسائل خیلی مهمی در مورد M‌ و یا هر ماشین M‌ دیگری که همان زبان L(M) را بپذیرد، اشاره می‌کند: تعداد وضعیتها باید حداقل به اندازه کلاسهای هم‌ارزی L(M) تحت ≈ ‌باشد.به عبارت دیگر،‌تعداد کلاس‌های هم‌ارزی L(M) یک حد پایین ذاتی برای تعداد وضعیتهای M است.آیا می‌توان به این حد پایین رسید؟ بعداً نشان خواهیم داد که واقعاً می‌توان.

قضیه 2-5-2: (قضیه Myhill-Nerode)

L⊆∑* را به عنوان یک زبان منظم در نظر بگیرید. یک ماشین متناهی قطعی ،‌دقیقا"ً با تعداد وضعیتهای مساوی با تعداد کلاسهای هم‌ارزی _L≈ ،که L‌ را می‌پذیرد.

اثبات: قبلاً کلاسهای هم‌ارزی رشته x∈∑*  متعلق به کلاسهای هم‌ارزی _L≈ را با نماد [x] نشان دادیم. با داشتن L ،‌یک ماشین متناهی قطعی(ماشین استاندارد برای L) M={K,∑,&,s,F}را به طوری خواهیم ساخت که L=L(M). M به صورت زیر تعریف شده است:

K-{[x]: x∈∑*} :‌ مجموعه کلاسهای هم‌ارزی تحت _L≈

s=[e] : کلاس هم‌ارزی e تحت _L≈

F={[x]: x∈L}

در نهایت برای هر [x]∈K و هر a∈∑*، تعریف می‌کنیم: &([x],a)=[xa]

چگونه بفهمیم که مجموعه K متناهی است؟‌یعنی _L≈ تعداد کلاسهای هم‌ارزی محدودی دارد؟ L منظم است،‌و همچنین مطمئناً‌توسط حداقل یک ماشین متناهی قطعی M` پذیرفته می‌شود. با استفاده از قضیه قبل، M` اصلاح‌شده _L‌≈ است،‌و همچنین تعداد کلاسهای هم‌ارزی L‌کمتر از تعداد کلاسهای هم‌ارزی ~<sub>M`</sub> است – یعنی تعداد وضعیتهای M`. بنابراین  K‌ یک مجموعه متناهی است. همچنین باید &‌ را خوش‌تعریف بدانیم،‌یعنی قطع نظر از ایکه رشته x∈[x] ،‌&([x],a)=[xa] .اما این موضوع واضح است زیرا x ≈_Lx` اگر و فقط اگر xa ≈<sub>L</sub>x`a.

سپس نشان می‌دهیم که L=L(M). اول نشان میدهیم که برای همه x,y∈∑*‌ داریم: ([x],y)Ⱶ_M*([xy],e)  (رابطه (1))

این موضوع با استقرا روی |y|‌ ثابت می‌شود. رابطه (1) اثبات را تکمیل می‌کند:‌برای همه x∈∑* ،‌داریم x∈L(M)‌اگر و فقط اگر حداقل به ازای یک q∈F داشته باشیم: ([e],x) Ⱶ (q,e) که با توجه به رابطه (1) مثل این است که بگوییم:‌[x]∈F و یا با توجه به تعریف F ،‌[x∈F].

مثال 1-5-2: (ادامه) ماشین استاندارد مربوط به زبان L=(ab∪ba)* که توسط ماشین متناهی قطعی 6-حالته شکل 20-2 پذیرفته می‌شود، در شکل 21-2 نشان داده شده است.این ماشین 4 حالت دارد.مسلماً‌این کوچکترین ماشین متناهی قطعی است که این زبان را می‌پذیرد.

قضیه 2-5-2 بطور ضمنی به توصیف زیر از زبانهای منظم ، که گاهی اوقات قضیه Myhill-Nerode  نامیده می‌شود،اشاره می‌کند:

نتیجه: زبان L منظم است اگر و فقط اگر _L≈ کلاسهای هم ‌ارزی محدودی داشته باشد.

اثبات:‌اگر L منظم باشد، به ازای حداقل یک ماشین متناهی غیرقطعی L=L(M) ، و تعدداد وضعیتهای M حداقل به اندازه کلاسهای هم‌ارزی متعلق به _L≈ است.

به طور معکوس، اگر _L≈ تعداد کلاسهای هم‌ارزی محدودی داشته باشد، ماشین متناهی قطعی M‌ استاندارد(اثبات قضیه 2-5-2 را به یاد آورید.) ،‌زبان L  را می‌پذیرد.مثال 2-5-2:‌نتیجه مذکور فقط  یک پیشنهاد جالب توجه برای تشخیص منظم بودن یک زبان ارائه می‌کند.بعلاوه، روش مفید دیگری برای اثبات منظم نبودن یک زبان ارائه می‌کند.- در کنار قضیه پامپینگ. مثلاً ،‌این یک اثبات برای منظم نبودن L={aⁿbⁿ: n≥1} است:‌هیچ دو رشته aⁱ, bⁱ که i≠j ،‌تحت ≈ معادل نیستند،‌زیرا رشته‌ای وجود دارد (مثل bⁱ) که وقتی به aⁱ ملحق میشود، رشته‌ای متعلق به L‌ حاصل میشود،‌ولی وقتی به a^j‌الحاق می‌شود،‌حاصل رشته‌ای نامتعلق به L‌است. بنابراین _L≈ تعداد نامحدودی کلاس هم‌ارزی [a],[aa],[aaa],… دارد و از این رو  و برطبق نتیجه گفته شده، L نامنظم است.

برای هر زبان منظم L ماشین ساخته شده در اثبات قضیه 2-5-2 ماشین قطعی با کمترین تعداد وضعیت است که L را می‌پذیرد.-یک موضوع مهم کاربردی و بدیهی. متاسفانه، این ماشین در ارتباط با کلاسهای هم‌ارزی ≈_L تعریف شده است ،‌و واضح نیست که آیا این کلاسهای هم‌ارزی می‌توانند برای هر زبان دلخواه منظم L شناسایی شوند؟- مخصوصاً‌اگر L در ارتباط با یک ماشین متناهی M داده شده باشد.ما بعداً الگوریتمی برای ساخت این ماشین مینیمال ، با شروع از هر ماشین متناهی قطعی M  که L=L(M) ، ارائه می‌دهیم.

M={K,∑,&,s,F} را به عنوان یک ماشین متناهی قطعی در نظر بگیرید.رابطه A_M⊆k*z*‌به صورت (q,w)∈A_M تعریف می‌شود اگر و فقط اگر به ازای حداق یک f∈F داشته باشیم (q,w)Ⱶ_M*(f,e) ؛ به عبارت دیگر،(q,w) ∈A_M به این معناست که اشتقاق w در ماشین M با شروع از وضعیت q  ، به یک وضعیت پذیرش میرسد.بیایید دووضعیت p,q را معادل بنامیم و آن را با نماد q≡p نشان دهیم،‌اگر به ازای همه z∈∑* داشته باشیم: (q,z) ∈A_M اگر و فقط اگر (p,z) ∈A_M. بنابراین اگر دو وضعیت معادل باشند،‌کلاسهای هم‌ارزی وابسته به ~_M زیر مجموعه‌ای از کلاسهای هم‌ارزی یکسان هستند. به عبارت دیگر،‌کلاسهای هم‌ارزی ≡ دقیقاً‌همان مجموعه وضعیتهایی M هستند که باید با هم دسته‌بندی شوند،به طوری که ماشین استاندارد L(M) به دست آید.*

الگوریتم محاسبه کلاسهای هم‌ارزی ≡ را توسعه می‌دهیم. الگوریتم ما ≡ را به عنوان تعیین کننده دنباله روابط هم‌ارزی

*رابطه ≡ خارج قسمت تقسیم  _L‌≈ به ~_L نامیده می‌شود. اگر ~  اصلاح شده ≈ باشد،‌خارج قسمت ≈‌ بر ~ - که  با نماد  ‌  /~≈ نشان می‌دهیم- یک رابطه هم‌ارزی روی کلاسهای هم‌ارزی ~ است.دو کلاس [x],[y] از ~ توسط /~≈ با هم رابطه دارند اگر x≈y.- به آسانی دیده می‌شود که این یک رابطه هم‌ارزی است. برای برگشت به مثال جغرافیایی خودمان،‌خارج قسمت رابطه "ایالت یکسان" بر رابطه "استان یکسان" ، هر دو استان(با حداقل یک شهر) را که در یک ایالت هستند به هم مرتبط می‌کند.

₀,≡₁,≡₂,…≡ که بعداً تعریف خواهند شد ،محاسبه خواهد کرد. برای دو حالت p,q ،‌q≡p اگر عبارت زیر در موردشان صدق کند: (q,z) ∈A_M اگر و فقط اگر(p,z) ∈A_M به ازای همه رشته‌های z  به طوری که |z|<+n.

به عبارت دیگر، _n ≡‌ نسبت به ≡ یک رابطه هم‌ارزی صیقل‌یافته است، و فقط مستلزم این است ککه وضعیتهای p,q در رابطه با پذیرش رشته‌هایی با حداکثر n مرحله اشتقاق رفتار یکسانی داشته باشند.

به طور واضح‌تر، هر رابطه هم‌ارزی ₀,≡₁,≡₂,… ≡ اصلاح شده رابطه قبل از خود است.همچنین، q≡₀p نشان‌دهنده این است که یا هر دوی آنهاحالتهای نهایی هستند و یا هیچکدام حالتهای نهایی نیستند. یعنی دقیقاً‌دو کلاس هم‌ارزی ≡ وجود دارد: F و K-F(فرض کنید هیچ کدام تهی نیستند.).حالا باید چگونگی وابستگی _n+1≡ را به _n‌≡ نشان دهیم.

لم 1-5-2: برای هر دو وضعیت p,q∈K‌و هر عدد n≥1،‌داریم: q≡_np اگر و فقط اگر

(a)    Q≡_n-1p

(b)   به ازای هر a∈∑،‌&(q,a)≡_n-1&(p,a).

اثبات:‌بر طبق تعریف _n≡ ،‌q≡np‌ اگر و فقط اگر q≡_n-1p ، و بنابراین هر رشته w=au با دقیقاً n‌ مرحله اشتقاق یا توسط هر دو حالت p,q پذیرش می‌شود و یا توسط هیچ کدام پذیرفته نمی‌شود.بنابراین شرط دوم مثل این است که بگوییم به ازای هر a∈∑ :&(q,a)≡_n-1&(p,a).

لم 1-5-2 میگوید که ما می‌توانیم ≡ را ،‌و از روی آن ماشین استاندارد زبان L‌ را توسط الگوریتم زیر محاسبه کنیم:

در ابتدا کلاسهای هم‌ارزی ₀≡ را با F و K-F  مقداردهی اولیه کن.

برای  n=1,2,…‌تکرار کن:

کلاسهای هم‌ارزی _n‌≡ را از روی _n-1≡ محاسبه کن،

تا وقتی که _n‌≡ دقیقاً‌ همان _n≡ شود.هر تکرار میتواند با اعمال لم 1-5-2 انجام شود.برای هر جفت از وضعیتهای M، تست می‌کنیم که آیا شرایط لم برقرار هستند، و اگر برقرار بودند هر دو وضعیت را در کلاس هم‌ارزی _n ≡ قرار می‌دهیم.اما از کجا بفهمیم که این یک الگوریتم است؟یعنی اینکه تکرارها سرانجام پایان می‌یابند؟پاسخ ساده است: در هر تکرار ،‌برای هر کدام از انتقالها اگر _n≠≡_n-1≡  باشد،‌شرط پاین براورده نمی‌شود و _n≡ یک اصلاح کننده صحیح _n-1≡ است،‌و بنابراین حداقل یک کلاس هم‌ارزی بیشتر از _n-1‌≡ وجود دارد. از آنجا که تعداد کلاسهای هم‌ترزی نمی‌توانند بیشتر از تعداد وضعیتهای M‌باشند،‌الگوریتم حداکثر پس از |k|-1 تکرار به پایان می‌ر در پایان الگوریتم، در nامین تکرار هستیم و _n=≡_n-1≡  محاسبه شده است و لم همچنین به طور ضمنی نشان می‌دهد که _n=≡_n+1=≡_n+2=…≡،‌بنابراین رابطه محاسبه شده دقیقاًهمان ≡ است.در بخش بعدی تحلیل دقیقتری از پیچیدگی این الگوریتم مهم ارائه می‌دهیم و نشان می‌دهیم که این الگوریتم از مرحله چند جمله‌ای است.

مثال 3-5-2: بیایید الگوریتم کمینه‌سازی وضعیت را به ماشین متناهی قطعی M شکل 20-2 اعمال کنیم.(البته با کمک مثال قبلی ، میدانیم که چه چیزی در انتظارمان است: ماشین استانددارد چهار حالته برای L(M)).) در تکرارهای قبلی ما این کلاسهای هم‌ارزی مرتبط با _i‌≡ را خواهیم داشت: در ابتدا،‌کلاسهای هم‌ارزی  ₀≡، {q₁,q₃} و {q₂,q₄,q₅,q₆} هستند. بعد از تکرار اول کلاسهای ₁≡ ، {q₁,q₃},{q₂},{q₄,q₆},{q₅} هستند. شکسته شدن‌ها به دلیل اینکه  &(q₂,b)     ₀ &(q₄,b),&(q₅,b) و &(q₄,a)    ₀&(q₅,a) اتفاق می‌افتند.

بعد از تکرار دوم، هیچ یک از کلاسها تقسیم نمیشوند. بنابراین الگوریتم پایان می‌پذیرد و ماشین با کمترین وضعیت در شکل 22-2 نشان داده شده است.همانطور که انتظار داشتیم،‌این ماشین همریخت با ماشین استاندارد شکل 21-2 است.