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

حل تمرین 1-25

تمرین

الفبا={[000][001]...[111]}

{سطر سومwمجموع سطور اول و دوم آن باشد|B = {W .نشان دهید B منظم است.(راهنمایی: کار کردن با B^R ساده تر است.از نتیجه مساله1-24 استفاده کنید)

حل

شکل زیر NFA را برای B^R نشان می دهد. چون B^R دارایNFA است پس منظم است . بنابراین چون B^R منظم است پس B نیز منظم است.