۰
subtitle
ارسال: #۱
  
تبدیل nfa به dfa
[attachment=17480]دوستان سلام
این تصویر گرافی که الان می ذارم رو طبق کتاب پیتر لینز تا کشیدن dfa با همه ی رئوس میرم ، اما تو کم کردن تعداد رئوس گیر می کنم. میشه از اون مرحله به بعدش رو بهم بگین چی میشه و باید چکار کرد؟
با تشکر
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
این تصویر گرافی که الان می ذارم رو طبق کتاب پیتر لینز تا کشیدن dfa با همه ی رئوس میرم ، اما تو کم کردن تعداد رئوس گیر می کنم. میشه از اون مرحله به بعدش رو بهم بگین چی میشه و باید چکار کرد؟
با تشکر
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
۰
ارسال: #۲
  
RE: تبدیل nfa به dfa
شکل dfa معادل و dfa کمینه را گذاشته ام و روش کمینه کردن هم خیلی کوتاهه
اولا اون final state با هیچ state دیگری برابر نیست چون اون دو تا غیر فاینال هستند و اون q1,2 فاینال است
اما در مورد دو state دیگر q0 با ۰ می ره به q1,2
از طرفی q0,2 هم با ۰ می ره به q1,2
پس تا اینجا عملکرد این دوتا با هم مساویه اما باید به ازای ورودی ۱ هم مقایسه بشن
q0 با ۱ می ره به q1,2
از طرفی q0,2 هم با ۱ می ره به q1,2
پس کلا از q0 با هر ورودی ای به هر جا که بریم با q0,2 هم با همون ورودی به همون جا می ریم
پس این و state در واقع مثل هم عمل می کنند
پس یکی شون زیادی است و حذفش می کنیم
اولا اون final state با هیچ state دیگری برابر نیست چون اون دو تا غیر فاینال هستند و اون q1,2 فاینال است
اما در مورد دو state دیگر q0 با ۰ می ره به q1,2
از طرفی q0,2 هم با ۰ می ره به q1,2
پس تا اینجا عملکرد این دوتا با هم مساویه اما باید به ازای ورودی ۱ هم مقایسه بشن
q0 با ۱ می ره به q1,2
از طرفی q0,2 هم با ۱ می ره به q1,2
پس کلا از q0 با هر ورودی ای به هر جا که بریم با q0,2 هم با همون ورودی به همون جا می ریم
پس این و state در واقع مثل هم عمل می کنند
پس یکی شون زیادی است و حذفش می کنیم
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close