查看“︁确定有限状态自动机最小化”︁的源代码

[[File:DFA_to_be_minimized.jpg|缩略图|确定有限状态自动机 (DFA)的一个例子，状态c对任何输入串都和状态d与e有相同的行为。类似地，状态a和b是等价的。这个DFA没有不可达状态。]]
[[File:Minimized_DFA.jpg|缩略图|等价的最小DFA，等价状态都被合并成了一个。]]
在[[自动机理论]]（[[计算机科学]]的一个分支）中，'''确定有限状态自动机最小化'''是将给定的[[确定有限状态自动机]]（DFA, Deterministic Finite Automaton）改造为等价且拥有最少状态的DFA的过程。这里，两个DFA等价意味着他们识别相同的正则语言。各自动机理论的教材中，已经给出了若干已知的最小化算法。<ref>{{Harvard citation text|Hopcroft|Motwani|Ullman|2001}}, Section 4.4.3, "Minimization of DFA's".</ref>

== 最小DFA ==
对于每个正则语言，都存在一个'''最小自动机'''接受它，即一个有着最小状态数目的DFA，且这个DFA是唯一的（除去状态命名不同的差别）。<ref>{{Harvard citation text|Hopcroft|Ullman|1979}}, Section 3.4, Theorem 3.10, p.67</ref><ref>{{Harvard citation text|Hopcroft|Motwani|Ullman|2001}}, Section 4.4.3, "Minimization of DFA's", p. 159, and p. 164 (remark after Theorem 4.26)</ref> 最小DFA保证了其在模式匹配等计算应用中开销的最小。

在不影响原始DFA所接受语言的情况下，有两类状态可以被移除或合并，以实现最小化过程。
* '''不可达状态'''指DFA在任意输入串下都无法达到的状态。
* '''等价状态'''指在同一输入串下不产生区别的状态。
DFA最小化通常要经历三个步骤，分别对应于相关状态的移除或合并。因为等价状态的消解开销高昂，通常会将其放到最后一步。

== 不可达状态 ==
DFA <math>M=(Q, \Sigma, \delta, q_0, F)</math> 的状态 <math>p</math> 是不可达的，若不存在 <math>\Sigma^*</math> 上的串 <math>w</math>，使得 <math>p=\delta^*(q_0, w)</math>。可达状态可以用如下算法来找到：

