سلام
وقت بخیر
لطفا عکس ببینید
تشکر
سلام
این ماشین هیچ ایرادی نداره
ماشین که مشکلی نداره ولی میشه واسه سادگی از حالت trap هم صرف نظر کرد (حالت q1 )
تشکر
این الان گراف dfa یا nfa و چرا
nfa
چون باید از فاینالت با a وb بری به trapتا بشه dfa
سلام. این گراف یک nda چون از q2 با a به دو حالت q2 و q3 میره. برای تبدیل به dfa میتونید انتقال از q2 به خودش با b رو حذف کنید و یک یال از q3 به q2 با b و یک یال از q3 به خودش با a رو اضافه کنید.
این گراف nfa است و dfa آن به صورت زیر است :
سلام
تشکر
دلیل حذف a از q2 که مشخصه
اما چرا یال q3 بهq2 با حرف b ست و a نیست
و چرا روی راس پایانی یک طوقه گذاشته شده اونهم با حرف a ؟
(31 تير 1393 06:00 ب.ظ)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 یال داشته باشیم.