پرش به محتوا

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

ویکی‎کتاب، کتابخانهٔ آزاد

حل تمرین 1-42

تمرین

[ویرایش]

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

دانلود صورت ریاضی 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، که در آن:

[[۱]]