۰
subtitle
ارسال: #۱
سال ۸۸
سلام
این سوال من واسش یه ماشین رسم کردم که در ضمیمه آوردم
اشتباهش کجاست؟
مرسی
این سوال من واسش یه ماشین رسم کردم که در ضمیمه آوردم
اشتباهش کجاست؟
مرسی
۰
ارسال: #۲
تست سال ۸۸
همونطور که جواب ثابت نداره فرمول ثابت هم نداره. توی هر مرحله باید درنظر بگیرین که با چه رشته هایی میتونه به ون حالت رسیده باشه. مثلا برای فایل ضمیمه شما اگه شماره هارو به ترتیب بگیریم:
q0 شامل یه تعداد ۱ هست (حداقل تعداد برابر ۰)
q1 شامل یه تعداد ۰ و ۱ هست که ۲ تا ۰ پشت سرهم نداره (حداقل یه ۰ داره و میتونه ۱ نداشته باشه) ولی معلوم نیست آخرین حرفش صفر یا یکه
q2 شامل یه تعداد ۰ و ۱ هست که ۲ تا ۰ پشت سرهم نداره (حداقل یه ۰ داره) و آخرین حرفش یکه
q3 شامل یه تعداد ۰ و ۱ هست که "۱۱" داره ولی ۲ تا ۰ پشت سرهم نداره (حداقل یه ۰ و دوتا ۱ داره) و آخرین حرفش یکه
q4 شامل یه تعداد ۰ و ۱ هست که "۱۱" داره ولی ۲ تا ۰ پشت سرهم نداره (حداقل دوتا ۰ و دوتا ۱ داره) و آخرین حرفش صفره
اگه دقت کنین رشته هایی که فقط شامل ۱ هستن رو قبول نمیکنه. پس یا حرکتهاتون درست نبود و یا حالتهاتونو درست انتخاب نکردین. درکل برای هرسوال باید حالتهایی رو درنظر بگیرین که همه حالتهای رشته ورودی رو درنظر بگیره و راه انتقال به حالت پایانی رو هم از همه حالات چک کنین.
q0 شامل یه تعداد ۱ هست (حداقل تعداد برابر ۰)
q1 شامل یه تعداد ۰ و ۱ هست که ۲ تا ۰ پشت سرهم نداره (حداقل یه ۰ داره و میتونه ۱ نداشته باشه) ولی معلوم نیست آخرین حرفش صفر یا یکه
q2 شامل یه تعداد ۰ و ۱ هست که ۲ تا ۰ پشت سرهم نداره (حداقل یه ۰ داره) و آخرین حرفش یکه
q3 شامل یه تعداد ۰ و ۱ هست که "۱۱" داره ولی ۲ تا ۰ پشت سرهم نداره (حداقل یه ۰ و دوتا ۱ داره) و آخرین حرفش یکه
q4 شامل یه تعداد ۰ و ۱ هست که "۱۱" داره ولی ۲ تا ۰ پشت سرهم نداره (حداقل دوتا ۰ و دوتا ۱ داره) و آخرین حرفش صفره
اگه دقت کنین رشته هایی که فقط شامل ۱ هستن رو قبول نمیکنه. پس یا حرکتهاتون درست نبود و یا حالتهاتونو درست انتخاب نکردین. درکل برای هرسوال باید حالتهایی رو درنظر بگیرین که همه حالتهای رشته ورودی رو درنظر بگیره و راه انتقال به حالت پایانی رو هم از همه حالات چک کنین.
۰
ارسال: #۳
تست سال ۸۸
سلام.
میشه یه dfa با ۶ حالت و یا nfa با ۵ حالت ساخت. nfa:
که q0 حالت شروع و q3 و q4 حالت پایانیه. منظور از شناسایی رو نمیدونم.
میشه یه 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 حالت پایانیه. منظور از شناسایی رو نمیدونم.
ارسال: #۴
RE: تست سال ۸۸
۰
ارسال: #۵
تست سال ۸۸
اگر باید ماشین متناهی کامل رسم کنیم دارای ۶ وضعیت خواهیم بود با دو وضعیت نهایی
[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 حالت نهایی هستند
[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 حالت نهایی هستند
۰
ارسال: #۶
RE: تست سال ۸۸
نکته‌ی این سوال اینه که نباید برای nfa کمینه، حالت trap در نظر بگیریم،، چیزی که من تا الان نمیدونستم، خوب شد که این سوال گذاشتید، ممنون 
۰
ارسال: #۷
RE: تست سال ۸۸
بچه‌ها من یه ماشین با ۵ وضعیت و دو حالت نهایی کشیدم. عیبش چیه؟
راستی این برام سوال بود در کجا باید trapها هم لحاظ بشوند؟
(۲۷ دى ۱۳۹۰ ۰۸:۲۵ ب.ظ)Ali-B نوشته شده توسط: نکته‌ی این سوال اینه که نباید برای nfa کمینه، حالت trap در نظر بگیریم،، چیزی که من تا الان نمیدونستم، خوب شد که این سوال گذاشتید، ممنون
راستی این برام سوال بود در کجا باید trapها هم لحاظ بشوند؟
ارسال: #۸
RE: تست سال ۸۸
(۲۸ دى ۱۳۹۰ ۱۲:۴۴ ق.ظ)پشتکار نوشته شده توسط: بچه‌ها من یه ماشین با ۵ وضعیت و دو حالت نهایی کشیدم. عیبش چیه؟
ایراد داره، اون حلقه‌ها که یک می‌گیرن برای چی هستن؟ اصلا نیازی به این کار نیست.
خب بعد از رسم با چند تا مثال ساده امتحانش کنید، مثلا ساده‌ترین رشته ۱۱ هست، که این ماشین قبولش نمیکنه!
(۲۸ دى ۱۳۹۰ ۱۲:۴۴ ق.ظ)پشتکار نوشته شده توسط: راستی این برام سوال بود در کجا باید trapها هم لحاظ بشوند؟
نمیدونم، ولی یادمه تو یه سوال نوشته بود که در نظر نگیرید، البته فکر کنم dfa میخواست، نه nfa.
۰
ارسال: #۹
تست سال ۸۸
توی nfa که کشیدم میتونین یه q5 اضافه کنین که با ۰ و ۱ به خودش میره و از q4 و q1 میشه به q5 رفت. اگه این حالت و ۴ حرکت رو اضافه کنین dfa میشه.
nfa شما اشتباهه. رشته هایی که فقط ۱ دارن رو قبول نمیکنه.
nfa شما اشتباهه. رشته هایی که فقط ۱ دارن رو قبول نمیکنه.
۰
ارسال: #۱۰
تست سال ۸۸
۰
ارسال: #۱۲
RE: تست سال ۸۸
۰
ارسال: #۱۳
تست سال ۸۸
بعضی موقع شرایط خاص وجود داره که برای ماشینی که طراحی میکنیم پیش بینی نکردیم. بعضی موقع هم حواسمون به یه حالت خاص پرت میشه و برای رفع اون یه حالت به ماشین اضافه میکنیم که باعث اشتباهات جدید میشه. معمولاً این اشتباهات توی nfa بیشتر اتفاق می افته. چون میگیم ماشین ما در یکی از شرایط جواب این رشته خاص رو میده پس درسته. ولی احتمال داره رشته غلط رو هم قبول کنه.
ارسال: #۱۴
RE: تست سال ۸۸
(۲۸ دى ۱۳۹۰ ۱۱:۳۶ ب.ظ)Lakikharin نوشته شده توسط: بعضی موقع شرایط خاص وجود داره که برای ماشینی که طراحی میکنیم پیش بینی نکردیم. بعضی موقع هم حواسمون به یه حالت خاص پرت میشه و برای رفع اون یه حالت به ماشین اضافه میکنیم که باعث اشتباهات جدید میشه. معمولاً این اشتباهات توی nfa بیشتر اتفاق می افته. چون میگیم ماشین ما در یکی از شرایط جواب این رشته خاص رو میده پس درسته. ولی احتمال داره رشته غلط رو هم قبول کنه.
شما چیکار کردید؟
فرمول ثابتی نداره؟ بشه راحت بدست آورد؟
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close