سلام
این ماشین هیچ ایرادی نداره

سلام. این گراف یک nda چون از q2 با a به دو حالت q2 و q3 میره. برای تبدیل به dfa میتونید انتقال از q2 به خودش با b رو حذف کنید و یک یال از q3 به q2 با b و یک یال از q3 به خودش با a رو اضافه کنید.

ماشین که مشکلی نداره ولی میشه واسه سادگی از حالت trap هم صرف نظر کرد (حالت q1 )

تشکر
این الان گراف dfa یا nfa و چرا

nfa
چون باید از فاینالت با a وb بری به trapتا بشه dfa

سلام
تشکر
دلیل حذف a از q2 که مشخصه
اما چرا یال q3 بهq2 با حرف b ست و a نیست
و چرا روی راس پایانی یک طوقه گذاشته شده اونهم با حرف a ؟

(۳۱ تیر ۱۳۹۳ ۰۶:۰۰ ب.ظ)s_t_6 نوشته شده توسط:  سلام
تشکر
دلیل حذف a از q2 که مشخصه
اما چرا یال q3 بهq2 با حرف b ست و a نیست
و چرا روی راس پایانی یک طوقه گذاشته شده اونهم با حرف a ؟

با گرفتن اولین a به حالت q2 میریم و در حال خوندن w هستیم. اگه b ببینیم باید توی همین حالت بمونیم چون بعد از w حتماً a میبینیم. با دیدن a فرض میکنیم w تموم شده و a نهایی رو گرفتیم. به حالت نهایی میریم. اگه حرف بعدی رو بگیریم مشخص میشه که فرضمون اشتباه بوده. اگه این حرف جدید b باشه به حالت قبلی برمیگردیم و ادامه w رو میخونیم. اگه این حرف a باشه فرض میکنیم a قبلی جزء w بوده و aی آخری نشون دهنده آخر رشتست.
ما در dfa مجاز به دو خروجی با یک حرف نیستیم. پس نباید از q3 به q2 با a یال داشته باشیم.