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

حل تمرین 1-24

تمرین

برای همه رشته‌های مانند: w=w1w2...wn معکوسشان را با wR نشان می دهیم که به صورت: wR=wn...w2w1 است. حال ثابت کنید برای هر زبان منظم مانند A ، معکوس آن هم منظم است.

حل

فرض می کنیم برای زبان منظم A یک nfa می سازیم که ثابت شده است این کار در هر حالت امکان دارد. در گراف مربوط به این nfa راس نهایی را اولیه و جهت تمامی یال‌ها را معکوس می کنیم. به سادگی می توان نشان داد که اگر و فقط اگر nfa اولیه w را بپذیرد nfa تغییر یافته هم wR را می پذیرد. بنابراین nfa تغییر یافته LR را می‌پذیرد.