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