حل تمرین نظریه محاسبات/فصل اول/حل تمرین1-42
ظاهر
حل تمرین 1-42
تمرین
[ویرایش]ثابت کنید که اگر A منظم باشد A1/2 نیز منظم است.
حل
[ویرایش]ایده اثبات برای اینکه A1/2 منظم است در صورتیکه A منظم باشد این است:
- فرض کنید حالت پایانی q عضوی از F است و y به صورتی است که |x| = |y|
- M را به صورت موازی شبیه سازی می کنیم روی x از s به سمت جلو و روی y از q به سمت عقب، و
- اگر هر دو شبیه سازی به یک حالت ختم شدند می پذیریم.
در نظر بگیرید (M = (Q ; ; ;q0; F یک DFA باشد، به طوریکه L(M) = A. سپس M' را به صورت (M' = (Q';�; �'; q'0; F' به طوریکه L(M') = A -1/2، که در آن:
[[۱]]