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

حل تمرین ۱-۱۶

تمرین

با استفاده از روش ارائه شده در لم ۳۲-۱، دو آتوماتای متناهی زیر را به عبارت منظم تبدیل کنید.

• 
  شکل «الف»
• 
  شکل «ب»

حل

• حل قسمت «الف»
• 
  مرحلهٔ اول. دو حالت S و A را اضافه می‌کنیم.
• 
  مرحلهٔ دوم. حالت ۲ را حذف کرده و عبارت منظم معادل را جایگزین می‌کنیم.
• 
  مرحلهٔ سوم. حالت ۱ را حذف کرده و عبارت منظم معادل را جایگزین می‌کنیم.

• حل قسمت «ب»
• 
  مرحلهٔ اول. دو حالت S و A را اضافه می‌کنیم.
• 
  مرحلهٔ دوم. حالت ۳ را حذف کرده و عبارت منظم معادل را جایگزین می‌کنیم.
• 
  مرحلهٔ سوم. حالت ۲ را حذف کرده و عبارت منظم معادل را جایگزین می‌کنیم.
• 
  مرحلهٔ‌چهارم. حالت ۱ را حذف کرده و عبارت منظم معادل را جایگزین می‌کنیم.