Kleene's algorithm: Difference between revisions

Revision as of 18:10, 31 May 2014

Revision as of 18:21, 31 May 2014

Line 6:

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''₀, ''F''), with ''Q'' = { ''q''₀,...,''q''_''n'' } its set of [[deterministic 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 though any state numbered higher than ''k''.

Given a [[deterministic finite automaton#Formal definition|deterministic finite automaton]] ''M'' = (''Q'', Σ, δ, ''q''₀, ''F''), with ''Q'' = { ''q''₀,...,''q''_''n'' } its set of 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 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''₀ to the final state ''q''_''j''. If ''F'' = { ''q''₁,...,''q''_''f'' } 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''.

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.

Given a [[deterministic finite automaton#Formal definition|deterministic finite automaton]] ''M'' = (''Q'', Σ, δ, ''q''₀, ''F''), with ''Q'' = { ''q''₀,...,''q''_''n'' } its set of 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 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 [[deterministic finite automaton#Formal definition|start state]] ''q''₀ to the final state ''q''_''j''. If ''F'' = { ''q''₁,...,''q''_''f'' } 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''.

==References==