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

[سوال نظریه] تبدیل nfa به dfa - masoudt - 06 آبان ۱۳۹۱ ۱۰:۱۱ ب.ظ

با سلام خدمت دوستان

[تصویر:  140042_1_1379088301.jpg]

ممنون میشم اگه ساده و گام به گام توضیح بدین.
تشکر

RE: [سوال نظریه] تبدیل nfa به dfa - mp1368 - 06 آبان ۱۳۹۱ ۱۰:۵۸ ب.ظ

سلام .
در مرحله اول برای هر حالت در nfa تعیین می کنیم که با هر ورودی به چه حالتی می رویم و اگر در مراحل کار حالت ترکیبی جدیدی اضافه شد آن را نیز در جدول در نظر می گیرم مثلا در حالت ۱ با هر دو ورودی a,b امکان تغییر وضعیت به هر دو حالت ۱,۲ وجود دارد پس یک حالت جدید {۱,۲} به وجود می آید که این را نیز بعنوان یک حالت جدید در نظر گرفته و در ادامه نیز برای این حالت جدید وضعیت تغییر حالت را در جدول تعیین می کنیم.
جدولی به صورت زیر تشکیل می شود

[attachment=7445]

حال بر اساس همین جدول dfa اولیه رو تشکیل می دهیم

[attachment=7448]

و در ادامه نیز با اصلاح نام حالت ها dfa نهایی زیر به دست می آید که معادل nfa اولیه ما هستش

[attachment=7450]

موفق باشی

RE: [سوال نظریه] تبدیل nfa به dfa - jameshenas - 06 آبان ۱۳۹۱ ۱۱:۲۲ ب.ظ

مهندس خسته نباشی...این حالت q1 چطور به qt رفت؟مگه q1 با a میشه جایی رفت؟مگه نمیشه حالت تهی؟

RE: [سوال نظریه] تبدیل nfa به dfa - masoudt - 07 آبان ۱۳۹۱ ۰۱:۱۳ ب.ظ

نقل قول: سلام .
در مرحله اول برای هر حالت در nfa تعیین می کنیم که با هر ورودی به چه حالتی می رویم و اگر در مراحل کار حالت ترکیبی جدیدی اضافه شد آن را نیز در جدول در نظر می گیرم مثلا در حالت ۱ با هر دو ورودی a,b امکان تغییر وضعیت به هر دو حالت ۱,۲ وجود دارد پس یک حالت جدید {۱,۲} به وجود می آید که این را نیز بعنوان یک حالت جدید در نظر گرفته و در ادامه نیز برای این حالت جدید وضعیت تغییر حالت را در جدول تعیین می کنیم.
جدولی به صورت زیر تشکیل می شود
با تشکر. با این روش میشه nfa دارای [tex]\epsilon[/tex] رو هم تبدیل نمود؟
سوال دوم: در نرم افزار jflap تبدیل رو به یه صورت دیگه نشون میده.دلیلش رو میدونید؟

نقل قول: این حالت q1 چطور به qt رفت؟مگه q1 با a میشه جایی رفت؟مگه نمیشه حالت تهی؟
فکر کنم qt حالت تهی هست

RE: [سوال نظریه] تبدیل nfa به dfa - mp1368 - 07 آبان ۱۳۹۱ ۱۱:۰۰ ب.ظ

با این روش میشه nfa دارای [tex]\epsilon[/tex] رو هم تبدیل نمود؟

سلام .
شما زمانی که داری جدول رو تولید میکنی از هر حالتی که با الفبای خاص داری تمام حالت های قابل دسترسی رو پیدا مکنی همون به روش nfa عمل کن، یعنی حتی با لاندا هم ببین کدوم مسیر بعلاوه اون الفبات قابل دسترسی و اونو بزار توی ستون کنونی جدول


در نرم افزار jflap تبدیل رو به یه صورت دیگه نشون میده.دلیلش رو میدونید؟

ببین ماشینی که jflap تولید می کنه به صورت زیر هستش که دقیق مثل dfa خودمونه فقط حالت تله رو دیگه در نظر نگرفته که اونم خودمون اضافه می کنیم چون مثلا توی حالت q1 با a هیچ خروجی نداره که میشه همون تله دیگه.

[attachment=7473]

[سوال نظریه] تبدیل nfa به dfa - masoudt - 07 آبان ۱۳۹۱ ۱۱:۱۰ ب.ظ

(۰۷ آبان ۱۳۹۱ ۱۱:۰۰ ب.ظ)mp1368 نوشته شده توسط:  ببین ماشینی که jflap تولید می کنه به صورت زیر هستش که دقیق مثل dfa خودمونه فقط حالت تله رو دیگه در نظر نگرفته که اونم خودمون اضافه می کنیم چون مثلا توی حالت q1 با a هیچ خروجی نداره که میشه همون تله دیگه.
تشکر ولی طبق تعریف dfa همه transition ها باید مشخص شده باشه.به نظر من این نموداری که نرم افزار تولید کرده اصلا dfa نیست،بلکه nfa است.این طور نیست؟

RE: [سوال نظریه] تبدیل nfa به dfa - mp1368 - 07 آبان ۱۳۹۱ ۱۱:۵۸ ب.ظ

(۰۷ آبان ۱۳۹۱ ۱۱:۱۰ ب.ظ)masoudt نوشته شده توسط:  تشکر ولی طبق تعریف dfa همه transition ها باید مشخص شده باشه.به نظر من این نموداری که نرم افزار تولید کرده اصلا dfa نیست،بلکه nfa است.این طور نیست؟

سلام . گزینه ی Complete رو که بزنی DFA تبدیلی رو به یه صفحه جدید میبره و توی صفحه ی جدید اول یک حالت جدید به صفحه اضافه کن بعد از منوی Convert گزینه ی Add Trap State To DFA رو انتخاب کن در ادامه حالت تله رو نیز به DFA اضافه میکنه که ماشین زیر رو ایجاد میکنه :

[attachment=7475]

موفق باشی