(۰۴ آذر ۱۳۹۵ ۱۲:۴۴ ب.ظ)mostafaheydar1370 نوشته شده توسط: سلام خدمت دوستان
سوال و جواب مدرسان رو پیوست کردم ولی جوابی که مدرسان به این سوال داده ی کم غیر قطعیه یعنی نمیشه روش حساب کرد کسی میدونه جواب این سوال رو جطور میشه با قطعیت داد یعنی با اثبات ریاضی حلش کرد ؟
سوال
جواب
سلام . برای حل این سوال با روش رد گزینه و دونستن این نکته که کمینه بودن یه DFA چجوری میشه و چطوری این کارو میکنن گزینه ۴ رو انتخاب کرد .
رد گزینه ۱ : به عنوان مثال رشته ab رو قبول نمیکنه.
رد گزینه ۲ : این FSA
اصلا یک DFA نیست و یک NFA است ( به State اول نگاه کن !) ( ۲ تا a خارج شده ).
پس بررسیش نمیکنیم .
میمونه گزینه ۳ و ۴ : میدونیم که DFA برای یک عبارت منظم همیشه
یونیک نیست . از طرفی هم صورت سوال DFA کمینه ( با کمترین حالات ممکن ) رو خواسته ، شما هر رشته ای که ممکن است رو به گزینه ۳ و ۴ بده همشو قبول میکنه ، اما آیا گزینه ۳ یک DFA بهینه است ؟
در واقع اگه الگوریتم کاهش حالت رو روی گزینه ۳ بزنی به گزینه ۴ ( بهینه شده ) میرسی . مراحل کمینه کردن گزینه ۳ رو تو فایل پیوست ببینید .