زمان کنونی: ۲۸ مهر ۱۳۹۶, ۰۳:۰۴ ق.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)
ارسال:
  

پشتکار پرسیده:

سال ۸۸

سلام
این سوال من واسش یه ماشین رسم کردم که در ضمیمه آوردم
اشتباهش کجاست؟
مرسی


فایل‌(های) پیوست شده

۰
ارسال:
  

Jooybari پاسخ داده:

تست سال ۸۸

همونطور که جواب ثابت نداره فرمول ثابت هم نداره. توی هر مرحله باید درنظر بگیرین که با چه رشته هایی میتونه به ون حالت رسیده باشه. مثلا برای فایل ضمیمه شما اگه شماره هارو به ترتیب بگیریم:
q0 شامل یه تعداد ۱ هست (حداقل تعداد برابر ۰)
q1 شامل یه تعداد ۰ و ۱ هست که ۲ تا ۰ پشت سرهم نداره (حداقل یه ۰ داره و میتونه ۱ نداشته باشه) ولی معلوم نیست آخرین حرفش صفر یا یکه
q2 شامل یه تعداد ۰ و ۱ هست که ۲ تا ۰ پشت سرهم نداره (حداقل یه ۰ داره) و آخرین حرفش یکه
q3 شامل یه تعداد ۰ و ۱ هست که "۱۱" داره ولی ۲ تا ۰ پشت سرهم نداره (حداقل یه ۰ و دوتا ۱ داره) و آخرین حرفش یکه
q4 شامل یه تعداد ۰ و ۱ هست که "۱۱" داره ولی ۲ تا ۰ پشت سرهم نداره (حداقل دوتا ۰ و دوتا ۱ داره) و آخرین حرفش صفره
اگه دقت کنین رشته هایی که فقط شامل ۱ هستن رو قبول نمیکنه. پس یا حرکتهاتون درست نبود و یا حالتهاتونو درست انتخاب نکردین. درکل برای هرسوال باید حالتهایی رو درنظر بگیرین که همه حالتهای رشته ورودی رو درنظر بگیره و راه انتقال به حالت پایانی رو هم از همه حالات چک کنین.

۰
ارسال:
  

Jooybari پاسخ داده:

تست سال ۸۸

سلام.
میشه یه 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]

که q0 حالت شروع و q3 و q4 حالت پایانیه. منظور از شناسایی رو نمیدونم.

ارسال:
  

پشتکار پاسخ داده:

RE: تست سال ۸۸

(۲۷ دى ۱۳۹۰ ۰۱:۵۵ ب.ظ)Lakikharin نوشته شده توسط:  منظور از شناسایی رو نمیدونم.

منظور همون حالت نهاییه
یافتن تمامی ارسال‌های این کاربر

۰
ارسال:
  

lsamimi پاسخ داده:

تست سال ۸۸

