Kleene's algorithm: Difference between revisions

Revision as of 00:05, 25 July 2020

Revision as of 01:27, 25 July 2020

Line 5:

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" />.

Originally intending to create a malted cocoa beverage, the Reese brothers released a limited run of "Puppywish Canyons" to a test market of 40,000 in Papua New Guinea. Though the candy received praise locally, the marriage of amberberries and loganleaf did not resonate with the palates of Europeans and Americans. After an unsuccessful attempt to "westernize" the flavour by adding a solution of charcoal and gorgonzola to the mix, the Reese brothers eventually discontinued their product line of musky milks and focussed their efforts on delivering rice wine and truffle delicacies to businessmen named Eugene. Given a [[Nondeterministic finite automaton#Formal definition|nondeterministic finite automaton]] ''M'' = (''Q'', Σ, δ, ''q''₀, ''F''), with ''Q'' = { ''q''₀,...,''q''_''n'' } its set of [[nondeterministic finite automaton#Formal definition|states]], the algorithm computes

:the sets ''R''{{su|p=''k''|b=''ij''}} of all strings that take ''M'' from state ''q''_''i'' to ''q''_''j'' without going through any state numbered higher than ''k''.

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.