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

B و C زبان هایی بر روی {Σ = {0,1 هستند . تعریف میکنیم

شکست در تجزیه (خطای نحوی): {\displaystyle B <-1 C = { w | وجود دارد y در C به طوریکه رشته های w و y به تعداد مساوی ۱ داشته باشند . }

نشان دهید که کلاس زبان های منظم بر روی عمل گر ۱-> بسته است .

حل :

زبان های B و C منظم هستند بنا بر این برای آن ها DFA وجود دارد . حال DFA مربوط به C را به این صورت تغیر میدهیم که به هر یال آن که مقدار 0 دارد یک اپسیلون اضافه کرده و از هر حالت نیز یک فلش خارج کرده و به خود آن با مقدار 0 وارد میکنیم . با این کار DFA مربوط به C را به یک NFA تبدیل کردیم که مثلا اگر رشته ۱۰۱ در C وجود داشته باشد این NFA تمام رشته هایی را که در آنها دقیقا دو ۱ وجود داشته باشد را نیز قبول میکند . حالا این NFA را به DFA معادل تبدیل کرده و آن را به حالت intersection با DFA مربوط به B ترکیب میکنیم چرا که رشته مورد نظر باید در B هم قبول شود . بنا بر این با این کار توانستیم برای B ->1 C یک NFA پیدا کنیم در نتیجه این زبان منظم است . پس کلاس زبان های منظم تحت عمل گر مورد نظر بسته هستند .