مینیم‌سازی دی‌اف‌ای

در نظریه اتوماتا (شاخه‌ای از علوم کامپیوتر)، مینیمم‌سازی کار انتقال یک اتوماتای متناهی قطعی (دی‌اف‌ای) به یک دی‌اف‌ای معادل است که دارای تعداد وضعیت‌های مینیمم است. در اینجا، دو دی‌اف‌ای معادل نامیده می‌شوند اگر آن‌ها یک زبان منظم یکسان را مشخص کنند. چند الگوریتم مختلف که این کار را انجام می‌دهند شناخته شده‌اند و در متون استاندارد در مورد نظریهٔ اتوماتا توضیح داده می‌شوند.^[۱]

الگو:Multiple image

دی اف ای مینیمم

برای هر زبان منظم که به وسیلهٔ یک دی‌اف‌ای می‌تواند پذیرفته شود، یک دی‌اف‌ای با تعداد وضعیت‌های مینیمم وجود دارد و این دی‌اف‌ای منحصر بفرد است (مگر اینکه به آن وضعیت‌ها نام‌های مختلفی بتوان داد)^[۲]. دی‌اف‌ای مینیمم، مینیمم هزینهٔ محاسبات برای کارهایی مانند تطبیق الگو را تضمین می‌کند.

دو دسته از وضعیت‌ها وجود دارند که بدون اینکه روی زبان اثر بگذارند می‌توانند از دی‌اف‌ای اصلی حذف/ادغام شوند تا مینیمم‌سازی آن را بپذیرد.

وضعیت‌های دست نیافتنی آن‌هایی هستند که برای هر رشتهٔ ورودی دور از دسترس وضعیت‌های اولیهٔ دی‌اف‌ای باشند.
وضعیت‌های غیرقابل تمیز آن‌هایی هستند که برای هر رشتهٔ ورودی از یکدیگر تمیز داده نشوند.

مینیمم‌سازی دی‌اف‌ای، در ارتباط با حذف/ ادغام وضعیت‌های مربوط معمولاً در سه مرحله انجام می‌شود. چون حذف وضعیت‌های غیرقابل تمیز از جنبهٔ محاسبات گران‌ترین است، معمولاً در آخرین مرحله انجام می‌شود.

وضعیت‌های غیر قابل دسترس

