حل تمرین نظریه محاسبات-ویرایش دوم/فصل اول/حل تمرین۱-۱۱

سوال 1.11 از ویرایش دوم کتاب مقدمه‌ای بر نظریه محاسبات - مایکل سیپسر

مسئله :

ثابت کنید که هر NFA را می توان به یک NFA معادل که فقط یک حالت پذیرش داشته باشد تبدیل کرد.

پاسخ:

فرض کنید هر NFA مانند N با تعریف (N=(Q,Ʃ,δ,q₀,F داشته باشیم ، حال یک NFA مانند M خواهیم ساخت که فقط یک حالت پذیرش داشته و همان زبانی را که ماشین N می پذیرد قبول کند . به زبانی دیگر ، ماشین M دقیقا مانند ماشین N خواهد بود با این تفاوت که ماشین M تعدادی انتقال تهی از حالات پذیرش ماشین N به یک حالت پذیرش جدید به نام q_accept خواهد داشت. حالت q_accept هیچ انتقالی به حالات دیگر ندارد . به زبان ریاضی می توان گفت که ({M=(Q ∪ {q_accept}, Ʃ, δ^´, q₀, {q_accept به گونه ای که برای هر q∈Q و a∈Ʃ خواهیم داشت :

$\delta '(q,a)={\begin{cases}\delta (q,a)&{\text{if }}a\neq \epsilon {\text{ or }}q\notin F\\\delta (q,a)\cup \{q_{\text{accept}}\}&{\text{if }}a=\epsilon {\text{ and }}q\in F\end{cases}}$

همان گونه که گفته شد هیچ انتقالی از حالت پذیرش به حالات دیگر وجود نخواهد داشت یعنی به ازای هر a ∈ Ʃ_ϵ داریم

δ^´(q_accept , a)=ø

منبع سوال : کتاب مقدمه ای بر نظریه محاسبات اثر مایکل سیپسر ، ویرایش دوم ، صفحه 85

منبع پاسخ : کتاب مقدمه ای بر نظریه محاسبات اثر مایکل سیپسر ، ویرایش دوم ، صفحه 95