[attachment=17480]دوستان سلام
این تصویر گرافی که الان می ذارم رو طبق کتاب پیتر لینز تا کشیدن dfa با همه ی رئوس میرم ، اما تو کم کردن تعداد رئوس گیر می کنم. میشه از اون مرحله به بعدش رو بهم بگین چی میشه و باید چکار کرد؟
با تشکر
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
شکل dfa معادل و dfa کمینه را گذاشته ام و روش کمینه کردن هم خیلی کوتاهه
اولا اون final state با هیچ state دیگری برابر نیست چون اون دو تا غیر فاینال هستند و اون q1,2 فاینال است
اما در مورد دو state دیگر q0 با ۰ می ره به q1,2
از طرفی q0,2 هم با ۰ می ره به q1,2
پس تا اینجا عملکرد این دوتا با هم مساویه اما باید به ازای ورودی ۱ هم مقایسه بشن
q0 با ۱ می ره به q1,2
از طرفی q0,2 هم با ۱ می ره به q1,2
پس کلا از q0 با هر ورودی ای به هر جا که بریم با q0,2 هم با همون ورودی به همون جا می ریم
پس این و state در واقع مثل هم عمل می کنند
پس یکی شون زیادی است و حذفش می کنیم