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

ویکی‎کتاب، کتابخانهٔ آزاد
پرش به ناوبری پرش به جستجو

سوال :

Show how all the labels in Figure 3.14 were obtained ?

Peterlinz ch3 3.2.12.png Peterlinz figure3.12.png

برای اینکه برچسب های مورد نظر را برای زبان بالا به دست بیاوریم ابتدا می‌بایست چهار حالت برای نشان دادن زوجیت تعداد a یا b دریافت شده در نظر بگیریم. این چهار حالت با OO OE EO EE که O نشاندهنده ی تعداد فرد و E نشاندهنده ی تعداد زوج است در شکل ۱۳.۳ کتاب مشخص شده اند. سپس شروع به حذف حالات و جایگزین کردن برچسب ها با عبارت های مناسب میکنیم. به عنوان مثال با حذف OE انتقال از EE به آن را با عبارت aa و انتقال از OO به آن را با عبارت bb جایگزین میکنیم. همین کار را برای حذف OO نیز انجام می‌دهیم که در آن صورت حالت هایی که از EE شروع شده و از OO گذر کرده و دوباره به EE باز میگردد شامل ab(bb)*ba خواهد بود و با aa که از قبل وجود داشت اجتماع گرفته خواهد شد. یعنی :

r1 = aa + ab(bb)*ba

اما از طرفی با حذف OO انتقال هایی که از EE به EO انجام می‌شد را اکنون می‌توان با b که از قبل وجود داشت و یا با a(bb)*a (برای حالت هایی که از OO رد می‌شد) انجام داد که اجتماع این دو نتیجه می‌دهد :

r2 = b + a(bb)*a