تالار گفتمان مانشت
تبدیل nfa به dfa - نسخه‌ی قابل چاپ

تبدیل nfa به dfa - payman84ce - 30 آبان ۱۳۹۰ ۰۷:۴۹ ب.ظ

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

تبدیل nfa به dfa - pos - 30 آبان ۱۳۹۰ ۰۸:۵۴ ب.ظ

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

تبدیل nfa به dfa - variant20002000 - 30 آبان ۱۳۹۰ ۱۰:۴۶ ب.ظ

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

تبدیل nfa به dfa - Xilinx - 01 آذر ۱۳۹۰ ۰۷:۵۱ ب.ظ

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

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

RE: تبدیل nfa به dfa - nasim_sh - 22 مهر ۱۳۹۱ ۱۰:۵۰ ق.ظ


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


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

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

تبدیل nfa به dfa - Jooybari - 23 مهر ۱۳۹۱ ۰۳:۵۲ ب.ظ

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