مینیم‌سازی دی‌اف‌ای کیست؟ توضیح بده.
در نظریه اتوماتا (شاخه‌ای از علوم کامپیوتر)، مینیمم‌سازی کار انتقال یک اتوماتای متناهی قطعی (دی‌اف‌ای) به یک دی‌اف‌ای معادل است که دارای تعداد وضعیت‌های مینیمم است. در اینجا، دو دی‌اف‌ای معادل نامیده می‌شوند اگر آن‌ها یک زبان منظم یکسان را مشخص کنند. چند الگوریتم مختلف که این کار را انجام می‌دهند شناخته شده‌اند و در متون استاندارد در مورد نظریهٔ اتوماتا توضیح داده می‌شوند.دی اف ای مینیمم.برای هر زبان منظم که به وسیلهٔ یک دی‌اف‌ای می‌تواند پذیرفته شود، یک دی‌اف‌ای با تعداد وضعیت‌های مینیمم وجود دارد و این دی‌اف‌ای منحصر بفرد است (مگر اینکه به آن وضعیت‌ها نام‌های مختلفی بتوان داد). دی‌اف‌ای مینیمم، مینیمم هزینهٔ محاسبات برای کارهایی مانند تطبیق الگو را تضمین می‌کند.دو دسته از وضعیت‌ها وجود دارند که بدون اینکه روی زبان اثر بگذارند می‌توانند از دی‌اف‌ای اصلی حذف/ادغام شوند تا مینیمم‌سازی آن را بپذیرد.مینیمم‌سازی دی‌اف‌ای، در ارتباط با حذف/ ادغام وضعیت‌های مربوط معمولاً در سه مرحله انجام می‌شود. چون حذف وضعیت‌های غیرقابل تمیز از جنبهٔ محاسبات گران‌ترین است، معمولاً در آخرین مرحله انجام می‌شود.وضعیت‌های غیر قابل دسترس.وضعیت "p" از دی‌اف‌ای ("M="("Q", Σ, δ, "q""0", "F" غیرقابل دسترس است اگر هیچ رشته‌ای چون "w" در *∑ وجود نداشته باشد که برای آن ("p="δ("q""0", "w" باشد. وضعیت‌های قابل دسترس از الگوریتم زیر می‌تواند به دست آیند:let reachable_states:= {q0};let new_states:= {q0};do { temp := the empty set; for each q in new_states do for all c in ∑ do temp := temp ∪ {p such that p=δ(q,c)}; end; end; new_states := temp \ reachable_states; reachable_states := reachable_states ∪ new_states;} while(new_states ≠ the empty set);unreachable_states := Q \ reachable_states;وضعیت‌های غیرقابل دسترس از دی‌ای‌اف می‌توانند حذف شوند بدون اینکه روی زبانی که می‌پذیرد اثر بگذارد.وضعیت‌های غیر قابل تشخیص.الگوریتم هوپکرافت.یک الگوریتم برای ادغام کردن وضعیت‌های غیرقابل تشخیص از یک دی‌اف‌ای، بر طبق ، بر اساس تصفیهٔ بخشی است، بخش‌کردن وضعیت‌های دی‌اف‌ای به گروه‌ها بوسیلهٔ رفتارشان. این گروه‌ها کلاس‌های هم‌ارزی از رابطه هم‌ارزی مای‌هیل-نرود را بیان می‌کنند، که به موجب آن هر دو وضعیت از یک بخش هم‌ارزند اگر برای هر رشتهٔ ورودی رفتار مشابه داشته باشند. یعنی، برای هر دو وضعیت و که به یک کلاس هم‌ارزی در بخش متعلق باشند، حالتی خواهد بود که برای هر ورودی کلمهٔ ، اگر فردگذارهای تعیین شده با از دو وضعیت و را دنبال کند یا به قبول وضعیت‌ها در دو حالت می‌رسد یا به رد دو وضعیت در هر دو حالت می‌رسد؛ ممکن نیست برای که را یک وضعیت پذیرش بگیرد و رایک وضعیت رد بگیرد یا برعکس.شبه‌کد زیر الگوریتم را توضیح می‌دهد:P := {F, Q \ F};W := {F};while (W is not empty) do choose and remove a set A from W for each c in ∑ do let X be the set of states for which a transition on c leads to a state in A for each set Y in P for which X ∩ Y is nonempty and Y \ X is nonempty do replace Y in P by the two sets X ∩ Y and Y \ X if Y is in W replace Y in W by the same two sets else if |X ∩ Y| &lt;= |Y \ X| add X ∩ Y to W else add Y \ X to W end; end;end;الگوریتم بایک بخش که خیلی زمخت است شروع می‌شود: هر جفت وضعیت که معادل باشند بر طبق رابطهٔ مای هیل- نرود به یک مجموعهٔ یکسان در بخش متعلق است، ولی جفت‌هایی که نامعادلند نیز ممکن است به یک مجموعه تعلق داشته باشند. این به تدریج بخش را به تعداد زیادتری از مجموعه‌های کوچکتر تصفیه می‌کند، در هر گام مجموعه‌های وضعیت‌ها را به جفت‌های زیر مجموعه تفکیک می‌کند که لزوماً نامعادلند. بخش اولیه تفکیک وضعیت‌ها به دو زیر مجموعه از وصعیت‌هاست که به وضوح یک رفتار مشابه یکدیگر ندارند: پذیرش وضعیت‌ها و رد وضعیت‌ها. سپس الگوریتم به‌طور تکراری مجموعهٔ formula_1 از بخش جاری و یک علامت ورودی formula_2 را انتخاب می‌کند، و هر مجموعه از بخش را به دو زیر مجموعهٔ(احتمالاً خالی) تقسیم می‌کند: زیر مجموعهٔ وضعیت‌ها که به formula_1 روی علامت ورودی formula_2 منجر می‌شود، و زیر مجموعهٔ وضعیت‌ها که به formula_1 منجر نمی‌شود. چون formula_1 تاکنون به داشتن رفتارهای متفاوت نسبت به مجموعه‌های دیگر بخش مشخص می‌شود، زیر مجموعه‌هایی که به formula_1 منجر می‌شوند نیز رفتار متفاوتی از آن‌هایی که به formula_1 منجر نمی‌شوند دارند. وقتی که هیچ تقسیمی از این نوع نمی‌توان یافت، الگوریتم لم را خاتمه می‌دهد.با داشتن یک کاراکتر ثابت formula_2 و یک کلاس هم‌ارزی formula_10 که به کلاس‌های هم‌ارزی formula_11 و formula_12 تقسیم می‌شود، فقط یکی از formula_11 یا formula_12 لازم است تا کل بخش را تصیفیه کند. مثال: فرض کنید یک کلاس هم‌ارزی formula_10 داریم که به کلاس‌های هم‌ارزی formula_11 و formula_12 تقسیم می‌شود. فرض کنید کلاس‌های formula_18 ، formula_19 و formula_20 نیز داریم ؛formula_19 و formula_18وضعیت‌ها یی باانتقال به formula_11 روی کاراکتر formula_2 دارند، در حالیکه formula_20 انتقال‌هایی به formula_12 روی کاراکتر formula_2 دارد. به موجب لم، می‌توانیم یا formula_11 یا formula_12 را به عنوان تمیزدهنده انتخاب کنیم، بگذارید بگوییم formula_11 . سپس وضعیت‌های formula_19 وformula_18 با انتقال‌هایشان به formula_11 تقسیم می‌شوند. ولی formula_20، که به formula_11 اشاره ندارد، به سادگی در هنگام تکرار جاری الگوریتم تقسیم نمی‌شود؛به وسیلهٔ تمیز دهنده‌های دیگر تصفیه خواهد شد.هر formula_11 یاformula_12 لازم است که به کلاس‌های مورد اشارهٔ مانند formula_19، formula_18 وformula_20 به‌طورصحیح تقسیم شود-- زیر مجموعه‌ها مشاهده انجام نخواهند داد.غایت هدف جملهٔ اگر(اگر formula_41 درformula_42 باشد) وصله کردن formula_43 ، مجموعهٔ تمیز دهنده‌هاست. در جملهٔ قبل در الگوریتم می‌بینیم که formula_10 فقط تقسیم شده‌است. اگر formula_10 در formula_43 باشد، فقط کنار گذاشته شده‌است به عنوان وسیله‌ای که کلاس‌ها را در تکرارهای آینده تقسیم کند. بنابراین formula_10 بایستی بوسیلهٔ هردو تقسیمات جایگزین شود به علت مشاهدهٔ بالا. امااگر formula_10 در formula_43 نباشد، تنها یکی از دو تقسیم، نه هر دو، لازم است که به formula_43 اضافه شود به علت لم بالا. انتخاب کوچکترین از دو تقسیم تضمین می‌کند که اضافه‌کردن جدید به formula_43 بیشتر از نصف اندازهٔ formula_10 نیست؛ این هستهٔ الگوریتم هوپکرافت است: چگونه سرعت می‌گیرد، چنانچه در پاراگراف بعد می‌آید.بدترین حالت زمان اجرای این الگوریتم استformula_53، که formula_54 تعداد وضعیت‌ها وformula_55 اندازهٔ الفباست. این محدودیت از این حقیقت ناشی می‌شود که، برای هر یک از انتقال‌های formula_56 از اتوماتا، مجموعه‌هایی که از formula_57 گرفته شده‌است که شامل وضعیت هدف از انتقال است اندازه‌هایی دارد که نسبت به یکدیگر با ضریب یک یا دو کاهش می یابد، بنابراین هر انتقال در formula_58 از گام‌های تقسیم الگوریتم شرکت می‌کند. ساختمان دادهٔ تصفیهٔ بخش به هر گام تقسیم‌کننده اجازه می‌دهد که در زمانی متناسب باتعداد انتقال‌هایی که در آن شرکت می‌کند اجرا شود.این کاراترین الگوریتم شناخته شده را برای حل مسئله به جا می‌گذارد، و برای توزیع‌های خاصی از ورودی‌ها متوسط حالت پیچیدگی حتی بهتر است،formula_59. یک‌بار الگوریتم هوپکرافت بکار رفته‌است تا وضعیت ورودی دی‌اف‌ای به کلاس‌های هم‌ارزی گروه شوند، مینیمم دی‌اف‌ای می‌تواندبا تشکیل یک وضعیت برای هر کلاس هم‌ارزی ساخته شود. اگر formula_60 مجموعه‌ای وضعیت‌ها در formula_61 ، و formula_55 یک وضعیت در formula_60، و formula_2 یک کاراکتر ورودی باشد، انتقال در مینیمم دی‌اف‌ای از وضعیت برای formula_60، روی ورودی formula_2 ، می‌رود به سوی مجموعه‌ای شامل وضعیتی که اتومات ورودی برود از وضعیت formula_55 روی ورودی formula_2 . وضعیت اولیهٔ دی‌اف‌ای مینیمم آنی است که شامل وضعیت اولیهٔ ورودی دی‌راف‌ای است، و وضعیت‌های پذیرفتهٔ دی‌اف‌ای مینیمم آن‌هایی هستند که اعضایشان وضعیت‌های پذیرفتهٔ دی‌اف‌ای مینیمم هستند.الگوریتم مور.الگوریتم مور برای دی‌اف‌ای مینیمم مربوط به ادوارد اف مور( ۱۹۵۶) است. مانند الگوریتم هوپکرافت، بخشی را حفظ می‌کند که جداسازی پذیرش از وضعیت‌های رد شروع می‌کند، و پیوسته بخش راتصفیه می‌کند تا وقتی که هیج تصفیهٔ دیگری بتوان انجام داد. در هر گام، این جایگزین بخش جاری با تصفیهٔ معمول زمخت از formula_69 بخش می‌شود، یکی از آن‌ها جاری است و دیگران پیش تصویرهایی هستند از بخش جاری تحت توابع انتقال برای علامت‌های ورودی. وقتی این جایگزینی بخش جاری راتغییر ندهد الگوریتم پایان می‌پذیرد.بدترین حالت پیچیدگی زمانش : هر گام از الگوریتم می‌تواند در زمان formula_70 با بکار بردن تنوعی از مرتب‌سازی مبنا برای دوباره تنظیم کردن وضعیت‌هااجرا شود طوری‌که وضعیت‌ها در یک مجموعه از بخش جدید به ترتیب متوالی هستند، و حداکثر formula_54 گام وجود دارند چون هر کدام به جز آخری تعداد مجموعه‌ها در بخش را افزایش می‌دهد. مثال‌هایی از مسئلهٔ مینیمم‌سازی دی‌اف‌ای که رفتار حالت بدتر را موجب می‌شود مشابه آن‌ها برای الگوریتم هوپکرافت است.تعداد گامهایی که الگوریتم اجرا می‌شود می‌تواند خیلی کوچکتر از formula_54 شود، بنابراین به‌طور متوسط (برای ثابت formula_55) اجرایش روی formula_74 یا حتی formula_59 بستگی دارد به توزیع تصادفی روی اتومات که انتخاب شده‌است تا رفتار حالت متوسط الگوریتم را مدل سازی کند.الگوریتم برزوزسکی.چنانچه برزوزسکی(۱۹۶۳)مشاهده کرد، با وارون کردن لبه‌های یک دی‌اف‌ای یک اتوماتای متناهی غیر قطعی(NFA) برای وارون کردن زبان اصلی ایجاد می‌کند، و با تبدیل این ان‌اف‌ای را با بکار بردن ساختار مجموعۀ توانی استاندارد به یک دی‌اف‌ای (ساختن تنها وضعیت‌های در دسترس از دی‌اف‌ای تبدیل شده)برای همان زبان وارون شده به یک دی‌اف‌ای مینیمم منجر می‌شود. با تکرار این عمل برای بار دوم یک دی‌اف‌ای مینیمم برای زبان اصلی ایجاد می‌شود. بدترین حالت پیچیدگی الگوریتم برزورسکی نمایی است، چون زبان‌های منظمی وجود دارند که برای آن‌ها دی‌اف‌ای مینیمم وارون به‌طور نمایی بزرگتر از دی‌اف‌ای مینیمم زبان است، ولی به‌طور مکرر اجرا می‌شود بهتر از این که حالت بدتر که پیشنهاد می‌کند.مینیمم‌سازی ان‌اف‌ای.در حالیکه روندهای بالا برای دی‌اف‌ای‌ها ایجاد می‌شوند، روش بخش کردن برای اتوماتای متناهی غیرقطعی (ان‌اف‌ای‌ها) کار نمی‌کند. در حالیکه یک جستجوی جامع ممکن است یک ان‌اف‌ای را مینیمم سازد، یافتن یک الگوریتم با زمان چند جمله‌ای برای مینیمم‌سازی ان‌اف‌ای‌ها غیرممکن است، مگر اینکه حدس حل نشدۀ formula_76 در تئوری پیچیدگی محاسباتی درست باشد. باور بر این است که این حدس به‌طور گسترده اشتباه است.