حل تمرین نظریه محاسبات/فصل اول/حل تمرین1-24
ظاهر
حل تمرین 1-24
تمرین
[ویرایش]برای همه رشتههای مانند: w=w1w2...wn معکوسشان را با wR نشان می دهیم که به صورت: wR=wn...w2w1 است. حال ثابت کنید برای هر زبان منظم مانند A ، معکوس آن هم منظم است.
حل
[ویرایش]فرض می کنیم برای زبان منظم A یک nfa می سازیم که ثابت شده است این کار در هر حالت امکان دارد. در گراف مربوط به این nfa راس نهایی را اولیه و جهت تمامی یالها را معکوس می کنیم. به سادگی می توان نشان داد که اگر و فقط اگر nfa اولیه w را بپذیرد nfa تغییر یافته هم wR را می پذیرد. بنابراین nfa تغییر یافته LR را میپذیرد.