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