پرش به محتوا

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

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

حل تمرین ۱-۹

تمرین

[ویرایش]

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

ابتدا NFA به نام M را در نظر بگیرید. یک حالت پذیرش بنام qnew به آن اضافه کنید. بعد به سراغ هرکدام از حالات قبلی M به جز qnew رفته و :
1- آن را غیر پذیرش کنید.
2- گذار ε از حالت مذکور به qnew اضافه کنید.
بنابراین هر رشته که قابل پذیرش از طرف M باشد، می تواند از طرف ماشین جدید هم پذیرفته شود. اگر M هیچ حالت پذیرشی نداشت، به همین ترتیب حالت گذاری به سمت qnew نخواهد داشت. اما می توان گفت همچنان جزء ماشین جدید است.

Aida AsghariFard