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

تبدیل nfa به dfa

ارسال:
  

payman84ce پرسیده:

تبدیل nfa به dfa

سلام
یادمه یه روش بود که یه جدول می کشیدیم بعد سطرهایش حالات و ستونهاش حروف الفبا بوود بقیش یادم نیست
متاسفانه به دلیل شرایط کاری تنها منبع من اینترنت است
لطفا در صورت امکان لینک بدید ممنون

۲
ارسال:
  

Xilinx پاسخ داده:

تبدیل nfa به dfa

(۳۰ آبان ۱۳۹۰ ۱۰:۴۶ ب.ظ)variant20002000 نوشته شده توسط:  بچه‌ها اینجا نمیشه توضیح داد. ۲ صفحه است این مطلب که توی کتاب لینز خیلی راحت‌تر از اون روش جدول کشی گفته. (استادمون به ما هم همین روش جدول کشیدن رو درس داد) ولی این روشی که لینز گفته تقریباً همونه ولی یهکم سریع‌تر عمل میکنه.
صفحه ۶۳ و ۶۴ کتاب لینز ترجمه پور محقق رو یه نگاه بندازید یادتون میاد (انقدر این روش قشنگه که من حیفم اومد نگم) Big Grin
ولی به نظر من روش جدول کشی خیلی راحت و سریع هست .من اصلا از روی کتاب خوندم متوجه نشدم تا زمانی که جزوه‌ی خودمو دیدم !

توی این روش یه جدول میکشیم که سمت چپ یه سری حالت هست که درون آکولاد نوشته میشه.حالت اولی که مینویسیم {q0} هست .سمت راست جدول حالت های مختلف ورودی(یا الفبا) رو می نویسیم.(منظورم از سمت چپ جدول یه چیزی مثل ورودی جدول درستی توی منطقی هست )بعد NDFA رو نیگاه میکنیم که با مثلا وروی صفر (یا ورودی a) به چه حالت یا حالت هایی میره.مثلا اگه q0 به خوندن a به q1 و q2 میرفت‌، سمت راست جدول و زیر ستون صفر مینویسیم {q1,q2} و بعد ورودی ۱ رو برای حالت q0 مینویسیم و برای ادامه کار حالت های بدست اومده توی مراحل مختلف رو بررسی میکنید( توی مثالی که زدم سمت راست جدول زیر صفر {q1,q2} بدست اومد پس در قسمت حالت ها(یعنی سمت چپ جدول) این حالت رو اضافه میکنیم و بررسی میکنیم که در حالت q1 و q2 به چه حالت یا حالت هایی (ماشین غیر قطعی) میره) اگه در یکی از حالات فقط ماشین ۱ رو میخوند توی جدول واسه قسمت صفرش تهی میذاریم.جدول که تکمیل شد ماشین رو رسم میکنیم.و حالات نهایی و غیر نهایی هم به این صورت تعیین میشه که اگه مثلا q1 در ماشین غیر قطعی نهایی بود هر حالت دیگه ای که همراهش بوجود اومد مثل {q1,q2} اون هم نهایی میشه !

۰
ارسال:
  

pos پاسخ داده:

تبدیل nfa به dfa

من هم یادم یک چنین چیزی را یکی از استادامون برای ساده سازی گفته بودند که خیلی راحت بود. متاسفانه جزوش را ندارم. اگر این را هم کسی بلده ممنون میشم بگه.

۰
ارسال:
  

variant20002000 پاسخ داده:

تبدیل nfa به dfa

بچه‌ها اینجا نمیشه توضیح داد. ۲ صفحه است این مطلب که توی کتاب لینز خیلی راحت‌تر از اون روش جدول کشی گفته. (استادمون به ما هم همین روش جدول کشیدن رو درس داد) ولی این روشی که لینز گفته تقریباً همونه ولی یهکم سریع‌تر عمل میکنه.
صفحه ۶۳ و ۶۴ کتاب لینز ترجمه پور محقق رو یه نگاه بندازید یادتون میاد (انقدر این روش قشنگه که من حیفم اومد نگم) Big Grin

۰
ارسال:
  

nasim_sh پاسخ داده:

RE: تبدیل nfa به dfa


مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.


سلام دوستان در این NFA از q1 با ۰ و ۱ هم به q0 هم به q2 هم به q1 رفته ایم ولی چرا تو DFA معادلش از q1 با ۰ و ۱ به q2 رفته ؟
جریانش چیه ؟ Huh

(توی شکل NFA از q0 با ۰ و ۱ به q1 و از q1 با ۰ و ۱ به q0 رفته . شاید تو شکل واضح نباشه .Cool )

۰
ارسال:
  

Jooybari پاسخ داده:

تبدیل nfa به dfa

سلام. این dfa فقط از روی یه الگوریتم از روی nfa شکل سوال ساخته شده. مسلماً ساده تر هم میشه. عبارت منظمشم میشه [tex]0^*(0 1)[/tex]. مشکل کجاست؟



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  شمارش تعداد state های ماشین DFA mostafa2012 ۱۰ ۴,۱۱۴ ۱۳ بهمن ۱۳۹۳ ۱۲:۱۷ ب.ظ
آخرین ارسال: fatemeh69
  تعداد حالات نهایی nfa برای زبان دارای لاندا و فاقد لاندا pooyaa ۲ ۱,۲۱۸ ۰۶ بهمن ۱۳۹۳ ۰۶:۵۳ ب.ظ
آخرین ارسال: pooyaa
  تعریف رسمی زبانی که توسط nfa پذیرفته نمیشود pooyaa ۲ ۶۶۴ ۰۳ بهمن ۱۳۹۳ ۰۲:۴۲ ق.ظ
آخرین ارسال: pooyaa
  بدست آوردن عبارت منظم یک dfa mostafa2012 ۸ ۱,۷۰۳ ۰۳ بهمن ۱۳۹۳ ۰۲:۲۴ ق.ظ
آخرین ارسال: Jooybari
Question زبان منظم، DFA، حافظه، به خاطر آوردن! Ametrine ۷ ۱,۶۰۶ ۲۹ دى ۱۳۹۳ ۱۱:۴۰ ب.ظ
آخرین ارسال: Ametrine
  توضیح یک مسئله تبدیل به فرم چامسکی visitor ۴ ۱,۱۹۴ ۱۷ دى ۱۳۹۳ ۱۱:۳۴ ب.ظ
آخرین ارسال: Jooybari
  تبدیل nfa به dfa alirezafchh ۱ ۱,۲۲۳ ۰۸ دى ۱۳۹۳ ۱۲:۴۷ ق.ظ
آخرین ارسال: fatemeh69
  سوال از تبدیل nfa به عبارت منظم arefeh.hp ۱ ۱,۶۶۷ ۱۳ آذر ۱۳۹۳ ۰۸:۱۸ ب.ظ
آخرین ارسال: Jooybari
  محدودیت برای تبدیل مستقل از متن به نرمال چامسکی Imankhani ۵ ۱,۲۲۷ ۲۱ آبان ۱۳۹۳ ۱۱:۰۶ ق.ظ
آخرین ارسال: Imankhani
Question تبدیل همریختی و معکوس تبدیل Ametrine ۴ ۱,۰۵۷ ۲۴ مهر ۱۳۹۳ ۱۰:۳۱ ب.ظ
آخرین ارسال: Ametrine

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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