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

سوال :

Show how all the labels in Figure 3.14 were obtained ?

برای اینکه برچسب های مورد نظر را برای زبان بالا به دست بیاوریم ابتدا می‌بایست چهار حالت برای نشان دادن زوجیت تعداد 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