سلام
این سوال من واسش یه ماشین رسم کردم که در ضمیمه آوردم
اشتباهش کجاست؟
مرسی
سلام.
میشه یه dfa با ۶ حالت و یا nfa با ۵ حالت ساخت. nfa:
[tex]\delta (q_0,0) \to q_1[/tex]
[tex]\delta (q_0,1) \to q_2[/tex]
[tex]\delta (q_1,1) \to q_2[/tex]
[tex]\delta (q_2,0) \to q_1[/tex]
[tex]\delta (q_2,1) \to q_3[/tex]
[tex]\delta (q_3,0) \to q_4[/tex]
[tex]\delta (q_3,1) \to q_3[/tex]
[tex]\delta (q_4,1) \to q_3[/tex]
[tex]\delta (q_0,1) \to q_2[/tex]
[tex]\delta (q_1,1) \to q_2[/tex]
[tex]\delta (q_2,0) \to q_1[/tex]
[tex]\delta (q_2,1) \to q_3[/tex]
[tex]\delta (q_3,0) \to q_4[/tex]
[tex]\delta (q_3,1) \to q_3[/tex]
[tex]\delta (q_4,1) \to q_3[/tex]
که q0 حالت شروع و q3 و q4 حالت پایانیه. منظور از شناسایی رو نمیدونم.
(۲۷ دى ۱۳۹۰ ۰۲:۵۵ ب.ظ)Lakikharin نوشته شده توسط: منظور از شناسایی رو نمیدونم.
منظور همون حالت نهاییه
اگر باید ماشین متناهی کامل رسم کنیم دارای ۶ وضعیت خواهیم بود با دو وضعیت نهایی
[tex]\delta (q0,1)=q1,\delta(q0,0)=q3,\\ \delta(q1,1)=q2,\delta(q1,0)=q3,\\ \delta(q2,1)=q2,\delta(q2,0)=q4\\ \delta(q3,1)=q0,\delta(q3,0)=qe\\ \delta(q4,1)=q2,\delta(q4,0)=qe\\ \delta(qe,1)=qe, \delta(qe,0)=qe[/tex]
که در ماشین بالا q2 و q4 حالت نهایی هستند
نکتهی این سوال اینه که نباید برای nfa کمینه، حالت trap در نظر بگیریم،، چیزی که من تا الان نمیدونستم، خوب شد که این سوال گذاشتید، ممنون
بچهها من یه ماشین با ۵ وضعیت و دو حالت نهایی کشیدم. عیبش چیه؟
(۲۷ دى ۱۳۹۰ ۰۸:۲۵ ب.ظ)Ali-B نوشته شده توسط: نکتهی این سوال اینه که نباید برای nfa کمینه، حالت trap در نظر بگیریم،، چیزی که من تا الان نمیدونستم، خوب شد که این سوال گذاشتید، ممنون
راستی این برام سوال بود در کجا باید trapها هم لحاظ بشوند؟
توی nfa که کشیدم میتونین یه q5 اضافه کنین که با ۰ و ۱ به خودش میره و از q4 و q1 میشه به q5 رفت. اگه این حالت و ۴ حرکت رو اضافه کنین dfa میشه.
nfa شما اشتباهه. رشته هایی که فقط ۱ دارن رو قبول نمیکنه.
(۲۸ دى ۱۳۹۰ ۱۲:۴۴ ق.ظ)پشتکار نوشته شده توسط: بچهها من یه ماشین با ۵ وضعیت و دو حالت نهایی کشیدم. عیبش چیه؟
ایراد داره، اون حلقهها که یک میگیرن برای چی هستن؟ اصلا نیازی به این کار نیست.
خب بعد از رسم با چند تا مثال ساده امتحانش کنید، مثلا سادهترین رشته ۱۱ هست، که این ماشین قبولش نمیکنه!
(۲۸ دى ۱۳۹۰ ۱۲:۴۴ ق.ظ)پشتکار نوشته شده توسط: راستی این برام سوال بود در کجا باید trapها هم لحاظ بشوند؟
نمیدونم، ولی یادمه تو یه سوال نوشته بود که در نظر نگیرید، البته فکر کنم dfa میخواست، نه nfa.
فرمولی برای رسم ماشین نیست؟
(۲۸ دى ۱۳۹۰ ۰۱:۰۵ ق.ظ)Ali-B نوشته شده توسط: ایراد داره، اون حلقهها که یک میگیرن برای چی هستن؟ اصلا نیازی به این کار نیست.
چرا نیازی نیست؟ نباید تمامی حالات رو در نظر بگیریم؟
خب اگه از اولین حالت یه اتصال به نقطه نهایی با مقدار یک بکشیم مشکل حله؟
اون موقع رشته ۱ رو قبول میکنه. نمیدونم مشکلتون با dfa و nfa که نوشتم چیه؟!؟!
(۲۸ دى ۱۳۹۰ ۰۵:۱۳ ب.ظ)Lakikharin نوشته شده توسط: اون موقع رشته ۱ رو قبول میکنه. نمیدونم مشکلتون با dfa و nfa که نوشتم چیه؟!؟!
من مشکلی ندارم دوست عزیز
فقط سوالم اینه چرا هرچی ماشین طراحی می کنم همه میگن اشتباهه
بعضی موقع شرایط خاص وجود داره که برای ماشینی که طراحی میکنیم پیش بینی نکردیم. بعضی موقع هم حواسمون به یه حالت خاص پرت میشه و برای رفع اون یه حالت به ماشین اضافه میکنیم که باعث اشتباهات جدید میشه. معمولاً این اشتباهات توی nfa بیشتر اتفاق می افته. چون میگیم ماشین ما در یکی از شرایط جواب این رشته خاص رو میده پس درسته. ولی احتمال داره رشته غلط رو هم قبول کنه.
(۲۸ دى ۱۳۹۰ ۱۱:۳۶ ب.ظ)Lakikharin نوشته شده توسط: بعضی موقع شرایط خاص وجود داره که برای ماشینی که طراحی میکنیم پیش بینی نکردیم. بعضی موقع هم حواسمون به یه حالت خاص پرت میشه و برای رفع اون یه حالت به ماشین اضافه میکنیم که باعث اشتباهات جدید میشه. معمولاً این اشتباهات توی nfa بیشتر اتفاق می افته. چون میگیم ماشین ما در یکی از شرایط جواب این رشته خاص رو میده پس درسته. ولی احتمال داره رشته غلط رو هم قبول کنه.
شما چیکار کردید؟
فرمول ثابتی نداره؟ بشه راحت بدست آورد؟
همونطور که جواب ثابت نداره فرمول ثابت هم نداره. توی هر مرحله باید درنظر بگیرین که با چه رشته هایی میتونه به ون حالت رسیده باشه. مثلا برای فایل ضمیمه شما اگه شماره هارو به ترتیب بگیریم:
q0 شامل یه تعداد ۱ هست (حداقل تعداد برابر ۰)
q1 شامل یه تعداد ۰ و ۱ هست که ۲ تا ۰ پشت سرهم نداره (حداقل یه ۰ داره و میتونه ۱ نداشته باشه) ولی معلوم نیست آخرین حرفش صفر یا یکه
q2 شامل یه تعداد ۰ و ۱ هست که ۲ تا ۰ پشت سرهم نداره (حداقل یه ۰ داره) و آخرین حرفش یکه
q3 شامل یه تعداد ۰ و ۱ هست که "۱۱" داره ولی ۲ تا ۰ پشت سرهم نداره (حداقل یه ۰ و دوتا ۱ داره) و آخرین حرفش یکه
q4 شامل یه تعداد ۰ و ۱ هست که "۱۱" داره ولی ۲ تا ۰ پشت سرهم نداره (حداقل دوتا ۰ و دوتا ۱ داره) و آخرین حرفش صفره
اگه دقت کنین رشته هایی که فقط شامل ۱ هستن رو قبول نمیکنه. پس یا حرکتهاتون درست نبود و یا حالتهاتونو درست انتخاب نکردین. درکل برای هرسوال باید حالتهایی رو درنظر بگیرین که همه حالتهای رشته ورودی رو درنظر بگیره و راه انتقال به حالت پایانی رو هم از همه حالات چک کنین.