سلام . توی کتاب لینز یک تمرین هست که گفته dfa برای زبان زیر رسم کنید . عکسی که زیر میزارم از حل از مسائل هست که من جوابشو قبول ندارم .
![[تصویر: 425745_photo_2016-11-11_14-11-45.jpg]](https://img.manesht.ir/425745_photo_2016-11-11_14-11-45.jpg)
حالا جوابی که من بدست آوردم این هست که البته این جواب رو اول مطمئن نبودم که بعد از یک حل المسائل خارجی پیدا کردم دیدم حداقل جواب من درسته .
![[تصویر: 425745_2016-11-11_14-17-44.png]](https://img.manesht.ir/425745_2016-11-11_14-17-44.png)
اما مشکلی که دارم اینها هست اول با این نوشته در عکس اول که نوشته "زبان L زبانی است که قبل از آخرین a سه کاراکتر و بعد از آخرین a حداکثر ۵ ،b دارد " . به نظر من (البته با اجازه بزرگترا) باید بگه که "زبان L زبانی است که قبل از آخرین a سه کاراکتر و بعد از آخرین a حداکثر ۵ کاراکتر ( چه a و چه b). چون توی تمرین گفته بعد از a حداکثر طول باید ۵ باشه نگفته حداکثر ۵ تا b حتما باید باشه!. کلا هر چی فکر می کنم خیلی از رشته ها اشتباه ممکنه توسط dfa اول قبول بشه . مثلا یک همچین رشته ای aabaaaaaaa نباید پذیرفته بشه هر چند که توسط dfa حل المسائل بنظرم داره پذیرفته میشه . نظر شما چی هست .
بسیار ممنون از وقتی که میزارید.
(۲۱ آبان ۱۳۹۵ ۰۳:۲۷ ب.ظ)MBe نوشته شده توسط: مثلا یک همچین رشته ای aabaaaaaaa نباید پذیرفته بشه هر چند که توسط dfa حل المسائل بنظرم داره پذیرفته میشهچرا؟ این رشته که مشکلی نداره
گفته وسط w1 و w2 یه a باید قرار بگیره مثلا زیررشته اول و دوم رو اینجوری در نظر بگیر
w1=aabaaa--a--w2=aaa میشه رشته ای که نوشتی، یا خیلی حالتهای دیگه......
اتفاقا یه رشته ای بهت میگم با ماشین خودت پیش برو جواب نمیده:
bbbabbbab
خوب از سمت چپ تو ماشین دومی قرار بده با ۳ تا b اول میری به حالتq3 با a بعدی میری به q4 با ۳تا b دیگه میری به q23 بعد با a میری به q24 آخرشم با b میری به حالت آخر که final state نیست ، درصورتی که این رشته عوض زبان هست.
یکم دقت کن احتمالا اولشو خوب متوجه نشده بودی
سلام. وقت بخیر.
هیمنطور که دوستمون آقای signal_micro عنوان کردن، جواب کتاب درسته و جواب شما اشتباهه. اگه یه رشته رو بشه به یه شکلی به w1 و w2 تقسیم کرد، این رشته عضو زبان خواهد بود. کافیه بعد از حرف سوم حداقل یک a داشته باشیم و انتهای رشته، ۵ حرف b پیاپی نداشته باشیم.
سلام
ببخشید مگه ۵=> |W2| این DFA که رشته هایی با طول بیشتر از ۵ رو هم در قسمت W2 میگیرد؟
(۲۲ آبان ۱۳۹۵ ۱۱:۱۳ ب.ظ)Alirezaj نوشته شده توسط: سلاممن که W1 و W2 رو جدا کردم برات
ببخشید مگه ۵=> |W2| این DFA که رشته هایی با طول بیشتر از ۵ رو هم در قسمت W2 میگیرد؟
مشکلش چیه؟اگر مثلا میگفت بین W1 و W2 فرضا یه حرف c هست که از الفبای W1 و W2 نیست خیلی راحت بود و راه حل شما درست بود تقریبا ، ولی اینجا یه a وسط افتاده الان من رشته شما رو برات به شکلی چیندم که عضو زبان شد مشکلش کجاست؟
ببخشید !فکر کنم سوال من رو خوب متوجه نشدید!
۵>=|W2|
برای مثال:
اگر توجه کنید از گذرq4 به q5 با حرف a ,b یک حلقه ایجاد شده که باعث میشه رشته هایی با طول بیش از ۵ رو هم این ماشین بپذیره که با تعریف زبان تناقض داره!!!؟؟
(۲۳ آبان ۱۳۹۵ ۱۲:۰۲ ق.ظ)Alirezaj نوشته شده توسط: ببخشید !فکر کنم سوال من رو خوب متوجه نشدید!رشتشو بگو چک کنم
۵>=|W2|
برای مثال:
اگر توجه کنید از گذرq4 به q5 با حرف a ,b یک حلقه ایجاد شده که باعث میشه رشته هایی با طول بیش از ۵ رو هم این ماشین بپذیره که با تعریف زبان تناقض داره!!!؟؟
ایرادش چیه؟ حلقه باعث میشه هر بار که رشته a اومد انگار دوباره همه چیزایی که تا حالا نوشتی به زیررشته۱ اضافه شد(چون زیررشته۱سقف که نداره حداقل باید ۳ تا باشه که هست ) باز از b بعدی به زیررشته۲ وارد میشیم
امیدوارم مشکلت رفع شه
abaabababa
این رشته نباید پذیرفته بشه.که پذرفته میشه!!!
(۲۳ آبان ۱۳۹۵ ۱۲:۲۰ ق.ظ)Alirezaj نوشته شده توسط: abaabababaواسه چی ببین من چجوری تقسیمش میکنم
این رشته نباید پذیرفته بشه.که پذرفته میشه!!!
w1=abaab و بعد از این هم حرف a بعد هم w2=baba
چیزی نقض شد؟ w1 تعدادش از ۳ بیشتره درست؟ w2 هم از ۵ کمتر وسطشم حرف هست
این مشکلش چیه؟
حل دیگه
بله.حل شد .ممنون
DFA عکس کاملا درست.
(۲۳ آبان ۱۳۹۵ ۱۲:۲۵ ق.ظ)Alirezaj نوشته شده توسط: بله.حل شد .ممنونخدا رو شکر
DFA عکس کاملا درست.