Kleene's algorithm

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]

^ 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.