سلام کاهش dfa به روش پلکانی چطوریه؟
ممنون
سلام.
والا منم این اسمو نشنیدم ولی الان یه روش خوب رو برات تشریح میکنم.
این کار چنتا مرحله داره که به شرح زیرن:
۱/ تمام وضعیت های غیر قابل دسترس رو حذف کن. مثلا از q0 هیچ جور نمیتونی به q5 برسی. پس راحت با یه خط بترکونش و از صفحه کاغذ محوش کن.
۲/ به ازای هر Qi و Qj که توی گراف وجود داره زوج مرتب های (Qi,Qj( رو تشکیل بده. مثلا اگه گراف ۴ تا وضعیت داره (از Q0 تا Q3) شما باید Q0,Q1 و Q0,Q2 و Q0,Q3 و Q1,Q2 و Q1,Q3 و Q2,Q3 رو یه گوشه بنویسی. با یکم دقت و یه بار امتحان این روش میبینی که تعداد این حالتای دوتایی ترکیب n از ۲ه. (که مهم نیس. یعنی ربطی به کارمون نداره)
۳/ از این وضعیت های لیست شده(مثلا Q0,Q3) اونایی که یکیشون پایانی(مثلا Q3) و دیگری پایانی نیس (مثلا Q0) رو به سادگی هرچه تمام‌تر حذف میکنیم. گرفتی؟ یعنی بعد از لیست کردن اون زوج مرتبا میری تو گراف نگا میکنی، اگه یکی از وضعیتای زوج مرتب نهایی و یکی دیگش نهایی نبود حذفش میکنی.
*******"تذکر": اگه هر دوتا عنصر زوج مرتب پایانی بودن اون زوج مرتبه رو حذفش نمیکنی. خیلی مهمه‌ها *******
این مرحله‌ی ۳ رو واسه همه‌ی زوج مرتبا انجام بده.
مهم. به دققققت بخونش ۴/ به ازای هر زوج مرتب Qi,Qj که تا الان حذف نشده، به ازای تمام حروف الفبا، خروجی های هر عنصر از این زوج مرتب رو ب دست بیار. یعنی مثلا Q0,Q1 (که تا اینجا حذف نشده) نگا کن ببین از Q0 و ۰ به کدوم وضضعیت میریم. Q0 و ۱ هم نگا کن . واسه Q1 هم همین کارو انجام بده. خب، حالا اگه با Q0 و ۰ رسیدیم به یه وضعیت غیر پایانی ولی با Q1 رسیدیم به یه وضعیت پایانی، این زوج مرتب هم خط میزنیم. Q0 و ۱ , Q1 و۱ رو هم امتحان میکنیم. دقت کن که اگه هر دوتای Q0 و Q1 به ۰ میرسیدن به نود پایانی خط نمیخوره ها.
۵/ مرحله قبل رو واسه همه زوج مرتبا تکرار کن. تمومه.هر چی زوج مرتب باقی موندن ادغام پذیر هستن. مثلا Q0 و Q2 ادغام پذیرن. تو گراف جدید که میکشی این دوتا وضعیت رو تو یه دایره بکش. آفرین، تو تونستی کاهش وضعیت رو اعمال کنی
در کل این روش خیلی ساده و مختصره ولی من بخاطر اینکه مجبور بودم همراه توضیحاتم مثالم بیارم خیلی طولانی شد.
امیدوارم بفهمی چی گفتم
ببخشید. نوشتم ترکیب n از دو که درستش ۲ از nه یعنی همون فرمول C(n,2)
تو مدار منطقی فصل مربوط به طراحی مدارات سنکرون و آسنکرون یه روشی وجود داره که توش از جدول ادغام استفاده میشه تا تعداد حالات یک مدار رو مینیمم کرد.از این جدول ادغام خیلی راحت میشه برای مینیمم کردن تعداد حالات یک DFA هم استفاده کرد(جدول ادغام به صورت پلکانی رسم میشه و احتمالا به همین دلیله که بهش جدول پلکانی هم میگن)