Content deleted Content added
m Reverted edits by 38.18.114.116 (talk) to last version by Citation bot |
m v2.04b - Bot T20 CW#61 - Fix errors for CW project (Reference before punctuation) |
||
Line 3:
==Algorithm description==
According to Gross and Yellen (2004),<ref name="gross2004handbook">{{cite book| title=Handbook of Graph Theory| year=2004| volume=| publisher=CRC Press| editor=Jonathan L. Gross and Jay Yellen| series=Discrete Mathematics and it Applications| isbn=1-58488-090-2}} Here: sect.2.1, remark R13 on p.65</ref> the algorithm can be traced back to [[Kleene]] (1956).<ref>{{cite journal| author=Kleene, Stephen C.| title=Representation of Events in Nerve Nets and Finite Automate| journal=Automata Studies, Annals of Math. Studies| year=1956| volume=34| publisher=Princeton Univ. Press| url=http://www.dlsi.ua.es/~mlf/nnafmc/papers/kleene56representation.pdf}} Here: sect.9, p.37-40</ref> A presentation of the algorithm in the case of [[deterministic finite automata]] (DFAs) is given in Hopcroft and Ullman (1979).<ref>{{cite book| author=John E. Hopcroft, Jeffrey D. Ullman| title=Introduction to Automata Theory, Languages, and Computation| year=1979| publisher=Addison-Wesley| isbn=0-201-02988-X| url-access=registration| url=https://archive.org/details/introductiontoau00hopc}} Here: Section 3.2.1 pages 91-96</ref> The presentation of the algorithm for NFAs below follows Gross and Yellen (2004).<ref name="gross2004handbook" />
Given a [[Nondeterministic finite automaton#Formal definition|nondeterministic finite automaton]] ''M'' = (''Q'', Σ, δ, ''q''<sub>0</sub>, ''F''), with ''Q'' = { ''q''<sub>0</sub>,...,''q''<sub>''n''</sub> } its set of [[nondeterministic finite automaton#Formal definition|states]], the algorithm computes
| |||