Kleene's algorithm: Difference between revisions

Revision as of 19:45, 31 May 2014

Latest revision as of 06:30, 14 April 2025

(67 intermediate revisions by 23 users not shown)

Line 1:

In [[theoretical computer science]], in particular in [[formal language theory]], '''Kleene's algorithm''' transforms a given [[deterministicnondeterministic finite automaton]] (NFA) into a [[regular expression]].

Together with other conversion algorithms, it establishes the equivalence of several description formats for [[regular language]]s. Alternative presentations of the same method include the "elimination method" attributed to [[Janusz Brzozowski (computer scientist)|Brzozowski]] and [[Edward J. McCluskey|McCluskey]], the algorithm of [[Robert McNaughton|McNaughton]] and [[Hisao Yamada|Yamada]],<ref>{{Cite journal|last1=McNaughton|first1=R.|last2=Yamada|first2=H.|date=March 1960|title=Regular Expressions and State Graphs for Automata|journal=IRE Transactions on Electronic Computers|volume=EC-9|issue=1|pages=39–47|doi=10.1109/TEC.1960.5221603|issn=0367-9950}}</ref> and the use of [[Arden's lemma]].

Together with other conversion algorithms, it establishes the equivalence of several description formats for [[regular language]]s.

==Algorithm description==

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

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

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:the a [[deterministic finite automaton#Formal definition|deterministic finite automaton]]sets ''MR'' {{su|p= (''Qk'', Σ, δ, |b=''qij''₀,}} ''F''),of withall strings that take ''QM'' =from {state ''q''_0''i'',..., to ''q''_''nj'' }without itsgoing setthrough ofany [[deterministicstate finitenumbered automaton#Formalhigher definition|states]],than the algorithm computes''k''.

: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''.

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 [[deterministicnondeterministic finite automaton#Formal definition|start state]] ''q''₀ to ''q''_''j''. If ''F'' = { ''q''₁,...,''q''_''f'' } is the set of [[deterministicnondeterministic 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 [[deterministicnondeterministic finite automaton#Formal definition|accepted]] by ''M''.

The initial regular expressions, for ''k'' = -1, are computed as follows for ''i''≠''j'':

:''R''{{su|p=-1−1|b=''ij''}} = ''a''₁ | ... | ''a''_''m'' &nbsp; &nbsp; &nbsp; ifwhere ''iq''≠_''j'', where∈ δ(''q''_''i'',''a''₁) =, ..., = δ(''q''_''ij'', ∈ δ(''aq''_''mi'') = ,''qa''_''jm'')

and as follows for ''i''=''j'':

:''R''{{su|p=-1|b=''ij''}} = ''a''₁ | ... | ''a''_''m'' | ε, if ''i''=''j'', where δ(''q''_''i'',''a''₁) = ... = δ(''q''_''i'',''a''_''m'') = ''q''_''j''

:''R''{{su|p=−1|b=''ii''}} = ''a''₁ | ... | ''a''_''m'' | ε &nbsp; &nbsp; &nbsp; where ''q''_''i'' ∈ δ(''q''_''i'',''a''₁), ..., ''q''_''i'' ∈ δ(''q''_''i'',''a''_''m'')

In other words, ''R''{{su|p=−1|b=''ij''}} mentions all letters that label a transition from ''i'' to ''j'', and we also include ε in the case where ''i''=''j''.

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''}})^* ''R''{{su|p=''k''-1|b=''kj''}} | ''R''{{su|p=''k''-1|b=''ij''}}

Another way to understand the operation of the algorithm is as an "elimination method", where the states from 0 to ''n'' are successively removed: when state ''k'' is removed, the regular expression ''R''{{su|p=''k''-1|b=''ij''}}, which describes the words that label a path from state ''i''>''k'' to state ''j''>''k'', is rewritten into ''R''{{su|p=''k''|b=''ij''}} so as to take into account the possibility of going via the "eliminated" state ''k''.

By induction on ''k'', it can be shown that the length<ref>More precisely, the number of regular-expression symbols, "''a''_''i''", "ε", "|", "^*", "·"; not counting parentheses.</ref> of each expression ''R''{{su|p=''k''|b=''ij''}} is at most {{sfrac|1|3}}(4^''k''+1(6''s''+7) - 4) symbols, where ''s'' denotes the number of characters in Σ.

Therefore, the length of the regular expression representing the language accepted by ''M'' is at most {{sfrac|1|3}}(4^''n''+1(6''s''+7)''f'' - ''f'' - 3) symbols, where ''f'' denotes the number of final states.

This exponential blowup is inevitable, because there exist families of DFAs for which any equivalent regular expression must be of exponential size.<ref>{{Cite book|last1=Gruber|first1=Hermann|last2=Holzer|first2=Markus|title=Automata, Languages and Programming |chapter=Finite Automata, Digraph Connectivity, and Regular Expression Size |date=2008|editor-last=Aceto|editor-first=Luca|editor2-last=Damgård|editor2-first=Ivan|editor3-last=Goldberg|editor3-first=Leslie Ann|editor4-last=Halldórsson|editor4-first=Magnús M.|editor5-last=Ingólfsdóttir|editor5-first=Anna|editor6-last=Walukiewicz|editor6-first=Igor|volume=5126|series=Lecture Notes in Computer Science|publisher=Springer Berlin Heidelberg|pages=39–50|doi=10.1007/978-3-540-70583-3_4|isbn=9783540705833|s2cid=10975422}}. Theorem 16.</ref>

In practice, the size of the regular expression obtained by running the algorithm can be very different depending on the order in which the states are considered by the procedure, i.e., the order in which they are numbered from 0 to ''n''.

==Example==

[[File:Deterministicfiniteautomaton.svg|thumb|150px|Example DFA given to Kleene's algorithm]]

The automaton shown in the picture can be described as ''M'' = (''Q'', Σ, δ, ''q''₀, ''F'') with

* the set of states ''Q'' = { ''q''₀, ''q''₁, ''q''₂ },

* the input alphabet Σ = { ''a'', ''b'' },

* the transition function δ with δ(''q''₀,''a'')=''q''₀, &nbsp; δ(''q''₀,''b'')=''q''₁, &nbsp; δ(''q''₁,''a'')=''q''₂, &nbsp; δ(''q''₁,''b'')=''q''₁, &nbsp; δ(''q''₂,''a'')=''q''₁, and δ(''q''₂,''ab'')=''q''₁,

* the start state ''q''₀, and

* set of accept states ''F'' = { ''q''₁ }.

Kleene's algorithm computes the initial regular expressions as

:{|

|-

| ''R''{{su|p=-1−1|b=''00''}} &nbsp; &nbsp;

| | = ''a'' | ε

|-

| ''R''{{su|p=-1−1|b=''01''}}

| | = ''b''

|-

| ''R''{{su|p=-1−1|b=''02''}}

| | = ∅

|-

| ''R''{{su|p=-1−1|b=''10''}}

| | = ∅

|-

| ''R''{{su|p=-1−1|b=''11''}}

| | = ''b'' | ε

|-

| ''R''{{su|p=-1−1|b=''12''}}

| | = ''a''

|-

| ''R''{{su|p=-1−1|b=''20''}}

| | = ∅

|-

| ''R''{{su|p=-1−1|b=''21''}}

| | = ''a'' | ''b''

|-

| ''R''{{su|p=-1−1|b=''22''}}

| | = ε

|}

After that, the ''R''{{su|p=''k''|b=''ij''}} are computed from the ''R''{{su|p=''k''-1|b=''ij''}} step by step for ''k'' = 0, 1, 2.

Step 0:

[[Kleene algebra]] equalities are used to simplify the regular expressions as much as possible.

; Step 0

{|

: {|

|-

| ''R''{{su|p=0|b=''00''}} &nbsp; &nbsp;

| | = ''R''{{su|p=-1−1|b=''00''}} (''R''{{su|p=-1−1|b=''00''}})^* ''R''{{su|p=-1−1|b=''00''}} | ''R''{{su|p=-1−1|b=''00''}} &nbsp; &nbsp;

| | = (''a'' | ε)

| | (''a'' | ε)^*

Line 71 ⟶ 83:

| | = ''a''^*

|-

| ''R''{{su|p=0|b=''01''}}

| | = ''R''{{su|p=-1−1|b=''00''}} (''R''{{su|p=-1−1|b=''00''}})^* ''R''{{su|p=-1−1|b=''01''}} | ''R''{{su|p=-1−1|b=''01''}}

| | = (''a'' | ε)

| | (''a'' | ε)^*

Line 79 ⟶ 91:

| | = ''a''^* ''b''

|-

| ''R''{{su|p=0|b=''02''}}

| | = ''R''{{su|p=-1−1|b=''00''}} (''R''{{su|p=-1−1|b=''00''}})^* ''R''{{su|p=-1−1|b=''02''}} | ''R''{{su|p=-1−1|b=''02''}}

| | = (''a'' | ε)

| | (''a'' | ε)^*

Line 87 ⟶ 99:

| | = ∅

|-

| ''R''{{su|p=0|b=''10''}}

| | = ''R''{{su|p=-1−1|b=''10''}} (''R''{{su|p=-1−1|b=''00''}})^* ''R''{{su|p=-1−1|b=''00''}} | ''R''{{su|p=-1−1|b=''10''}}

| | = ∅

| | (''a'' | ε)^*

Line 95 ⟶ 107:

| | = ∅

|-

| ''R''{{su|p=0|b=''11''}}

| | = ''R''{{su|p=-1−1|b=''10''}} (''R''{{su|p=-1−1|b=''00''}})^* ''R''{{su|p=-1−1|b=''01''}} | ''R''{{su|p=-1−1|b=''11''}}

| | = ∅

| | (''a'' | ε)^*

Line 103 ⟶ 115:

| | = ''b'' | ε

|-

| ''R''{{su|p=0|b=''12''}}

| | = ''R''{{su|p=-1−1|b=''10''}} (''R''{{su|p=-1−1|b=''00''}})^* ''R''{{su|p=-1−1|b=''02''}} | ''R''{{su|p=-1−1|b=''12''}}

| | = ∅

| | (''a'' | ε)^*

Line 111 ⟶ 123:

| | = ''a''

|-

| ''R''{{su|p=0|b=''20''}}

| | = ''R''{{su|p=-1−1|b=''20''}} (''R''{{su|p=-1−1|b=''00''}})^* ''R''{{su|p=-1−1|b=''00''}} | ''R''{{su|p=-1−1|b=''20''}}

| | = ∅

| | (''a'' | ε)^*

Line 119 ⟶ 131:

| | = ∅

|-

| ''R''{{su|p=0|b=''21''}}

| | = ''R''{{su|p=-1−1|b=''20''}} (''R''{{su|p=-1−1|b=''00''}})^* ''R''{{su|p=-1−1|b=''01''}} | ''R''{{su|p=-1−1|b=''21''}}

| | = ∅

| | (''a'' | ε)^*

Line 127 ⟶ 139:

| | = ''a'' | ''b''

|-

| ''R''{{su|p=0|b=''22''}}

| | = ''R''{{su|p=-1−1|b=''20''}} (''R''{{su|p=-1−1|b=''00''}})^* ''R''{{su|p=-1−1|b=''02''}} | ''R''{{su|p=-1−1|b=''22''}}

| | = ∅

| | (''a'' | ε)^*

Line 136 ⟶ 148:

|}

; Step 1:

: {|

{|

|-

| ''R''{{su|p=1|b=''00''}} &nbsp; &nbsp;

| | = ''R''{{su|p=0|b=''01''}} (''R''{{su|p=0|b=''11''}})^* ''R''{{su|p=0|b=''10''}} | ''R''{{su|p=0|b=''00''}} &nbsp; &nbsp;

| | = ''a''^*''b''

| | (''b'' | ε)^*

| | ∅

| | | ''a''^* &nbsp; &nbsp; &nbsp; &nbsp;

| | = ''a''^*

|-

| ''R''{{su|p=1|b=''01''}}

| | = ''R''{{su|p=0|b=''01''}} (''R''{{su|p=0|b=''11''}})^* ''R''{{su|p=0|b=''11''}} | ''R''{{su|p=0|b=''01''}}

| | = ''a''^*''b''

| | (''b'' | ε)^*

| | (''b'' | ε)

| | | ''a''^* ''b''

| | = ''a''^* ''b''^* ''b''

| | =

|-

| ''R''{{su|p=1|b=''02''}}

| | = ''R''{{su|p=0|b=''01''}} (''R''{{su|p=0|b=''11''}})^* ''R''{{su|p=0|b=''12''}} | ''R''{{su|p=0|b=''02''}}

| | = ''a''^*''b''

| | (''b'' | ε)^*

| | ''a''

| | | ∅

| | = ''a''^* ''b''^* ''ba''

| | =

|-

| ''R''{{su|p=1|b=''10''}}

| | = ''R''{{su|p=0|b=''11''}} (''R''{{su|p=0|b=''11''}})^* ''R''{{su|p=0|b=''10''}} | ''R''{{su|p=0|b=''10''}}

| | = (''b'' | ε)

| | (''b'' | ε)^*

| | ∅

| | | ∅

| | = ∅

|-

| ''R''{{su|p=1|b=''11''}}

| | = ''R''{{su|p=0|b=''11''}} (''R''{{su|p=0|b=''11''}})^* ''R''{{su|p=0|b=''11''}} | ''R''{{su|p=0|b=''11''}}

| | = (''b'' | ε)

| | (''b'' | ε)^*

| | (''b'' | ε)

| | | ''b'' | ε

| | = ''b''^*

|-

| ''R''{{su|p=1|b=''12''}}

| | = ''R''{{su|p=0|b=''11''}} (''R''{{su|p=0|b=''11''}})^* ''R''{{su|p=0|b=''12''}} | ''R''{{su|p=0|b=''12''}}

| | = (''b'' | ε)

| | (''b'' | ε)^*

| | ''a''

| | | ''a''

| | = ''b''^* ''a''

| | =

|-

| ''R''{{su|p=1|b=''20''}}

| | = ''R''{{su|p=0|b=''21''}} (''R''{{su|p=0|b=''11''}})^* ''R''{{su|p=0|b=''10''}} | ''R''{{su|p=0|b=''20''}}

| | = (''a'' | ''b'')

| | (''b'' | ε)^*

| | ∅

| | | ∅

| | = ∅

|-

| ''R''{{su|p=1|b=''21''}}

| | = ''R''{{su|p=0|b=''21''}} (''R''{{su|p=0|b=''11''}})^* ''R''{{su|p=0|b=''11''}} | ''R''{{su|p=0|b=''21''}}

| | = (''a'' | ''b'')

| | (''b'' | ε)^*

| | (''b'' | ε)

| | | ''a'' | ''b''

| | = (''a'' | ''b'') ''b''^*

| | =

|-

| ''R''{{su|p=1|b=''22''}}

| | = ''R''{{su|p=0|b=''21''}} (''R''{{su|p=0|b=''11''}})^* ''R''{{su|p=0|b=''12''}} | ''R''{{su|p=0|b=''22''}}

| | = (''a'' | ''b'')

| | (''b'' | ε)^*

| | ''a''

| | | ε

| | = (''a'' | ''b'') ''b''^* ''a'' | ε

| | =

|}

; Step 2:

: {|

|-

| ''R''{{su|p=2|b=00}} &nbsp; &nbsp;

| | = ''R''{{su|p=1|b=02}} (''R''{{su|p=1|b=22}})^* ''R''{{su|p=1|b=20}} | ''R''{{su|p=1|b=00}} &nbsp; &nbsp;

| | = ''a''^*''b''^*''ba''

| | ((''a''|''b'')''b''^*''a'' | ε)^*

| | ∅

| | | ''a''^*

| | = ''a''^*

|-

| ''R''{{su|p=2|b=01}}

| | = ''R''{{su|p=1|b=02}} (''R''{{su|p=1|b=22}})^* ''R''{{su|p=1|b=21}} | ''R''{{su|p=1|b=01}}

| | = ''a''^*''b''^*''ba''

| | ((''a''|''b'')''b''^*''a'' | ε)^*

| | (''a''|''b'')''b''^*

| | | ''a''^* ''b''^* ''b''

| | = ''a''^* ''b'' (''a'' (''a'' | ''b'') | ''b'')^*

|-

| ''R''{{su|p=2|b=02}}

| | = ''R''{{su|p=1|b=02}} (''R''{{su|p=1|b=22}})^* ''R''{{su|p=1|b=22}} | ''R''{{su|p=1|b=02}}

| | = ''a''^*''b''^*''ba''

| | ((''a''|''b'')''b''^*''a'' | ε)^*

| | ((''a''|''b'')''b''^*''a'' | ε)

| | | ''a''^* ''b''^* ''ba''

| | = ''a''^* ''b''^* ''b'' (''a'' (''a'' | ''b'') ''b''^*)^* ''a''

|-

| ''R''{{su|p=2|b=10}}

| | = ''R''{{su|p=1|b=12}} (''R''{{su|p=1|b=22}})^* ''R''{{su|p=1|b=20}} | ''R''{{su|p=1|b=10}}

| | = ''b''^* ''a''

| | ((''a''|''b'')''b''^*''a'' | ε)^*

| | ∅

| | | ∅

| | = ∅

|-

| ''R''{{su|p=2|b=11}}

| | = ''R''{{su|p=1|b=12}} (''R''{{su|p=1|b=22}})^* ''R''{{su|p=1|b=21}} | ''R''{{su|p=1|b=11}}

| | = ''b''^* ''a''

| | ((''a''|''b'')''b''^*''a'' | ε)^*

| | (''a''|''b'')''b''^*

| | | ''b''^*

| | = (''a'' (''a'' | ''b'') | ''b'')^*

|-

| ''R''{{su|p=2|b=12}}

| | = ''R''{{su|p=1|b=12}} (''R''{{su|p=1|b=22}})^* ''R''{{su|p=1|b=22}} | ''R''{{su|p=1|b=12}}

| | = ''b''^* ''a''

| | ((''a''|''b'')''b''^*''a'' | ε)^*

| | ((''a''|''b'')''b''^*''a'' | ε)

| | | ''b''^* ''a''

| | = (''a'' (''a'' | ''b'') | ''b'')^* ''a''

|-

| ''R''{{su|p=2|b=20}}

| | = ''R''{{su|p=1|b=22}} (''R''{{su|p=1|b=22}})^* ''R''{{su|p=1|b=20}} | ''R''{{su|p=1|b=20}}

| | = ((''a''|''b'')''b''^*''a'' | ε)

| | ((''a''|''b'')''b''^*''a'' | ε)^*

| | ∅

| | | ∅

| | = ∅

|-

| ''R''{{su|p=2|b=21}}

| | = ''R''{{su|p=1|b=22}} (''R''{{su|p=1|b=22}})^* ''R''{{su|p=1|b=21}} | ''R''{{su|p=1|b=21}}

| | = ((''a''|''b'')''b''^*''a'' | ε)

| | ((''a''|''b'')''b''^*''a'' | ε)^*

| | (''a''|''b'')''b''^*

| | | (''a'' | ''b'') ''b''^*

| | = (''a'' | ''b'') (''a'' (''a'' | ''b'') | ''b'')^*

|-

| ''R''{{su|p=2|b=22}}

| | = ''R''{{su|p=1|b=22}} (''R''{{su|p=1|b=22}})^* ''R''{{su|p=1|b=22}} | ''R''{{su|p=1|b=22}}

| | = ((''a''|''b'')''b''^*''a'' | ε)

| | ((''a''|''b'')''b''^*''a'' | ε)^*

| | ((''a''|''b'')''b''^*''a'' | ε)

| | | (''a'' | ''b'') ''b''^* ''a'' | ε &nbsp; &nbsp;

| | = ((''a'' | ''b'') ''b''^* ''a'')^*

|}

Since ''q''₀ is the start state and ''q''₁ is the only accept state, the regular expression ''R''{{su|p=2|b=01}} denotes the set of all strings accepted by the automaton.

==See also==

* [[Floyd–Warshall algorithm#Applications and generalizations|Floyd–Warshall algorithm]] &mdash; an algorithm on weighted graphs that can be implemented by Kleene's algorithm using a particular [[Kleene algebra#Examples|Kleene algebra]]

* [[Star height problem]] &mdash; what is the minimum stars' nesting depth of all regular expressions corresponding to a given DFA?

* [[Generalized star height problem]] &mdash; if a complement operator is allowed additionally in regular expressions, can the [[star height#Generalized star height|stars' nesting depth]] of Kleene's algorithm's output be limited to a fixed bound?

* [[Thompson's construction algorithm]] &mdash; transforms a regular expression to a finite automaton

==References==

{{reflist}}

[[Category:Algorithms]]

{{comp-sci-theory-stub}}

[[Category:Finite-state machines]]

[[Category:Regular expressions]]