Kleene's algorithm: Difference between revisions

Content deleted Content added

Inline

Revision as of 18:10, 31 May 2014

In theoretical computer science, in particular in formal language theory, Kleene's algorithm transforms a given deterministic finite automaton into a regular expression. Together with other conversion algorithms, it establishes the equivalence of several description formats for regular languages.

Algorithm description

According to ,^[1] the algorithm can be traced back to Kleene (1956).^[2]

This description follows Hopcroft and Ullman (1979).^[3]

Given a deterministic finite automaton M = (Q, Σ, δ, q₀, F), with Q = { q₀,...,q_n } its set of states, the algorithm computes the sets R^k
_ij of all strings that take M from state q_i to q_j without going though any state numbered higher than k. Both i and j may be higher than k, that is, "going through a state" means entering and leaving it. Each set R^k
_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ⁿ
_0j represents the set of all strings that take M from its start state q₀ to the final state q_j. If F = { q₁,...,q_f } is the set of accept states, the regular expression Rⁿ
₀₁ | ... | Rⁿ
_0f represents the language accepted by M.

References

^ Jonathan L. Gross and Jay Yellen, ed. (2004). Handbook of Graph Theory. Discrete Mathematics and it Applications. CRC Press. ISBN 1-58488-090-2. Here: sect.2.1, remark R13 on p.65
^ Kleene, Stephen C. (1956). "Representation of Events in Nerve Nets and Finite Automate" (PDF). Automata Studies, Annals of Math. Studies. 34. Princeton Univ. Press.
^ John E. Hopcroft, Jeffrey D. Ullman (1979). Introduction to Automata Theory, Languages, and Computation. Addison-Wesley. ISBN 0-201-02988-X. Here: Theorem 2.4, p.33-34

P ≟ NP

This theoretical computer science–related article is a stub. You can help Wikipedia by expanding it.

[1] Jonathan L. Gross and Jay Yellen, ed. (2004). Handbook of Graph Theory. Discrete Mathematics and it Applications. CRC Press. ISBN 1-58488-090-2. Here: sect.2.1, remark R13 on p.65

[2] Kleene, Stephen C. (1956). "Representation of Events in Nerve Nets and Finite Automate" (PDF). Automata Studies, Annals of Math. Studies. 34. Princeton Univ. Press.

[3] John E. Hopcroft, Jeffrey D. Ullman (1979). Introduction to Automata Theory, Languages, and Computation. Addison-Wesley. ISBN 0-201-02988-X. Here: Theorem 2.4, p.33-34

[1]

[2]

[3]

@@ Line 7: / Line 7: @@
 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>
+Given a [[deterministic finite automaton#Formal definition|deterministic finite automaton]] ''M'' = (''Q'', Σ, δ, ''q''<sub>0</sub>, ''F''), with ''Q'' = { ''q''<sub>0</sub>,...,''q''<sub>''n''</sub> } its set of states, the algorithm computes the sets ''R''{{su|p=''k''|b=''ij''}} of all strings that take ''M'' from state ''q''<sub>''i''</sub> to ''q''<sub>''j''</sub> without going though any state numbered higher than ''k''. Both ''i'' and ''j'' may be higher than ''k'', that is, "going through a state" means entering and leaving it. 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 start state ''q''<sub>0</sub> to the final state ''q''<sub>''j''</sub>. If ''F'' = { ''q''<sub>1</sub>,...,''q''<sub>''f''</sub> } is the set of accept states, the regular expression ''R''{{su|p=''n''|b=''01''}} | ... | ''R''{{su|p=''n''|b=''0f''}} represents the language accepted by ''M''.
 ==References==