وضعیت p از دی‌اف‌ای (M=(Q, Σ, δ, q₀, F غیرقابل دسترس است اگر هیچ رشته‌ای چون w در ^*∑ وجود نداشته باشد که برای آن (p=δ(q₀, 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;

وضعیت‌های غیرقابل دسترس از دی‌ای‌اف می‌توانند حذف شوند بدون اینکه روی زبانی که می‌پذیرد اثر بگذارد.

وضعیت‌های غیر قابل تشخیص

الگوریتم هوپکرافت

یک الگوریتم برای ادغام کردن وضعیت‌های غیرقابل تشخیص از یک دی‌اف‌ای، بر طبق الگو:Harvtxt، بر اساس تصفیهٔ بخشی است، بخش‌کردن وضعیت‌های دی‌اف‌ای به گروه‌ها بوسیلهٔ رفتارشان. این گروه‌ها کلاس‌های هم‌ارزی از رابطه هم‌ارزی مای‌هیل-نرود را بیان می‌کنند، که به موجب آن هر دو وضعیت از یک بخش هم‌ارزند اگر برای هر رشتهٔ ورودی رفتار مشابه داشته باشند. یعنی، برای هر دو وضعیت الگو:Math و الگو:Math که به یک کلاس هم‌ارزی در بخش الگو:Mvar متعلق باشند، حالتی خواهد بود که برای هر ورودی کلمهٔ الگو:Mvar، اگر فردگذارهای تعیین شده با الگو:Mvar از دو وضعیت الگو:Math و الگو:Math را دنبال کند یا به قبول وضعیت‌ها در دو حالت می‌رسد یا به رد دو وضعیت در هر دو حالت می‌رسد؛ ممکن نیست برای الگو:Mvar که الگو:Math را یک وضعیت پذیرش بگیرد و الگو:Math رایک وضعیت رد بگیرد یا برعکس.

شبه‌کد زیر الگوریتم را توضیح می‌دهد:

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| <= |Y \ X|
                         add X ∩ Y to W
                    else
                         add Y \ X to W
          end;
     end;
end;

الگوریتم بایک بخش که خیلی زمخت است شروع می‌شود: هر جفت وضعیت که معادل باشند بر طبق رابطهٔ مای هیل- نرود به یک مجموعهٔ یکسان در بخش متعلق است، ولی جفت‌هایی که نامعادلند نیز ممکن است به یک مجموعه تعلق داشته باشند. این به تدریج بخش را به تعداد زیادتری از مجموعه‌های کوچکتر تصفیه می‌کند، در هر گام مجموعه‌های وضعیت‌ها را به جفت‌های زیر مجموعه تفکیک می‌کند که لزوماً نامعادلند. بخش اولیه تفکیک وضعیت‌ها به دو زیر مجموعه از وصعیت‌هاست که به وضوح یک رفتار مشابه یکدیگر ندارند: پذیرش وضعیت‌ها و رد وضعیت‌ها. سپس الگوریتم به‌طور تکراری مجموعهٔ $A$ از بخش جاری و یک علامت ورودی $c$ را انتخاب می‌کند، و هر مجموعه از بخش را به دو زیر مجموعهٔ(احتمالاً خالی) تقسیم می‌کند: زیر مجموعهٔ وضعیت‌ها که به $A$ روی علامت ورودی $c$ منجر می‌شود، و زیر مجموعهٔ وضعیت‌ها که به $A$ منجر نمی‌شود. چون $A$ تاکنون به داشتن رفتارهای متفاوت نسبت به مجموعه‌های دیگر بخش مشخص می‌شود، زیر مجموعه‌هایی که به $A$ منجر می‌شوند نیز رفتار متفاوتی از آن‌هایی که به $A$ منجر نمی‌شوند دارند. وقتی که هیچ تقسیمی از این نوع نمی‌توان یافت، الگوریتم لم را خاتمه می‌دهد.

با داشتن یک کاراکتر ثابت $c$ و یک کلاس هم‌ارزی $Y$ که به کلاس‌های هم‌ارزی $B$ و $C$ تقسیم می‌شود، فقط یکی از $B$ یا $C$ لازم است تا کل بخش را تصیفیه کند. ^[۳]

مثال: فرض کنید یک کلاس هم‌ارزی $Y$ داریم که به کلاس‌های هم‌ارزی $B$ و $C$ تقسیم می‌شود. فرض کنید کلاس‌های $E$ ، $D$ و $F$ نیز داریم ؛ $D$ و $E$ وضعیت‌ها یی باانتقال به $B$ روی کاراکتر $c$ دارند، در حالیکه $F$ انتقال‌هایی به $C$ روی کاراکتر $c$ دارد. به موجب لم، می‌توانیم یا $B$ یا $C$ را به عنوان تمیزدهنده انتخاب کنیم، بگذارید بگوییم $B$ . سپس وضعیت‌های $D$ و $E$ با انتقال‌هایشان به $B$ تقسیم می‌شوند. ولی $F$ ، که به $B$ اشاره ندارد، به سادگی در هنگام تکرار جاری الگوریتم تقسیم نمی‌شود؛به وسیلهٔ تمیز دهنده‌های دیگر تصفیه خواهد شد.

هر $B$ یا $C$ لازم است که به کلاس‌های مورد اشارهٔ مانند $D$ ، $E$ و $F$ به‌طورصحیح تقسیم شود-- زیر مجموعه‌ها مشاهده انجام نخواهند داد.

غایت هدف جملهٔ اگر(اگر $y$ در $w$ باشد) وصله کردن $W$ ، مجموعهٔ تمیز دهنده‌هاست. در جملهٔ قبل در الگوریتم می‌بینیم که $Y$ فقط تقسیم شده‌است. اگر $Y$ در $W$ باشد، فقط کنار گذاشته شده‌است به عنوان وسیله‌ای که کلاس‌ها را در تکرارهای آینده تقسیم کند. بنابراین $Y$ بایستی بوسیلهٔ هردو تقسیمات جایگزین شود به علت مشاهدهٔ بالا. امااگر $Y$ در $W$ نباشد، تنها یکی از دو تقسیم، نه هر دو، لازم است که به $W$ اضافه شود به علت لم بالا. انتخاب کوچکترین از دو تقسیم تضمین می‌کند که اضافه‌کردن جدید به $W$ بیشتر از نصف اندازهٔ $Y$ نیست؛ این هستهٔ الگوریتم هوپکرافت است: چگونه سرعت می‌گیرد، چنانچه در پاراگراف بعد می‌آید.

بدترین حالت زمان اجرای این الگوریتم است $O (n s l o g n)$ ، که $n$ تعداد وضعیت‌ها و $s$ اندازهٔ الفباست. این محدودیت از این حقیقت ناشی می‌شود که، برای هر یک از انتقال‌های $n s$ از اتوماتا، مجموعه‌هایی که از $Q$ گرفته شده‌است که شامل وضعیت هدف از انتقال است اندازه‌هایی دارد که نسبت به یکدیگر با ضریب یک یا دو کاهش می یابد، بنابراین هر انتقال در $O (l o g n)$ از گام‌های تقسیم الگوریتم شرکت می‌کند. ساختمان دادهٔ تصفیهٔ بخش به هر گام تقسیم‌کننده اجازه می‌دهد که در زمانی متناسب باتعداد انتقال‌هایی که در آن شرکت می‌کند اجرا شود.^[۴]این کاراترین الگوریتم شناخته شده را برای حل مسئله به جا می‌گذارد، و برای توزیع‌های خاصی از ورودی‌ها متوسط حالت پیچیدگی حتی بهتر است، $O (n l o g l o g n)$ . ^[۵]

یک‌بار الگوریتم هوپکرافت بکار رفته‌است تا وضعیت ورودی دی‌اف‌ای به کلاس‌های هم‌ارزی گروه شوند، مینیمم دی‌اف‌ای می‌تواندبا تشکیل یک وضعیت برای هر کلاس هم‌ارزی ساخته شود. اگر $S$ مجموعه‌ای وضعیت‌ها در $P$ ، و $s$ یک وضعیت در $S$ ، و $c$ یک کاراکتر ورودی باشد، انتقال در مینیمم دی‌اف‌ای از وضعیت برای $S$ ، روی ورودی $c$ ، می‌رود به سوی مجموعه‌ای شامل وضعیتی که اتومات ورودی برود از وضعیت $s$ روی ورودی $c$ . وضعیت اولیهٔ دی‌اف‌ای مینیمم آنی است که شامل وضعیت اولیهٔ ورودی دی‌راف‌ای است، و وضعیت‌های پذیرفتهٔ دی‌اف‌ای مینیمم آن‌هایی هستند که اعضایشان وضعیت‌های پذیرفتهٔ دی‌اف‌ای مینیمم هستند.

الگوریتم مور

الگوریتم مور برای دی‌اف‌ای مینیمم مربوط به ادوارد اف مور( ۱۹۵۶) است. مانند الگوریتم هوپکرافت، بخشی را حفظ می‌کند که جداسازی پذیرش از وضعیت‌های رد شروع می‌کند، و پیوسته بخش راتصفیه می‌کند تا وقتی که هیج تصفیهٔ دیگری بتوان انجام داد. در هر گام، این جایگزین بخش جاری با تصفیهٔ معمول زمخت از $s + 1$ بخش می‌شود، یکی از آن‌ها جاری است و دیگران پیش تصویرهایی هستند از بخش جاری تحت توابع انتقال برای علامت‌های ورودی. وقتی این جایگزینی بخش جاری راتغییر ندهد الگوریتم پایان می‌پذیرد.

بدترین حالت پیچیدگی زمانش الگو:Math: هر گام از الگوریتم می‌تواند در زمان $O (n s)$ با بکار بردن تنوعی از مرتب‌سازی مبنا برای دوباره تنظیم کردن وضعیت‌هااجرا شود طوری‌که وضعیت‌ها در یک مجموعه از بخش جدید به ترتیب متوالی هستند، و حداکثر $n$ گام وجود دارند چون هر کدام به جز آخری تعداد مجموعه‌ها در بخش را افزایش می‌دهد. مثال‌هایی از مسئلهٔ مینیمم‌سازی دی‌اف‌ای که رفتار حالت بدتر را موجب می‌شود مشابه آن‌ها برای الگوریتم هوپکرافت است.

تعداد گامهایی که الگوریتم اجرا می‌شود می‌تواند خیلی کوچکتر از $n$ شود، بنابراین به‌طور متوسط (برای ثابت $s$ ) اجرایش روی $O (n l o g n)$ یا حتی $O (n l o g l o g n)$ بستگی دارد به توزیع تصادفی روی اتومات که انتخاب شده‌است تا رفتار حالت متوسط الگوریتم را مدل سازی کند.^[۵]

الگوریتم برزوزسکی

چنانچه برزوزسکی(۱۹۶۳)مشاهده کرد، با وارون کردن لبه‌های یک دی‌اف‌ای یک اتوماتای متناهی غیر قطعی(NFA) برای وارون کردن زبان اصلی ایجاد می‌کند، و با تبدیل این ان‌اف‌ای را با بکار بردن ساختار مجموعۀ توانی استاندارد به یک دی‌اف‌ای (ساختن تنها وضعیت‌های در دسترس از دی‌اف‌ای تبدیل شده)برای همان زبان وارون شده به یک دی‌اف‌ای مینیمم منجر می‌شود. با تکرار این عمل برای بار دوم یک دی‌اف‌ای مینیمم برای زبان اصلی ایجاد می‌شود. بدترین حالت پیچیدگی الگوریتم برزورسکی نمایی است، چون زبان‌های منظمی وجود دارند که برای آن‌ها دی‌اف‌ای مینیمم وارون به‌طور نمایی بزرگتر از دی‌اف‌ای مینیمم زبان است،^[۶] ولی به‌طور مکرر اجرا می‌شود بهتر از این که حالت بدتر که پیشنهاد می‌کند.^[۵]

مینیمم‌سازی ان‌اف‌ای

در حالیکه روندهای بالا برای دی‌اف‌ای‌ها ایجاد می‌شوند، روش بخش کردن برای اتوماتای متناهی غیرقطعی (ان‌اف‌ای‌ها) کار نمی‌کند. در حالیکه یک جستجوی جامع ممکن است یک ان‌اف‌ای را مینیمم سازد، یافتن یک الگوریتم با زمان چند جمله‌ای برای مینیمم‌سازی ان‌اف‌ای‌ها غیرممکن است، مگر اینکه حدس حل نشدۀ $P = P S P A C E$ در تئوری پیچیدگی محاسباتی درست باشد.^[۷] باور بر این است که این حدس به‌طور گسترده اشتباه است.

پانویس

الگو:پانویس

منابع

پیوند به بیرون

مینیمم‌سازی دی‌اف‌ای بوسیلهٔ نظریه مای‌هیل-نرود

↑ Hopcroft, Ullman (1979)
↑ الگو:Harvtxt, Section 4.4.3, "Minimization of DFA's", p. 159.
↑ Based on Corollary 10 of الگو:Harvtxt
↑ الگو:Harvtxt; الگو:Harvtxt
↑ ^۵٫۰ ^۵٫۱ ^۵٫۲ الگو:Harvtxt.
↑ For instance, the language of binary strings whose الگو:Mvarth symbol is a one requires only الگو:Math states, but its reversal requires الگو:Math states. الگو:Harvtxt provides a ternary الگو:Mvar-state DFA whose reversal requires الگو:Math states, the maximum possible. For additional examples and the observation of the connection between these examples and the worst-case analysis of Brzozowski's algorithm, see الگو:Harvtxt.
↑ الگو:Harvtxt, Section 4.4, Figure labeled "Minimizing the States of an NFA", p. 163.

[1] Hopcroft, Ullman (1979)

[2] الگو:Harvtxt, Section 4.4.3, "Minimization of DFA's", p. 159.

[3] Based on Corollary 10 of الگو:Harvtxt

[4] الگو:Harvtxt; الگو:Harvtxt

[bbcf-5] ۵٫۰ ^۵٫۱ ^۵٫۲ الگو:Harvtxt.

[6] For instance, the language of binary strings whose الگو:Mvarth symbol is a one requires only الگو:Math states, but its reversal requires الگو:Math states. الگو:Harvtxt provides a ternary الگو:Mvar-state DFA whose reversal requires الگو:Math states, the maximum possible. For additional examples and the observation of the connection between these examples and the worst-case analysis of Brzozowski's algorithm, see الگو:Harvtxt.

[7] الگو:Harvtxt, Section 4.4, Figure labeled "Minimizing the States of an NFA", p. 163.

[۱]

[۲]

[۳]

[۴]

[۵]

[۶]

[۷]