سلام
برای تبدیل یک NFA به DFA باید جدول حالت کشید
من اینها رو خوب بلد بودم اما چند سال گذشته ازش.
امکان داره بفرمائید جدول حالت رو بر چه اساس میکشیم؟
سلام. باید ببینید از هر حالت با هر حرکت به کدوم مجموعه از حالت ها میتونه بره. درواقع حالت های جدید در dfa یک مجموعه از چند حالت از nfa هستن. به عنوان مثال:
اگه از حالت ۲ با a بتونیم هم به ۳ و هم به ۴ بریم، توی dfa از حالت [tex]\{2\}[/tex] به حالت [tex]\{3,4\}[/tex] میریم.
اگه از حالت ۳ با a به ۸ و ۹ همچنین از ۴ بشه با a به ۳ و ۵ و ۶ رفت، از حالت [tex]\{3,4\}[/tex] میشه به [tex]\{3,5,6,8,9\}[/tex] رفت.
سلام
من یک مثالی دارم که از همه حالات ماشین استفاده نکرده
از ۴ تا state دو تا از وضعیت ها رو ننوشته
کی هست که یک وضعیت رو نمی نویسیم در جدول؟
(۲۱ اسفند ۱۳۹۲ ۰۶:۱۰ ب.ظ)H-Arshad نوشته شده توسط: سلام
من یک مثالی دارم که از همه حالات ماشین استفاده نکرده
از ۴ تا state دو تا از وضعیت ها رو ننوشته
کی هست که یک وضعیت رو نمی نویسیم در جدول؟
عزیزان کمک
متوجه نمیشم منظورتون رو. اگه یه nfa تعداد n حالت داشته باشه dfa متناظر حداکثر ۲ به توان n حالت داره. ولی با ساده سازی میتونه کمتر از n حالت هم داشته باشه. روال کاریش به همون شکلیه که گفتم. از هر مجموعه از حالت ها به یه مجموعه ای از حالت ها میریم. اگه یکی از اعضای اون مجموعه پایانی بود اون حالت پایانی میشه.