<syntaxhighlight lang="ocaml">
let reachable_states := {q0};
let new_states := {q0};
do {
    temp := the empty set;
    for each q in new_states do
        for each 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;
</syntaxhighlight>
将不可达状态从DFA中移去并不会影响其接受的语言。

== 等价状态 ==

=== Hopcroft算法 ===
根据 {{Harvard citation text|Hopcroft|1971}}，以下算法可用来合并等价状态。该算法基于划分细化，按照状态的行为将DFA各状态分组。这些分组即[[迈希尔－尼罗德定理|Myhill-Nerode等价关系]]下的等价类，满足同一等价类中的两个状态在相同的输入下有相同的行为。即对划分中属于同一等价类的任意两个状态 <math>p_1</math> 和 <math>p_2</math>，对所有输入串 <math>w</math>，<math>w</math> 所导致的转移应当始终将 <math>p_1</math> 和 <math>p_2</math> 带到相同的状态，或都接受，或都拒绝。而不应当出现 <math>w</math> 将 <math>p_1</math> 带到了一个接受状态，而将 <math>p_2</math> 带到了一个拒绝状态，反之亦然。

下面以[[伪代码]]形式描述了该算法：

<syntaxhighlight lang="ocaml">
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;
</syntaxhighlight>
算法从一个粗划分开始：在Myhill–Nerode关系下等价的状态对都属于划分中的同一子集，但此时不等价的状态对也可能被划入了同一子集。 上述算法逐渐将划分细化为大量较小的集合，每一步都将各状态集分为不等价的一对子集。起始划分是将那些明显没有相同行为的状态分为接受状态和拒绝状态。随后算法在每一轮都会从当前划分中选中一个集合 <math>A</math> 和一个输入符 <math>c</math>，再将划分中的每个集合分成两个子集（可能为空）：在输入 <math>c</math> 下可以被带到 <math>A</math> 中状态的状态，和在输入 <math>c</math> 下不会被带到 <math>A</math> 中状态的状态。由于 <math>A</math> 已知和划分中其他集合具有不同的行为，<math>A</math> 的子集也具有该性质。当找不到细分的时候，算法终止。

最坏情况下，算法的运行时间是 <math>O(ns\log n)</math>，其中 <math>n</math> 为状态数，<math>s</math> 为字母表大小。这一时间界的得出是由于，对自动机的每 <math>ns</math> 个转移，每步转移在切分步骤中参与了 <math>O(\log n)</math> 的复杂度。划分细分的数据结构可以允许每步切分的操作时间和转移次数成比例。<ref>{{Harvard citation text|Hopcroft|1971}}; {{Harvard citation text|Aho|Hopcroft|Ullman|1974}}</ref> 这一算法仍是解决该问题的已知最有效算法，对某些输入的随机分布，算法平均复杂度的时间界要更好，为 <math>O(\log\log n)</math>.<ref name="bbcf">{{Harvard citation text|Berstel|Boasson|Carton|Fagnot|2010}}.</ref>

当Hopcroft算法已经将DFA中的状态划分为等价类，最小DFA就可以通过为每个等价类生成一个状态来构造了。若 <math>S</math> 是划分 <math>P</math> 的一个状态集，<math>s</math> 是 <math>S</math> 中的一个状态，<math>c</math> 是一个字符输入；那么最小DFA的状态转移从 <math>S</math> 起始，在 <math>c</math> 下转移到原自动机从状态 <math>s</math> 在输入 <math>c</math> 下转移到的状态集。最小DFA的起始状态是包含有原DFA起始状态的集合，接受状态是其成员为原DFA中接受状态的集合。

=== Moore算法 ===
Moore DFA最小化算法由{{Harvard citations|txt|last=Moore|first=Edward F.|author-link=Edward F. Moore|authorlink=Edward F. Moore|year=1956}} 给出。与 Hopcroft 算法类似地，它维护一个划分，且这个划分的初值为接受和拒绝状态的划分，并同样反复细化直至无法继续细化。在每一步中，它都会用 <span class="texhtml">''s'' + 1</span> 个划分的[[最粗公细化]] (coarsest common refinement) 来替代当前的划分，这 <math>s+1</math> 个划分中的一个是当前划分，其他的 <math>s</math> 个则是当前划分在转移函数和在所有输入符号下的原象。当这一操作无法改善当前划分时，算法即停止。这个算法在最坏情况下的复杂度是 <math>O(n^2s)</math>：算法的每个步骤都需要 <math>O(ns)</math>，这是[[基数排序]]一个变种用以重排状态的复杂度，状态重排使得新划分下同一集合中状态的编号顺序是接连的。又，最多会有 <math>n</math> 轮，因为除最后一轮外，每轮都使得划分中的集合数目增加。在Moore算法下导致最坏情况的DFA最小化问题实例和Hopcroft算法是相同的。算法的轮数会比 <math>n</math> 小得多，所以平均上（<math>s</math> 是常数），其性能可达 <math>O(n\log n)</math> 甚至 <math>O(n\log\log n)</math>，结果取决于建模平均情况行为的自动机随机选取分布方式。{{Sfnp|David|2012}}

=== Brzozowski算法 ===
{{Harvard citation text|Brzozowski|1963}} 注意到，将DFA的边反转将产生一个原语言反序的[[非确定有限状态自动机]] (NFA)。再将这个NFA用标准的[[幂集构造|幂集构造法]]（只构造转换后DFA的可达状态）转换为DFA，就会产生原语言反序的最小DFA。重复反转操作，就可以得到原语言的最小DFA。Brzozowski算法在最坏情况下的复杂度是指数的，因为存在这样的正则语言，其反序的最小DFA的规模是原语言DFA规模的指数大。<ref>For instance, the language of binary strings whose nth symbol is a one requires only <span class="texhtml">''n'' + 1</span> states, but its reversal requires <span class="texhtml">2<sup>''n''</sup></span> states. {{Harvard citation text|Leiss|1981}} provides a ternary n-state DFA whose reversal requires <span class="texhtml">2<sup>''n''</sup></span> 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 {{Harvard citation text|Câmpeanu|Culik|Salomaa|Yu|2001}}.</ref> 但通常来说这个算法比最坏情况表现得要好。

== NFA最小化 ==
以上的步骤都对DFA有效，可是划分的方法并不适用于[[非确定有限状态自动机]] (NFA)。<ref>{{Harvard citation text|Hopcroft|Motwani|Ullman|2001}}, Section 4.4, Figure labeled "Minimizing the States of an NFA", p. 163.</ref>虽然穷举搜索可以最小化NFA，但并没有一个多项式时间的算法可以完成该过程，除非 [[P (複雜度)|P]]=[[PSPACE]]（[[计算复杂性理论]]中的一个未解决问题，一般认为很可能P≠PSPACE）。然而的确存在比暴力搜索可能更加有效的NFA最小化算法。{{Sfnp|Kameda|Weiner|1970}}

== 参见 ==
* [[确定有限状态自动机]]
* [[自动机理论]]

== 注释 ==
{{reflist}}

== 参考文献 ==
*{{citation|pages=157–162|chapter=4.13 Partitioning|title=The Design and Analysis of Computer Algorithms|first1=Alfred V.|last1=Aho|author1-link=Alfred Aho|first2=John E.|last2=Hopcroft|author2-link=John Hopcroft|first3=Jeffrey D.|last3=Ullman|author3-link=Jeffrey D. Ullman|publisher=Addison-Wesley|year=1974}}.
*{{citation | first1=Jean | last1=Berstel | first2=Luc | last2=Boasson | first3=Olivier | last3=Carton | first4=Isabelle | last4=Fagnot | contribution=Minimization of Automata | arxiv=1010.5318 | year=2010 | title=Automata: from Mathematics to Applications|publisher=European Mathematical Society }}
*{{citation
 | last = Brzozowski | first = J. A.
 | authorlink=Janusz Brzozowski (computer scientist)
 | contribution = Canonical regular expressions and minimal state graphs for definite events
 | mr = 0175719
 | pages = 529–561
 | publisher = Polytechnic Press of Polytechnic Inst. of Brooklyn, Brooklyn, N.Y.
 | title = Proc. Sympos. Math. Theory of Automata (New York, 1962)
 | year = 1963}}.
*{{citation
 | last1 = Câmpeanu | first1 = Cezar
 | last2 = Culik | first2 = Karel, II
 | last3 = Salomaa | first3 = Kai
 | last4 = Yu | first4 = Sheng
 | contribution = State Complexity of Basic Operations on Finite Languages
 | doi = 10.1007/3-540-45526-4_6
 | pages = 60–70
 | publisher = Springer-Verlag
 | series = Lecture Notes in Computer Science
 | title = 4th International Workshop on Automata Implementation (WIA '99)
 | volume = 2214
 | year = 2001}}.
*{{citation |title=Average complexity of Moore’s and Hopcroft’s algorithms |first=Julien |last=David |year=2012 |journal=[[Theoretical Computer Science (journal)|Theoretical Computer Science]]|volume=417 |pages=50–65 |doi=10.1016/j.tcs.2011.10.011}}.
*{{citation
 | last = Hopcroft | first = John | authorlink = John Hopcroft
 | contribution = An {{math|''n'' log ''n''}} algorithm for minimizing states in a finite automaton
 | mr = 0403320
 | location = New York
 | pages = 189–196
 | publisher = Academic Press
 | title = Theory of machines and computations (Proc. Internat. Sympos., Technion, Haifa, 1971)
 | year = 1971}}. See also preliminary version, [http://i.stanford.edu/pub/cstr/reports/cs/tr/71/190/CS-TR-71-190.pdf Technical Report STAN-CS-71-190] {{Wayback|url=http://i.stanford.edu/pub/cstr/reports/cs/tr/71/190/CS-TR-71-190.pdf |date=20170118225743 }}, Stanford University, Computer Science Department, January 1971.
*{{citation | isbn=0-201-02988-X | first1=John E. |last1=Hopcroft |first2= Jeffrey D. |last2=Ullman | title=Introduction to Automata Theory, Languages, and Computation | location=Reading/MA | publisher=Addison-Wesley | year=1979 }} 
*{{citation|title=[[Introduction to Automata Theory, Languages, and Computation]] | last1 = Hopcroft | first1 = John E. | author1-link = John Hopcroft | last2 = Motwani | first2 = Rajeev | author2-link = Rajeev Motwani | last3 = Ullman | first3 = Jeffrey D. | author3-link = Jeffrey D. Ullman | publisher = Addison-Wesley | edition = 2nd | year = 2001}}.
*{{citation
 | last1 = Kameda | first1 = Tsunehiko
 | last2 = Weiner | first2 = Peter
 | doi = 10.1109/T-C.1970.222994
 | issue = 7
 | journal = IEEE Transactions on Computers
 | title = On the state minimization of nondeterministic finite automata
 | volume = 100
 | year = 1970}}.
*{{citation
 | last = Knuutila | first = Timo
 | doi = 10.1016/S0304-3975(99)00150-4
 | issue = 1-2
 | journal = Theoretical Computer Science
 | mr = 1795249
 | pages = 333–363
 | title = Re-describing an algorithm by Hopcroft
 | volume = 250
 | year = 2001}}.
*{{citation
 | last = Leiss | first = Ernst
 | doi = 10.1016/S0304-3975(81)80005-9
 | mr = 603263
 | issue = 3
 | journal = Theoretical Computer Science
 | pages = 323–330
 | title = Succinct representation of regular languages by Boolean automata
 | volume = 13
 | url = http://www.sciencedirect.com/science/article/pii/S0304397581800059/pdf?md5=ae550d58084acf5f9af3fac6b8b20106&pid=1-s2.0-S0304397581800059-main.pdf
 | year = 1981}}.
*{{citation | last = Leiss | first = Ernst | title=Succinct representation of regular languages by Boolean automata II | journal=Theoretical Computer Science | volume=38 | number= | pages=133–136 | url=http://www.sciencedirect.com/science/article/pii/0304397585902154/pdf?md5=00582bb1bdc5f7a3af33b8c19479d3d3&pid=1-s2.0-0304397585902154-main.pdf | year=1985 | doi=10.1016/0304-3975(85)90215-4}} 
*{{citation
 | last = Moore | first = Edward F. | authorlink = Edward F. Moore
 | contribution = Gedanken-experiments on sequential machines
 | mr = 0078059
 | location = Princeton, N. J.
 | pages = 129–153
 | publisher = Princeton University Press
 | series = Annals of mathematics studies, no. 34
 | title = Automata studies
 | year = 1956}}.
* {{citation | last=Sakarovitch | first=Jacques | title=Elements of automata theory | others=Translated from French by Reuben Thomas | publisher=[[Cambridge University Press]] | year=2009 | isbn=978-0-521-84425-3 | zbl=1188.68177 }}

== 外部链接 ==
* [https://web.archive.org/web/20150621004621/http://www8.cs.umu.se/kurser/TDBC92/VT06/final/1.pdf 使用Myhill-Nerode定理做DFA最小化]

[[Category:自动机]]
[[Category:带有伪代码示例的条目]]