حل تمرین ۱-۹

تمرین

ویرایش

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

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

Aida AsghariFard