۰
subtitle
ارسال: #۱
[سوال نظریه] تبدیل nfa به dfa
با سلام خدمت دوستان
![[تصویر: 140042_1_1379088301.jpg]](https://img.manesht.ir/140042_1_1379088301.jpg)
ممنون میشم اگه ساده و گام به گام توضیح بدین.
تشکر
ممنون میشم اگه ساده و گام به گام توضیح بدین.
تشکر
۰
ارسال: #۲
RE: [سوال نظریه] تبدیل nfa به dfa
سلام .
در مرحله اول برای هر حالت در nfa تعیین می کنیم که با هر ورودی به چه حالتی می رویم و اگر در مراحل کار حالت ترکیبی جدیدی اضافه شد آن را نیز در جدول در نظر می گیرم مثلا در حالت ۱ با هر دو ورودی a,b امکان تغییر وضعیت به هر دو حالت ۱,۲ وجود دارد پس یک حالت جدید {۱,۲} به وجود می آید که این را نیز بعنوان یک حالت جدید در نظر گرفته و در ادامه نیز برای این حالت جدید وضعیت تغییر حالت را در جدول تعیین می کنیم.
جدولی به صورت زیر تشکیل می شود
حال بر اساس همین جدول dfa اولیه رو تشکیل می دهیم
و در ادامه نیز با اصلاح نام حالت ها dfa نهایی زیر به دست می آید که معادل nfa اولیه ما هستش
موفق باشی
در مرحله اول برای هر حالت در nfa تعیین می کنیم که با هر ورودی به چه حالتی می رویم و اگر در مراحل کار حالت ترکیبی جدیدی اضافه شد آن را نیز در جدول در نظر می گیرم مثلا در حالت ۱ با هر دو ورودی a,b امکان تغییر وضعیت به هر دو حالت ۱,۲ وجود دارد پس یک حالت جدید {۱,۲} به وجود می آید که این را نیز بعنوان یک حالت جدید در نظر گرفته و در ادامه نیز برای این حالت جدید وضعیت تغییر حالت را در جدول تعیین می کنیم.
جدولی به صورت زیر تشکیل می شود
حال بر اساس همین جدول dfa اولیه رو تشکیل می دهیم
و در ادامه نیز با اصلاح نام حالت ها dfa نهایی زیر به دست می آید که معادل nfa اولیه ما هستش
موفق باشی
۰
ارسال: #۳
RE: [سوال نظریه] تبدیل nfa به dfa
مهندس خسته نباشی...این حالت q1 چطور به qt رفت؟مگه q1 با a میشه جایی رفت؟مگه نمیشه حالت تهی؟
۰
ارسال: #۴
RE: [سوال نظریه] تبدیل nfa به dfa
نقل قول: سلام .با تشکر. با این روش میشه nfa دارای [tex]\epsilon[/tex] رو هم تبدیل نمود؟
در مرحله اول برای هر حالت در nfa تعیین می کنیم که با هر ورودی به چه حالتی می رویم و اگر در مراحل کار حالت ترکیبی جدیدی اضافه شد آن را نیز در جدول در نظر می گیرم مثلا در حالت ۱ با هر دو ورودی a,b امکان تغییر وضعیت به هر دو حالت ۱,۲ وجود دارد پس یک حالت جدید {۱,۲} به وجود می آید که این را نیز بعنوان یک حالت جدید در نظر گرفته و در ادامه نیز برای این حالت جدید وضعیت تغییر حالت را در جدول تعیین می کنیم.
جدولی به صورت زیر تشکیل می شود
سوال دوم: در نرم افزار jflap تبدیل رو به یه صورت دیگه نشون میده.دلیلش رو میدونید؟
نقل قول: این حالت q1 چطور به qt رفت؟مگه q1 با a میشه جایی رفت؟مگه نمیشه حالت تهی؟فکر کنم qt حالت تهی هست
ارسال: #۵
RE: [سوال نظریه] تبدیل nfa به dfa
با این روش میشه nfa دارای [tex]\epsilon[/tex] رو هم تبدیل نمود؟
سلام .
شما زمانی که داری جدول رو تولید میکنی از هر حالتی که با الفبای خاص داری تمام حالت های قابل دسترسی رو پیدا مکنی همون به روش nfa عمل کن، یعنی حتی با لاندا هم ببین کدوم مسیر بعلاوه اون الفبات قابل دسترسی و اونو بزار توی ستون کنونی جدول
در نرم افزار jflap تبدیل رو به یه صورت دیگه نشون میده.دلیلش رو میدونید؟
ببین ماشینی که jflap تولید می کنه به صورت زیر هستش که دقیق مثل dfa خودمونه فقط حالت تله رو دیگه در نظر نگرفته که اونم خودمون اضافه می کنیم چون مثلا توی حالت q1 با a هیچ خروجی نداره که میشه همون تله دیگه.
سلام .
شما زمانی که داری جدول رو تولید میکنی از هر حالتی که با الفبای خاص داری تمام حالت های قابل دسترسی رو پیدا مکنی همون به روش nfa عمل کن، یعنی حتی با لاندا هم ببین کدوم مسیر بعلاوه اون الفبات قابل دسترسی و اونو بزار توی ستون کنونی جدول
در نرم افزار jflap تبدیل رو به یه صورت دیگه نشون میده.دلیلش رو میدونید؟
ببین ماشینی که jflap تولید می کنه به صورت زیر هستش که دقیق مثل dfa خودمونه فقط حالت تله رو دیگه در نظر نگرفته که اونم خودمون اضافه می کنیم چون مثلا توی حالت q1 با a هیچ خروجی نداره که میشه همون تله دیگه.
۰
ارسال: #۶
[سوال نظریه] تبدیل nfa به dfa
(۰۷ آبان ۱۳۹۱ ۱۱:۰۰ ب.ظ)mp1368 نوشته شده توسط: ببین ماشینی که jflap تولید می کنه به صورت زیر هستش که دقیق مثل dfa خودمونه فقط حالت تله رو دیگه در نظر نگرفته که اونم خودمون اضافه می کنیم چون مثلا توی حالت q1 با a هیچ خروجی نداره که میشه همون تله دیگه.تشکر ولی طبق تعریف dfa همه transition ها باید مشخص شده باشه.به نظر من این نموداری که نرم افزار تولید کرده اصلا dfa نیست،بلکه nfa است.این طور نیست؟
ارسال: #۷
RE: [سوال نظریه] تبدیل nfa به dfa
(۰۷ آبان ۱۳۹۱ ۱۱:۱۰ ب.ظ)masoudt نوشته شده توسط: تشکر ولی طبق تعریف dfa همه transition ها باید مشخص شده باشه.به نظر من این نموداری که نرم افزار تولید کرده اصلا dfa نیست،بلکه nfa است.این طور نیست؟
سلام . گزینه ی Complete رو که بزنی DFA تبدیلی رو به یه صفحه جدید میبره و توی صفحه ی جدید اول یک حالت جدید به صفحه اضافه کن بعد از منوی Convert گزینه ی Add Trap State To DFA رو انتخاب کن در ادامه حالت تله رو نیز به DFA اضافه میکنه که ماشین زیر رو ایجاد میکنه :
موفق باشی
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close