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

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

مثال دی‌اف‌ای. در وضعیت 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₁ و p₂ که به یک کلاس هم‌ارزی در بخش P متعلق باشند، حالتی خواهد بود که برای هر ورودی کلمهٔ w، اگر فردگذارهای تعیین شده با w از دو وضعیت p₁ و p₂ را دنبال کند یا به قبول وضعیت‌ها در دو حالت می‌رسد یا به رد دو وضعیت در هر دو حالت می‌رسد؛ ممکن نیست برای w که p₁ را یک وضعیت پذیرش بگیرد و p₂ رایک وضعیت رد بگیرد یا برعکس.

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

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;

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

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

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

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

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

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

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

الگوریتم مور

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

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

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

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

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

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

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

پانویس

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)
5. (Berstel و دیگران 2010).
6. For instance, the language of binary strings whose nth symbol is a one requires only n + 1 states, but its reversal requires 2ⁿ states. (Leiss 1981) provides a ternary n-state DFA whose reversal requires 2ⁿ 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.

منابع

• 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, Cambridge University Press, ISBN 978-0-521-84425-3, Zbl 1188.68177

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

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