موضوع مقاله: مینیم‌سازی دی‌اف‌ای | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # مینیم‌سازی دی‌اف‌ای | مقدمه: در نظریه اتوماتا (شاخه‌ای از علوم کامپیوتر)، مینیمم‌سازی کار انتقال یک اتوماتای متناهی قطعی (دی‌اف‌ای) به یک دی‌اف‌ای معادل است که دارای تعداد وضعیت‌های مینیمم است. | ## بخش 1: مینیم‌سازی دی‌اف‌ای | در اینجا، دو دی‌اف‌ای معادل نامیده می‌شوند اگر آن‌ها یک زبان منظم یکسان را مشخص کنند. دی‌اف‌ای مینیمم، مینیمم هزینهٔ محاسبات برای کارهایی مانند تطبیق الگو را تضمین می‌کند. دو دسته از وضعیت‌ها وجود دارند که بدون اینکه روی زبان اثر بگذارند می‌توانند از دی‌اف‌ای اصلی حذف/ادغام شوند تا مینیمم‌سازی آن را بپذیرد. وضعیت‌های دست نیافتنی آن‌هایی هستند که برای هر رشتهٔ ورودی دور از دسترس وضعیت‌های اولیهٔ دی‌اف‌ای باشند. وضعیت‌های غیرقابل تمیز آن‌هایی هستند که برای هر رشتهٔ ورودی از یکدیگر تمیز داده نشوند. مینیمم‌سازی دی‌اف‌ای، در ارتباط با حذف/ ادغام وضعیت‌های مربوط معمولاً در سه مرحله انجام می‌شود. چون حذف وضعیت‌های غیرقابل تمیز از جنبهٔ محاسبات گران‌ترین است، معمولاً در آخرین مرحله انجام می‌شود. وضعیت‌های غیر قابل دسترس وضعیت p از دی‌اف‌ای (M=(Q, Σ, δ, q0, F غیرقابل دسترس است اگر هیچ رشته‌ای چون w در *∑ وجود نداشته باشد که برای آن (p=δ(q0, w باشد. وضعیت‌های غیر قابل تشخیص الگوریتم هوپکرافت یک الگوریتم برای ادغام کردن وضعیت‌های غیرقابل تشخیص از یک دی‌اف‌ای، بر طبق ، بر اساس تصفیهٔ بخشی است، بخش‌کردن وضعیت‌های دی‌اف‌ای به گروه‌ها بوسیلهٔ رفتارشان. این گروه‌ها کلاس‌های هم‌ارزی از رابطه هم‌ارزی مای‌هیل-نرود را بیان می‌کنند، که به موجب آن هر دو وضعیت از یک بخش هم‌ارزند اگر برای هر رشتهٔ ورودی رفتار مشابه داشته باشند. یعنی، برای هر دو وضعیت و که به یک کلاس هم‌ارزی در بخش متعلق باشند، حالتی خواهد بود که برای هر ورودی کلمهٔ ، اگر فردگذارهای تعیین شده با از دو وضعیت و را دنبال کند یا به قبول وضعیت‌ها در دو حالت می‌رسد یا به رد دو وضعیت در هر دو حالت می‌رسد؛ ممکن نیست برای که را یک وضعیت پذیرش بگیرد و رایک وضعیت رد بگیرد یا برعکس. این به تدریج بخش را به تعداد زیادتری از مجموعه‌های کوچکتر تصفیه می‌کند، در هر گام مجموعه‌های وضعیت‌ها را به جفت‌های زیر مجموعه تفکیک می‌کند که لزوماً نامعادلند. | ## بخش 2: مینیم‌سازی دی‌اف‌ای | بخش اولیه تفکیک وضعیت‌ها به دو زیر مجموعه از وصعیت‌هاست که به وضوح یک رفتار مشابه یکدیگر ندارند: پذیرش وضعیت‌ها و رد وضعیت‌ها. سپس الگوریتم به‌طور تکراری مجموعهٔ از بخش جاری و یک علامت ورودی را انتخاب می‌کند، و هر مجموعه از بخش را به دو زیر مجموعهٔ(احتمالاً خالی) تقسیم می‌کند: زیر مجموعهٔ وضعیت‌ها که به روی علامت ورودی منجر می‌شود، و زیر مجموعهٔ وضعیت‌ها که به منجر نمی‌شود. چون تاکنون به داشتن رفتارهای متفاوت نسبت به مجموعه‌های دیگر بخش مشخص می‌شود، زیر مجموعه‌هایی که به منجر می‌شوند نیز رفتار متفاوتی از آن‌هایی که به منجر نمی‌شوند دارند. با داشتن یک کاراکتر ثابت و یک کلاس هم‌ارزی که به کلاس‌های هم‌ارزی و تقسیم می‌شود، فقط یکی از یا لازم است تا کل بخش را تصیفیه کند. فرض کنید کلاس‌های ، و نیز داریم ؛ و وضعیت‌ها یی باانتقال به روی کاراکتر دارند، در حالیکه انتقال‌هایی به روی کاراکتر دارد. ولی ، که به اشاره ندارد، به سادگی در هنگام تکرار جاری الگوریتم تقسیم نمی‌شود؛به وسیلهٔ تمیز دهنده‌های دیگر تصفیه خواهد شد. هر یا لازم است که به کلاس‌های مورد اشارهٔ مانند ، و به‌طورصحیح تقسیم شود-- زیر مجموعه‌ها مشاهده انجام نخواهند داد. اگر در باشد، فقط کنار گذاشته شده‌است به عنوان وسیله‌ای که کلاس‌ها را در تکرارهای آینده تقسیم کند. امااگر در نباشد، تنها یکی از دو تقسیم، نه هر دو، لازم است که به اضافه شود به علت لم بالا. انتخاب کوچکترین از دو تقسیم تضمین می‌کند که اضافه‌کردن جدید به بیشتر از نصف اندازهٔ نیست؛ این هستهٔ الگوریتم هوپکرافت است: چگونه سرعت می‌گیرد، چنانچه در پاراگراف بعد می‌آید. این محدودیت از این حقیقت ناشی می‌شود که، برای هر یک از انتقال‌های از اتوماتا، مجموعه‌هایی که از گرفته شده‌است که شامل وضعیت هدف از انتقال است اندازه‌هایی دارد که نسبت به یکدیگر با ضریب یک یا دو کاهش می یابد، بنابراین هر انتقال در از گام‌های تقسیم الگوریتم شرکت می‌کند. ساختمان دادهٔ تصفیهٔ بخش به هر گام تقسیم‌کننده اجازه می‌دهد که در زمانی متناسب باتعداد انتقال‌هایی که در آن شرکت می‌کند اجرا شود.; این کاراترین الگوریتم شناخته شده را برای حل مسئله به جا می‌گذارد، و برای توزیع‌های خاصی از ورودی‌ها متوسط حالت پیچیدگی حتی بهتر است،. | ## بخش 3: مینیم‌سازی دی‌اف‌ای | یک‌بار الگوریتم هوپکرافت بکار رفته‌است تا وضعیت ورودی دی‌اف‌ای به کلاس‌های هم‌ارزی گروه شوند، مینیمم دی‌اف‌ای می‌تواندبا تشکیل یک وضعیت برای هر کلاس هم‌ارزی ساخته شود. اگر مجموعه‌ای وضعیت‌ها در ، و یک وضعیت در ، و یک کاراکتر ورودی باشد، انتقال در مینیمم دی‌اف‌ای از وضعیت برای ، روی ورودی ، می‌رود به سوی مجموعه‌ای شامل وضعیتی که اتومات ورودی برود از وضعیت روی ورودی . وضعیت اولیهٔ دی‌اف‌ای مینیمم آنی است که شامل وضعیت اولیهٔ ورودی دی‌راف‌ای است، و وضعیت‌های پذیرفتهٔ دی‌اف‌ای مینیمم آن‌هایی هستند که اعضایشان وضعیت‌های پذیرفتهٔ دی‌اف‌ای مینیمم هستند. الگوریتم مور الگوریتم مور برای دی‌اف‌ای مینیمم مربوط به ادوارد اف مور( ۱۹۵۶) است. مانند الگوریتم هوپکرافت، بخشی را حفظ می‌کند که جداسازی پذیرش از وضعیت‌های رد شروع می‌کند، و پیوسته بخش راتصفیه می‌کند تا وقتی که هیج تصفیهٔ دیگری بتوان انجام داد. در هر گام، این جایگزین بخش جاری با تصفیهٔ معمول زمخت از بخش می‌شود، یکی از آن‌ها جاری است و دیگران پیش تصویرهایی هستند از بخش جاری تحت توابع انتقال برای علامت‌های ورودی. بدترین حالت پیچیدگی زمانش : هر گام از الگوریتم می‌تواند در زمان با بکار بردن تنوعی از مرتب‌سازی مبنا برای دوباره تنظیم کردن وضعیت‌هااجرا شود طوری‌که وضعیت‌ها در یک مجموعه از بخش جدید به ترتیب متوالی هستند، و حداکثر گام وجود دارند چون هر کدام به جز آخری تعداد مجموعه‌ها در بخش را افزایش می‌دهد. مثال‌هایی از مسئلهٔ مینیمم‌سازی دی‌اف‌ای که رفتار حالت بدتر را موجب می‌شود مشابه آن‌ها برای الگوریتم هوپکرافت است. تعداد گامهایی که الگوریتم اجرا می‌شود می‌تواند خیلی کوچکتر از شود، بنابراین به‌طور متوسط (برای ثابت ) اجرایش روی یا حتی بستگی دارد به توزیع تصادفی روی اتومات که انتخاب شده‌است تا رفتار حالت متوسط الگوریتم را مدل سازی کند. الگوریتم برزوزسکی چنانچه برزوزسکی(۱۹۶۳)مشاهده کرد، با وارون کردن لبه‌های یک دی‌اف‌ای یک اتوماتای متناهی غیر قطعی(NFA) برای وارون کردن زبان اصلی ایجاد می‌کند، و با تبدیل این ان‌اف‌ای را با بکار بردن ساختار مجموعۀ توانی استاندارد به یک دی‌اف‌ای (ساختن تنها وضعیت‌های در دسترس از دی‌اف‌ای تبدیل شده)برای همان زبان وارون شده به یک دی‌اف‌ای مینیمم منجر می‌شود. | ## جمع‌بندی | مینیمم‌سازی ان‌اف‌ای در حالیکه روندهای بالا برای دی‌اف‌ای‌ها ایجاد می‌شوند، روش بخش کردن برای اتوماتای متناهی غیرقطعی (ان‌اف‌ای‌ها) کار نمی‌کند.