Content deleted Content added
Line 3:
==Algorithm description==
According to Gross and Yellen (2004),<ref>{{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}}</ref>
This description follows 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}} Here: Theorem 2.4, p.33-34</ref>
Line 10:
Here, "going through a state" means entering ''and'' leaving it, so both ''i'' and ''j'' may be higher than ''k'', but no intermediate state may.
Each set ''R''{{su|p=''k''|b=''ij''}} is represented by a regular expression; the algorithm computes them step by step for ''k'' = -1, 0, ..., ''n''. Since there is no state numbered higher than ''n'', the regular expression ''R''{{su|p=''n''|b=''0j''}} represents the set of all strings that take ''M'' from its [[deterministic finite automaton#Formal definition|start state]] ''q''<sub>0</sub> to ''q''<sub>''j''</sub>. If ''F'' = { ''q''<sub>1</sub>,...,''q''<sub>''f''</sub> } is the set of [[deterministic finite automaton#Formal definition|accept states]], the [[regular expression#Formal definition|regular expression]] ''R''{{su|p=''n''|b=''01''}} | ... | ''R''{{su|p=''n''|b=''0f''}} represents the language [[deterministic finite automaton#Formal definition|accepted]] by ''M''.
The initial regular expressions, for ''k'' = -1, are computed as
:''R''{{su|p=-1|b=''ij''}} = ''a''<sub>1</sub> | ... | ''a''<sub>''m''</sub> if ''i''≠''j'', where δ(''q''<sub>''i''</sub>,''a''<sub>1</sub>) = ... = δ(''q''<sub>''i''</sub>,''a''<sub>''m''</sub>) = ''q''<sub>''j''</sub>
:''R''{{su|p=-1|b=''ij''}} = ''a''<sub>1</sub> | ... | ''a''<sub>''m''</sub> | ε, if ''i''=''j'', where δ(''q''<sub>''i''</sub>,''a''<sub>1</sub>) = ... = δ(''q''<sub>''i''</sub>,''a''<sub>''m''</sub>) = ''q''<sub>''j''</sub>
After that, in each step the expressions ''R''{{su|p=''k''|b=''ij''}} are computed from the previous ones by
:''R''{{su|p=''k''|b=''ij''}} = ''R''{{su|p=''k''-1|b=''ik''}} (''R''{{su|p=''k''-1|b=''kk''}})<sup>*</sup> ''R''{{su|p=''k''-1|b=''kj''}} | ''R''{{su|p=''k''-1|b=''ij''}}
==References==
| |||