سلام
عزیزان برای مینمم سازی DFA یک جدول می کشند و بعضا برخی خانه ها رو با تیک یا X علامت میزنند
مبنای این علامت زدن چطوری و بر چه اساسی هست؟ متاسفانه یادم رفته و ۳ سال پیش درس رو پاس کردم
ممنون
(۱۹ خرداد ۱۳۹۳ ۰۵:۴۸ ب.ظ)H-Arshad نوشته شده توسط: سلام
عزیزان برای مینمم سازی DFA یک جدول می کشند و بعضا برخی خانه ها رو با تیک یا X علامت میزنند
مبنای این علامت زدن چطوری و بر چه اساسی هست؟ متاسفانه یادم رفته و ۳ سال پیش درس رو پاس کردم
ممنون
هدف برای این مینمم سازی، کاهش state ها هست. وقتی جدول می کشید باید تمام حالات را در هر سطر بنویسید و در ستون ها هم الفبای مربوط به DFA. بعد جدول رو به این شکل کامل می کنید. مثلا در جدول زیر q1 با دیدن a به q3 میرود و نیز با دیدن b به حالت q2 میرود. اگه دقت کنید حالت q3 نیز رفتاری مثل q1 داره و خب بودن اون در DFA لزومی نداره چون تمامی حالاتی که q3 ایجاد می کنه رو با q1 هم میشه ایجاد کرد. پس میشه به جای این دو حالت q1 و q3 فقط یکی از آنها رو قرار داد و دیگری رو جایگزین کرد. بدون کشیدن جدول نیز میشه حالات رو کاهش داد ولی خب با جدول احتمال خطا کمتره.
----
a b
q0 q3 q2
q1 q2 q1
q2 q2 q2
q3 q2 q1