مینیم‌سازی دی‌اف‌ای: تفاوت میان نسخه‌ها

محتوای حذف‌شده محتوای افزوده‌شده

درخط

نسخهٔ ‏۲۱ ژانویهٔ ۲۰۱۵، ساعت ۱۱:۱۸

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

مثال دی‌اف‌ای. در وضعیت c، برای هر رشتهٔ ورودی همان رفتار وضعیت d یا e را بیان می‌کند.به طور مشابه، وضعیت‌های a و b غیر‌قابل تمیزند. دی‌اف‌ای وضعیت‌های دست نیافتنی ندارد.

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

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

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

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

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

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

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

وضعیت 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;

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

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

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

یک الگوریتم برای ادغام کردن وضعیت‌های غیرقابل تشخیص از یک دی‌اف‌ای، بر طبق (هوپکرافت ۱۹۷۱)، بر اساس تصفیۀ بخشی است، بخش‌کردن وضعیت‌های دی‌اف‌ای به گروه‌ها بوسیلۀ رفتارشان. این گروه‌ها کلاس‌های هم‌ارزی از رابطه هم‌ارزی مای‌هیل-نرود را بیان می‌کنند، که به موجب آن هر دو وضعیت از یک بخش هم‌ارزند اگر برای هر رشتۀ ورودی رفتار مشابه داشته باشند. یعنی، برای هر دو وضعیت $p 1$ و $p 2$ که به یک کلاس هم‌ارزی در بخش $P$ متعلق باشند، حالتی خواهد بود که برای هر ورودی کلمۀ $w$ ، اگر فرد‌گذار‌های تعیین شده با $w$ از دو وضعیت $p 1$ و $p 2$ را دنبال کند یا به قبول وضعیت‌ها در دو حالت می‌رسد یا به رد دو وضعیت در هر دو حالت می‌رسد؛ ممکن نیست برای $w$ که $p 1$ را یک وضعیت پذیرش بگیرد و $p 2$ رایک وضعیت رد بگیرد یا برعکس.

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

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(nslogn)$ ،که $n$ تعداد وضعیت ها و $s$ اندازۀ الفباست. این محدودیت از این حقیقت ناشی می‌شود که، برای هر یک از انتقال‌های $ns$ از اتوماتا، مجموعه‌هایی که از $Q$ گرفته شده است که شامل وضعیت هدف از انتقال است اندازه‌هایی دارد که نسبت به یکدیگر با ضریب یک یا دو کاهش می یابد،بنابراین هر انتقال در $O(logn)$ از گام های تقسیم الگوریتم شرکت می کند. ساختمان دادۀ تصفیۀ بخش به هر گام تقسیم کننده اجازه می‌دهد که در زمانی متناسب باتعداد انتقال‌هایی که در آن شرکت می‌کند اجرا شود.^[۴]این کاراترین الگوریتم شناخته شده را برای حل مسئله به جا می‌گذارد، و برای توزیع‌های خاصی از ورودی‌ها متوسط حالت پیچیدگی حتی بهتر است، $O(nloglogn)$ . ^[۵]

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

الگوریتم مور

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

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

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

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

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

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

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

پانویس

↑ Hopcroft, Ullman (1979)
↑ (Hopcroft، Motwani و Ullman 2001), Section 4.4.3, "Minimization of DFA's", p. 159.
↑ Based on Corollary 10 of (Knuutila 2001)
↑ (Hopcroft 1971); (Aho، Hopcroft و Ullman 1974)
↑ ^۵٫۰ ^۵٫۱ ^۵٫۲ (Berstel و دیگران 2010).
↑ For instance, the language of binary strings whose $n$ th symbol is a one requires only $n + 1$ states, but its reversal requires $2 n$ states. (Leiss 1981) provides a ternary $n$ -state DFA whose reversal requires $2 n$ 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 (Câmpeanu و دیگران 2001).
↑ (Hopcroft، Motwani و Ullman 2001), Section 4.4, Figure labeled "Minimizing the States of an NFA", p. 163.

منابع

Aho, Alfred V.; Hopcroft, John E.; Ullman, Jeffrey D. (1974), "4.13 Partitioning", The Design and Analysis of Computer Algorithms, Addison-Wesley, pp. 157–162.
Berstel, Jean; Boasson, Luc; Carton, Olivier; Fagnot, Isabelle (2010), "Minimization of Automata", Automata: from Mathematics to Applications, European Mathematical Society, arXiv:1010.5318
Brzozowski, J. A. (1963), "Canonical regular expressions and minimal state graphs for definite events", Proc. Sympos. Math. Theory of Automata (New York، 1962), Polytechnic Press of Polytechnic Inst. of Brooklyn، Brooklyn، N.Y., pp. 529–561, MR 0175719.
Câmpeanu, Cezar; Culik, Karel، II; Salomaa, Kai; Yu, Sheng (2001), "State Complexity of Basic Operations on Finite Languages", 4th International Workshop on Automata Implementation (WIA '99), Lecture Notes in Computer Science, vol. 2214, Springer-Verlag, pp. 60–70, doi:10.1007/3-540-45526-4_6.
Hopcroft, John (1971), "An $n log n$ algorithm for minimizing states in a finite automaton", Theory of machines and computations (Proc. Internat. Sympos.، Technion، Haifa، 1971), New York: Academic Press, pp. 189–196, MR 0403320
John Hopcroft (1971). An $n log n$ algorithm for minimizing states in a finite automaton (PDF) (Technical Report). Stanford Univ.، CS Dept. {{cite report}}: Unknown parameter |month= ignored (help)
Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D. (2001), Introduction to Automata Theory، Languages، and Computation (2nd ed.), Addison-Wesley.
Knuutila, Timo (2001), "Re-describing an algorithm by Hopcroft", Theoretical Computer Science, 250 (1–2): 333–363, doi:10.1016/S0304-3975(99)00150-4, MR 1795249.
Leiss, Ernst (1981), "Succinct representation of regular languages by Boolean automata" (PDF), Theoretical Computer Science, 13 (3): 323–330, doi:10.1016/S0304-3975(81)80005-9, MR 0603263.
Leiss, Ernst (1985), "Succinct representation of regular languages by Boolean automata II" (PDF), Theoretical Computer Science, 38: 133–136
Moore, Edward F. (1956), "Gedanken-experiments on sequential machines", Automata studies, Annals of mathematics studies، no. 34, Princeton، N. J.: Princeton University Press, pp. 129–153, MR 0078059.
Sakarovitch, Jacques (2009), Elements of automata theory, Translated from the French by Reuben Thomas, انتشارات دانشگاه کمبریج, ISBN 978-0-521-84425-3, Zbl 1188.68177

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

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

[1] Hopcroft, Ullman (1979)

[2] (Hopcroft، Motwani و Ullman 2001), Section 4.4.3, "Minimization of DFA's", p. 159.

[3] Based on Corollary 10 of (Knuutila 2001)

[4] (Hopcroft 1971); (Aho، Hopcroft و Ullman 1974)

[bbcf-5] ۵٫۰ ^۵٫۱ ^۵٫۲ (Berstel و دیگران 2010).

[6] For instance, the language of binary strings whose $n$ th symbol is a one requires only $n + 1$ states, but its reversal requires $2 n$ states. (Leiss 1981) provides a ternary $n$ -state DFA whose reversal requires $2 n$ 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 (Câmpeanu و دیگران 2001).

[7] (Hopcroft، Motwani و Ullman 2001), Section 4.4, Figure labeled "Minimizing the States of an NFA", p. 163.

[۱]

[۲]

[۳]

[۴]

[۵]

[۶]

[۷]