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

B و C زبان هایی بر روی {Σ = {0,1 هستند . تعریف میکنیم                      
 
<math> B <-1 C = { w | وجود دارد y در C به طوریکه رشته های w و y به تعداد مساوی ۱ داشته باشند . </math>
        
نشان دهید که کلاس زبان های منظم بر روی عمل گر ۱-> بسته است . 


حل : 


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