اگر باید ماشین متناهی کامل رسم کنیم دارای ۶ وضعیت خواهیم بود با دو وضعیت نهایی
[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 حالت نهایی هستند

۰
ارسال:
  

Ali-B پاسخ داده:

RE: تست سال ۸۸

نکته‌ی این سوال اینه که نباید برای nfa کمینه، حالت trap در نظر بگیریم،، چیزی که من تا الان نمیدونستم، خوب شد که این سوال گذاشتید، ممنون Smile

۰
ارسال:
  

پشتکار پاسخ داده:

RE: تست سال ۸۸

بچه‌ها من یه ماشین با ۵ وضعیت و دو حالت نهایی کشیدم. عیبش چیه؟
(۲۷ دى ۱۳۹۰ ۰۷:۲۵ ب.ظ)Ali-B نوشته شده توسط:  نکته‌ی این سوال اینه که نباید برای nfa کمینه، حالت trap در نظر بگیریم،، چیزی که من تا الان نمیدونستم، خوب شد که این سوال گذاشتید، ممنون Smile

راستی این برام سوال بود در کجا باید trap‌ها هم لحاظ بشوند؟


فایل‌(های) پیوست شده

ارسال:
  

Ali-B پاسخ داده:

RE: تست سال ۸۸

(۲۷ دى ۱۳۹۰ ۱۱:۴۴ ب.ظ)پشتکار نوشته شده توسط:  بچه‌ها من یه ماشین با ۵ وضعیت و دو حالت نهایی کشیدم. عیبش چیه؟

ایراد داره، اون حلقه‌ها که یک می‌گیرن برای چی هستن؟ اصلا نیازی به این کار نیست.
خب بعد از رسم با چند تا مثال ساده امتحانش کنید، مثلا ساده‌ترین رشته ۱۱ هست، که این ماشین قبولش نمیکنه!

(۲۷ دى ۱۳۹۰ ۱۱:۴۴ ب.ظ)پشتکار نوشته شده توسط:  راستی این برام سوال بود در کجا باید trap‌ها هم لحاظ بشوند؟

نمیدونم، ولی یادمه تو یه سوال نوشته بود که در نظر نگیرید، البته فکر کنم dfa میخواست، نه nfa.
یافتن تمامی ارسال‌های این کاربر

۰
ارسال:
  

Jooybari پاسخ داده:

تست سال ۸۸

توی nfa که کشیدم میتونین یه q5 اضافه کنین که با ۰ و ۱ به خودش میره و از q4 و q1 میشه به q5 رفت. اگه این حالت و ۴ حرکت رو اضافه کنین dfa میشه.

nfa شما اشتباهه. رشته هایی که فقط ۱ دارن رو قبول نمیکنه.

۰
ارسال: #۱۰
  

پشتکار پاسخ داده:

تست سال ۸۸

فرمولی برای رسم ماشین نیست؟


(۲۸ دى ۱۳۹۰ ۱۲:۰۵ ق.ظ)Ali-B نوشته شده توسط:  ایراد داره، اون حلقه‌ها که یک می‌گیرن برای چی هستن؟ اصلا نیازی به این کار نیست.

چرا نیازی نیست؟ نباید تمامی حالات رو در نظر بگیریم؟

خب اگه از اولین حالت یه اتصال به نقطه نهایی با مقدار یک بکشیم مشکل حله؟

۰
ارسال: #۱۱
  

Jooybari پاسخ داده:

تست سال ۸۸

اون موقع رشته ۱ رو قبول میکنه. نمیدونم مشکلتون با dfa و nfa که نوشتم چیه؟!؟!

ارسال: #۱۲
  

پشتکار پاسخ داده:

RE: تست سال ۸۸

(۲۸ دى ۱۳۹۰ ۰۴:۱۳ ب.ظ)Lakikharin نوشته شده توسط:  اون موقع رشته ۱ رو قبول میکنه. نمیدونم مشکلتون با dfa و nfa که نوشتم چیه؟!؟!

من مشکلی ندارم دوست عزیز
فقط سوالم اینه چرا هرچی ماشین طراحی می کنم همه میگن اشتباههHuhHuhHuh
یافتن تمامی ارسال‌های این کاربر

۰
ارسال: #۱۳
  

Jooybari پاسخ داده:

تست سال ۸۸

بعضی موقع شرایط خاص وجود داره که برای ماشینی که طراحی میکنیم پیش بینی نکردیم. بعضی موقع هم حواسمون به یه حالت خاص پرت میشه و برای رفع اون یه حالت به ماشین اضافه میکنیم که باعث اشتباهات جدید میشه. معمولاً این اشتباهات توی nfa بیشتر اتفاق می افته. چون میگیم ماشین ما در یکی از شرایط جواب این رشته خاص رو میده پس درسته. ولی احتمال داره رشته غلط رو هم قبول کنه.

ارسال: #۱۴
  

پشتکار پاسخ داده:

RE: تست سال ۸۸

(۲۸ دى ۱۳۹۰ ۱۰:۳۶ ب.ظ)Lakikharin نوشته شده توسط:  بعضی موقع شرایط خاص وجود داره که برای ماشینی که طراحی میکنیم پیش بینی نکردیم. بعضی موقع هم حواسمون به یه حالت خاص پرت میشه و برای رفع اون یه حالت به ماشین اضافه میکنیم که باعث اشتباهات جدید میشه. معمولاً این اشتباهات توی nfa بیشتر اتفاق می افته. چون میگیم ماشین ما در یکی از شرایط جواب این رشته خاص رو میده پس درسته. ولی احتمال داره رشته غلط رو هم قبول کنه.

شما چیکار کردید؟
فرمول ثابتی نداره؟ بشه راحت بدست آورد؟
یافتن تمامی ارسال‌های این کاربر



پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close