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

حل تمرین 1-42

تمرین

ثابت کنید که اگر A منظم باشد A_1/2 نیز منظم است.

دانلود صورت ریاضی A_1/2

حل

ایده اثبات برای اینکه A_1/2 منظم است در صورتیکه A منظم باشد این است:

- فرض کنید حالت پایانی q عضوی از F است و y به صورتی است که |x| = |y|

- M را به صورت موازی شبیه سازی می کنیم روی x از s به سمت جلو و روی y از q به سمت عقب، و

- اگر هر دو شبیه سازی به یک حالت ختم شدند می پذیریم.

در نظر بگیرید (M = (Q ; ; ;q₀; F یک DFA باشد، به طوریکه L(M) = A. سپس M^' را به صورت (M' = (Q';�; �'; q'0; F' به طوریکه L(M') = A _-1/2، که در آن:

[[۱]]