سلام
لطفا عکس ببینید
دلیل هر کدوم از یالهای ۱ تا ۴ ؟
و همینطور یه راه کلی برای تبدیل nfa به dfa ؟
تشکر
(۲۳ مرداد ۱۳۹۳ ۰۱:۱۲ ب.ظ)s_t_6 نوشته شده توسط: سلام
لطفا عکس ببینید
دلیل هر کدوم از یالهای ۱ تا ۴ ؟
و همینطور یه راه کلی برای تبدیل nfa به dfa ؟
تشکر
پیتر لینز کامل توضیح داده تبدیلات رو بخونید به نفعتونه بخونین متوجه نشدید دوباره اطلاع بدید .
سلام
اول باید ببینیم هر stste ای با هر ورودی به کجا می ره برای این کار به شکل ۱ نگاه کنید
بعد باید بیاییم بر اساس همین جدول یه DFa بکشیم
خب نگاه می کنیم می بینیم S0 با a هم به s0 رفته هم به S1 پس یالی از S0 با برچسب a به S0,S1 می کشیم
حالا ببینیم تکلیف state ای که در واقع S0, S1 است چیه
خب این state با a به کجا می ره
برای فهمیدن این مطلب باید ببینیم که S0 با a به کجا می ره و S1 با a به کجا می ره و بعد بین این ها اجتماع بگیرم
S0 با a به S0, S1 می ره و S1 هم با a به هیچ حا که کلا اجتماعشون می شه S0و S1
پس از state ای به نام S0, S1 با a به خودش می رویم
خب این state با b به کجا می ره
S0 با b می ره به S0
S1 با b می ره به S2
که کلا اجتماعشون می شه S0, S2
پس از s0, S1 با b به S0 , S2 می رویم
تکلیف s0, S1 کلا مشخص شد می ریم سراغ state ای به نام s0 , S2
و همین روند رو تکرار می کنیم
یعنی برای هر state ببنیم با A به کجا می ره با b به کجا
در این بین ممکنه state های جدیدی تولید بشن (مثل همین S0, S2 خب این state از اول نبود ولی در حین ساختن Dfa پدید اومد)
نهایتا وقتی ساخت Dfa تموم شد state ها خیلیاشون ممکنه اسمشون با اسم state های قبلی فرق کنه
هر state که یکی از state های فاینال قبلی رو در خودش داشت فایناله
مثلا این جا state تی به نام s0, S3 چون در خودش S3 رو داره پس فایناله
نهایتا می بینید که dfa ای که من با این روش بدست آودم کاملا مشابه Dfa شماست
تنها نا م های state ها متفاوته که اصصصصصصصصصصصلا مهم نیست و می توان در یک حرکت نام ها را تغییر داد