En informàtica teòrica , en particular en teoria de llenguatges formals , l'algorisme de Kleene transforma un autòmat finit no determinista (AFND) en una expressió regular . Juntament amb altres algorismes de conversió, estableix l'equivalència de diversos formats de descripció per llenguatges regulars . Presentacions alternatives del mateix mètode inclouen el "mètode d'eliminació" atribuït a Brzozowski i McCluskey , l'algorisme de McNaughton i Yamada , i l'ús del lema d'Arden .[ 1]
Segons Brut i Yellen (2004),[ 2] l'algoritme pot ser remuntat a Kleene (1956).[ 3] Una presentació de l'algorisme en el cas de l'autòmat determinista finit (ADF) és donat a Hopcroft i Ullman (1979).[ 4] La presentació de l'algorisme per AFNDs a sota segueix Brut i Yellen (2004).
Donat un autòmat finit no determinista
M
=
(
Q
,
Σ
,
δ
,
q
0
,
F
)
{\displaystyle M=(Q,\Sigma ,\delta ,q_{0},F)}
, amb
Q
=
{
q
0
,
…
,
q
n
}
{\displaystyle Q=\{q_{0},\dots ,q_{n}\}}
el seu conjunt d'estats, l'algorisme computa els conjunts
R
i
j
k
{\displaystyle R_{ij}^{k}}
de totes les entrades que porten
M
{\displaystyle M}
de l'estat
q
i
{\displaystyle q_{i}}
a
q
j
{\displaystyle q_{j}}
sense passar per cap estat superior a
k
{\displaystyle k}
. Aquí, "passar per un estat" vol dir entrar-hi i sortir-ne, així que ambdós
i
{\textstyle i}
i
j
{\textstyle j}
poden ser superiors a
k
{\displaystyle k}
, però no cap estat intermedi. Cada conjunt
R
i
j
k
{\textstyle R_{ij}^{k}}
és representat per una expressió regular; l'algorisme els computa pas a pas per
k
=
−
1
,
0
,
…
,
n
{\textstyle k=-1,0,\dots ,n}
. Com no hi ha cap estat superior a
n
{\textstyle n}
, l'expressió regular
R
0
j
n
{\textstyle R_{0j}^{n}}
representa el conjunt de totes les entrades que porten
M
{\displaystyle M}
del seu estat inicial
q
0
{\textstyle q_{0}}
a
q
j
{\textstyle q_{j}}
. Si
F
=
{
q
1
,
…
,
q
f
}
{\textstyle F=\{q_{1},\dots ,q_{f}\}}
és el conjunt d'estats finals, l'expressió regular
R
01
n
∣
⋯
∣
R
0
f
n
{\textstyle R_{01}^{n}\mid \dots \mid R_{0f}^{n}}
representa el llenguatge acceptat per
M
{\textstyle M}
.
Les expressions regulars inicials, per a
k
=
−
1
{\textstyle k=-1}
, es computen de la següent manera per a
i
≠
j
{\textstyle i\neq j}
:
R
i
j
−
1
=
a
1
∣
⋯
∣
a
m
{\displaystyle R_{ij}^{-1}=a_{1}\mid \dots \mid a_{m}}
on
q
j
∈
δ
(
q
i
,
a
1
)
,
…
,
q
j
∈
δ
(
q
i
,
a
m
)
{\displaystyle q_{j}\in \delta (q_{i},a_{1}),\dots ,q_{j}\in \delta (q_{i},a_{m})}
i com segueix per a
i
=
j
{\textstyle i=j}
:
R
i
i
−
1
=
a
1
∣
⋯
∣
a
m
∣
ϵ
{\displaystyle R_{ii}^{-1}=a_{1}\mid \dots \mid a_{m}\mid \epsilon }
on
q
i
∈
δ
(
q
i
,
a
1
)
,
…
,
q
i
∈
δ
(
q
i
,
a
m
)
{\displaystyle q_{i}\in \delta (q_{i},a_{1}),\dots ,q_{i}\in \delta (q_{i},a_{m})}
És a dir,
R
i
j
−
1
{\textstyle R_{ij}^{-1}}
representa tots els símbols d'entrada que causen una transició d'
q
i
{\textstyle q_{i}}
a
q
j
{\textstyle q_{j}}
, i també incloem
ϵ
{\textstyle \epsilon }
quan
i
=
j
{\textstyle i=j}
.
Seguidament, en cada pas les expressions
R
i
j
k
{\textstyle R_{ij}^{k}}
es calculen a partir de les anteriors mitjançant:
R
i
j
k
=
R
i
k
k
−
1
(
R
k
k
k
−
1
)
∗
R
k
j
k
−
1
∣
R
i
j
k
−
1
{\displaystyle R_{ij}^{k}=R_{ik}^{k-1}\left(R_{kk}^{k-1}\right)^{\ast }R_{kj}^{k-1}\mid R_{ij}^{k-1}}
Una altra manera d'entendre el procediment de l'algorisme és com un "mètode d'eliminació", on els estats de
0
{\textstyle 0}
a
n
{\textstyle n}
s'eliminen successivament: quan s'elimina l'estat
k
{\textstyle k}
, l'expressió regular
R
i
j
k
−
1
{\textstyle R_{ij}^{k-1}}
, que descriu les paraules d'entrada que generen un camí de l'estat
i
>
k
{\textstyle i>k}
a l'estat
j
>
k
{\displaystyle j>k}
, és reescrita dins
R
i
j
k
{\displaystyle R_{ij}^{k}}
a fi de tenir en compte la possibilitat de passar per l'estat "eliminat"
k
{\textstyle k}
.
Per inducció en
k
{\textstyle k}
, es pot veure que la longitud[ 5] de cada expressió
R
i
j
k
{\textstyle R_{ij}^{k}}
és com a màxim
1
3
(
4
k
+
1
(
6
s
+
7
)
−
4
)
{\textstyle {\frac {1}{3}}\left(4^{k+1}\left(6s+7\right)-4\right)}
símbols, on
s
{\textstyle s}
denota el nombre de caràcters dins l'alfabet
Σ
{\textstyle \Sigma }
. Per tant, la longitud de l'expressió regular que representa la llengua acceptada per
M
{\textstyle M}
és com a màxim
1
3
(
4
n
+
1
(
6
s
+
7
)
f
−
f
−
3
)
{\textstyle {\frac {1}{3}}\left(4^{n+1}\left(6s+7\right)f-f-3\right)}
símbols, on
f
{\textstyle f}
denota el nombre d'estats finals. Aquest creixement exponencial és inevitable, ja que existeixen famílies d'AFDs pels quals qualsevol expressió regular equivalent ha de ser de mida exponencial.[ 6]
A la pràctica, la mida de l'expressió regular obtinguda per l'algorisme pot ser molt diferent depenent en l'ordre en què es consideren els estats, i.e. l'ordre amb el qual són numerats de
0
{\textstyle 0}
a
n
{\textstyle n}
.
Autòmat finit determinista (AFD) de l'exemple
L'autòmat donat a l'esquema pot ser descrit com
M
=
(
Q
,
Σ
,
δ
,
q
0
,
F
)
{\textstyle M=(Q,\Sigma ,\delta ,q_{0},F)}
amb
Q
=
{
q
0
,
q
1
,
q
2
}
{\textstyle Q=\{q_{0},q_{1},q_{2}\}}
el conjunt d'estats,
Σ
=
{
a
,
b
}
{\textstyle \Sigma =\{a,b\}}
l'alfabet d'entrada,
δ
{\displaystyle \delta }
la funció de transició amb
δ
(
q
0
,
a
)
=
q
0
{\textstyle \delta (q_{0},a)=q_{0}}
,
δ
(
q
0
,
b
)
=
q
1
{\textstyle \delta (q_{0},b)=q_{1}}
,
δ
(
q
1
,
a
)
=
q
2
{\textstyle \delta (q_{1},a)=q_{2}}
,
δ
(
q
1
,
b
)
=
q
1
{\textstyle \delta (q_{1},b)=q_{1}}
,
δ
(
q
2
,
a
)
=
q
1
{\textstyle \delta (q_{2},a)=q_{1}}
,
δ
(
q
0
,
b
)
=
q
1
{\textstyle \delta (q_{0},b)=q_{1}}
,
q
0
{\textstyle q_{0}}
l'estat inicial,
F
=
{
q
1
}
{\displaystyle F=\{q_{1}\}}
el conjunt d'estats finals o d'acceptació.
L'algorisme de Kleene computa les expressions regulars inicials de la següent forma:
R
00
−
1
=
a
∣
ϵ
R
01
−
1
=
b
R
02
−
1
=
∅
R
10
−
1
=
∅
R
11
−
1
=
b
∣
ϵ
R
12
−
1
=
a
R
20
−
1
=
∅
R
21
−
1
=
a
∣
b
R
22
−
1
=
ϵ
{\displaystyle {\begin{aligned}R_{00}^{-1}&=a\mid \epsilon \\R_{01}^{-1}&=b\\R_{02}^{-1}&=\emptyset \\R_{10}^{-1}&=\emptyset \\R_{11}^{-1}&=b\mid \epsilon \\R_{12}^{-1}&=a\\R_{20}^{-1}&=\emptyset \\R_{21}^{-1}&=a\mid b\\R_{22}^{-1}&=\epsilon \end{aligned}}}
Seguidament, les
R
i
j
k
{\textstyle R_{ij}^{k}}
es computen a partir de les
R
i
j
k
−
1
{\textstyle R_{ij}^{k-1}}
pas a pas per
k
=
0
,
1
,
2
{\textstyle k=0,1,2}
. S'utilitzen igualtats de l'àlgebra de Kleene per a simplificar les expressions regulars tant com sigui possible.
Pas 0
R
00
0
=
R
00
−
1
(
R
00
−
1
)
∗
R
00
−
1
∣
R
00
−
1
=
(
a
∣
ϵ
)
(
a
∣
ϵ
)
∗
(
a
∣
ϵ
)
∣
a
∣
ϵ
=
a
∗
R
01
0
=
R
00
−
1
(
R
00
−
1
)
∗
R
01
−
1
∣
R
01
−
1
=
(
a
∣
ϵ
)
(
a
∣
ϵ
)
∗
b
∣
b
=
a
∗
b
R
02
0
=
R
00
−
1
(
R
00
−
1
)
∗
R
02
−
1
∣
R
02
−
1
=
(
a
∣
ϵ
)
(
a
∣
ϵ
)
∗
∅
∣
∅
=
∅
R
10
0
=
R
10
−
1
(
R
00
−
1
)
∗
R
00
−
1
∣
R
10
−
1
=
∅
(
a
∣
ϵ
)
∗
(
a
∣
ϵ
)
∣
∅
=
∅
R
11
0
=
R
10
−
1
(
R
00
−
1
)
∗
R
01
−
1
∣
R
11
−
1
=
∅
(
a
∣
ϵ
)
∗
b
∣
b
∣
ϵ
=
b
∣
ϵ
R
12
0
=
R
10
−
1
(
R
00
−
1
)
∗
R
02
−
1
∣
R
12
−
1
=
∅
(
a
∣
ϵ
)
∗
∅
∣
a
=
a
R
20
0
=
R
20
−
1
(
R
00
−
1
)
∗
R
00
−
1
∣
R
20
−
1
=
∅
(
a
∣
ϵ
)
∗
(
a
∣
ϵ
)
∣
∅
=
∅
R
21
0
=
R
20
−
1
(
R
00
−
1
)
∗
R
01
−
1
∣
R
21
−
1
=
∅
(
a
∣
ϵ
)
∗
b
∣
a
∣
b
=
a
∣
b
R
22
0
=
R
20
−
1
(
R
00
−
1
)
∗
R
02
−
1
∣
R
22
−
1
=
∅
(
a
∣
ϵ
)
∗
∅
∣
ϵ
=
ϵ
{\displaystyle {\begin{alignedat}{00}R_{00}^{0}&=&R_{00}^{-1}\left(R_{00}^{-1}\right)^{\ast }R_{00}^{-1}\mid R_{00}^{-1}&=&(a\mid \epsilon )&(a\mid \epsilon )^{\ast }&(a\mid \epsilon )&\mid &a\mid \epsilon &=&a^{\ast }\\R_{01}^{0}&=&R_{00}^{-1}\left(R_{00}^{-1}\right)^{\ast }R_{01}^{-1}\mid R_{01}^{-1}&=&(a\mid \epsilon )&(a\mid \epsilon )^{\ast }&b&\mid &b&=&a^{\ast }b\\R_{02}^{0}&=&R_{00}^{-1}\left(R_{00}^{-1}\right)^{\ast }R_{02}^{-1}\mid R_{02}^{-1}&=&(a\mid \epsilon )&(a\mid \epsilon )^{\ast }&\emptyset &\mid &\emptyset &=&\emptyset \\R_{10}^{0}&=&R_{10}^{-1}\left(R_{00}^{-1}\right)^{\ast }R_{00}^{-1}\mid R_{10}^{-1}&=&\emptyset &(a\mid \epsilon )^{\ast }&(a\mid \epsilon )&\mid &\emptyset &=&\emptyset \\R_{11}^{0}&=&R_{10}^{-1}\left(R_{00}^{-1}\right)^{\ast }R_{01}^{-1}\mid R_{11}^{-1}&=&\emptyset &(a\mid \epsilon )^{\ast }&b&\mid &b\mid \epsilon &=&b\mid \epsilon \\R_{12}^{0}&=&R_{10}^{-1}\left(R_{00}^{-1}\right)^{\ast }R_{02}^{-1}\mid R_{12}^{-1}&=&\emptyset &(a\mid \epsilon )^{\ast }&\emptyset &\mid &a&=&a\\R_{20}^{0}&=&R_{20}^{-1}\left(R_{00}^{-1}\right)^{\ast }R_{00}^{-1}\mid R_{20}^{-1}&=&\emptyset &(a\mid \epsilon )^{\ast }&(a\mid \epsilon )&\mid &\emptyset &=&\emptyset \\R_{21}^{0}&=&R_{20}^{-1}\left(R_{00}^{-1}\right)^{\ast }R_{01}^{-1}\mid R_{21}^{-1}&=&\emptyset &(a\mid \epsilon )^{\ast }&b&\mid &a\mid b&=&a\mid b\\R_{22}^{0}&=&R_{20}^{-1}\left(R_{00}^{-1}\right)^{\ast }R_{02}^{-1}\mid R_{22}^{-1}&=&\emptyset &(a\mid \epsilon )^{\ast }&\emptyset &\mid &\epsilon &=&\epsilon \end{alignedat}}}
Pas 1
R
00
1
=
R
01
0
(
R
11
0
)
∗
R
10
0
∣
R
00
0
=
a
∗
b
(
b
∣
ϵ
)
∗
∅
∣
a
∗
=
a
∗
R
01
1
=
R
01
0
(
R
11
0
)
∗
R
11
0
∣
R
01
0
=
a
∗
b
(
b
∣
ϵ
)
∗
(
b
∣
ϵ
)
∣
a
∗
b
=
a
∗
b
∗
b
R
02
1
=
R
01
0
(
R
11
0
)
∗
R
12
0
∣
R
02
0
=
a
∗
b
(
b
∣
ϵ
)
∗
a
∣
∅
=
a
∗
b
∗
b
a
R
10
1
=
R
11
0
(
R
11
0
)
∗
R
10
0
∣
R
10
0
=
(
b
∣
ϵ
)
(
b
∣
ϵ
)
∗
∅
∣
∅
=
∅
R
11
1
=
R
11
0
(
R
11
0
)
∗
R
11
0
∣
R
11
0
=
(
b
∣
ϵ
)
(
b
∣
ϵ
)
∗
(
b
∣
ϵ
)
∣
b
∣
ϵ
=
b
∗
R
12
1
=
R
11
0
(
R
11
0
)
∗
R
12
0
∣
R
12
0
=
(
b
∣
ϵ
)
(
b
∣
ϵ
)
∗
a
∣
a
=
b
∗
a
R
20
1
=
R
21
0
(
R
11
0
)
∗
R
10
0
∣
R
20
0
=
(
a
∣
b
)
(
b
∣
ϵ
)
∗
∅
∣
∅
=
∅
R
21
1
=
R
21
0
(
R
11
0
)
∗
R
11
0
∣
R
21
0
=
(
a
∣
b
)
(
b
∣
ϵ
)
∗
(
b
∣
ϵ
)
∣
a
∣
b
=
(
a
∣
b
)
b
∗
R
22
1
=
R
21
0
(
R
11
0
)
∗
R
12
0
∣
R
22
0
=
(
a
∣
b
)
(
b
∣
ϵ
)
∗
a
∣
ϵ
=
(
a
∣
b
)
b
∗
a
∣
ϵ
{\displaystyle {\begin{alignedat}{00}R_{00}^{1}&=&R_{01}^{0}\left(R_{11}^{0}\right)^{\ast }R_{10}^{0}\mid R_{00}^{0}&=&a^{\ast }b&(b\mid \epsilon )^{\ast }&\emptyset &\mid &a^{\ast }&=&a^{\ast }\\R_{01}^{1}&=&R_{01}^{0}\left(R_{11}^{0}\right)^{\ast }R_{11}^{0}\mid R_{01}^{0}&=&a^{\ast }b&(b\mid \epsilon )^{\ast }&(b\mid \epsilon )&\mid &a^{\ast }b&=&a^{\ast }b^{\ast }b\\R_{02}^{1}&=&R_{01}^{0}\left(R_{11}^{0}\right)^{\ast }R_{12}^{0}\mid R_{02}^{0}&=&a^{\ast }b&(b\mid \epsilon )^{\ast }&a&\mid &\emptyset &=&a^{\ast }b^{\ast }ba\\R_{10}^{1}&=&R_{11}^{0}\left(R_{11}^{0}\right)^{\ast }R_{10}^{0}\mid R_{10}^{0}&=&(b\mid \epsilon )&(b\mid \epsilon )^{\ast }&\emptyset &\mid &\emptyset &=&\emptyset \\R_{11}^{1}&=&R_{11}^{0}\left(R_{11}^{0}\right)^{\ast }R_{11}^{0}\mid R_{11}^{0}&=&(b\mid \epsilon )&(b\mid \epsilon )^{\ast }&(b\mid \epsilon )&\mid &b\mid \epsilon &=&b^{\ast }\\R_{12}^{1}&=&R_{11}^{0}\left(R_{11}^{0}\right)^{\ast }R_{12}^{0}\mid R_{12}^{0}&=&(b\mid \epsilon )&(b\mid \epsilon )^{\ast }&a&\mid &a&=&b^{\ast }a\\R_{20}^{1}&=&R_{21}^{0}\left(R_{11}^{0}\right)^{\ast }R_{10}^{0}\mid R_{20}^{0}&=&(a\mid b)&(b\mid \epsilon )^{\ast }&\emptyset &\mid &\emptyset &=&\emptyset \\R_{21}^{1}&=&R_{21}^{0}\left(R_{11}^{0}\right)^{\ast }R_{11}^{0}\mid R_{21}^{0}&=&(a\mid b)&(b\mid \epsilon )^{\ast }&(b\mid \epsilon )&\mid &a\mid b&=&(a\mid b)b^{\ast }\\R_{22}^{1}&=&R_{21}^{0}\left(R_{11}^{0}\right)^{\ast }R_{12}^{0}\mid R_{22}^{0}&=&(a\mid b)&(b\mid \epsilon )^{\ast }&a&\mid &\epsilon &=&(a\mid b)b^{\ast }a\mid \epsilon \end{alignedat}}}
Pas 2
R
00
2
=
R
02
1
(
R
22
1
)
∗
R
10
1
∣
R
00
1
=
a
∗
b
∗
b
a
(
(
a
∣
b
)
b
∗
a
∣
ϵ
)
∗
∅
∣
a
∗
=
a
∗
R
01
2
=
R
02
1
(
R
22
1
)
∗
R
11
1
∣
R
01
1
=
a
∗
b
∗
b
a
(
(
a
∣
b
)
b
∗
a
∣
ϵ
)
∗
(
a
∣
b
)
b
∗
∣
a
∗
b
∗
b
=
a
∗
b
(
a
(
a
∣
b
)
∣
b
)
∗
R
02
2
=
R
02
1
(
R
22
1
)
∗
R
12
1
∣
R
02
1
=
a
∗
b
∗
b
a
(
(
a
∣
b
)
b
∗
a
∣
ϵ
)
∗
(
(
a
∣
b
)
b
∗
a
∣
ϵ
)
∣
a
∗
b
∗
b
a
=
a
∗
b
∗
b
(
a
(
a
∣
b
)
b
∗
)
∗
a
R
10
2
=
R
12
1
(
R
22
1
)
∗
R
10
1
∣
R
10
1
=
b
∗
a
(
(
a
∣
b
)
b
∗
a
∣
ϵ
)
∗
∅
∣
∅
=
∅
R
11
2
=
R
12
1
(
R
22
1
)
∗
R
11
1
∣
R
11
1
=
b
∗
a
(
(
a
∣
b
)
b
∗
a
∣
ϵ
)
∗
(
a
∣
b
)
b
∗
∣
b
∗
=
(
a
(
a
∣
b
)
∣
b
)
∗
R
12
2
=
R
12
1
(
R
22
1
)
∗
R
12
1
∣
R
12
1
=
b
∗
a
(
(
a
∣
b
)
b
∗
a
∣
ϵ
)
∗
(
(
a
∣
b
)
b
∗
a
∣
ϵ
)
∣
b
∗
a
=
(
a
(
a
∣
b
)
∣
b
)
∗
a
R
20
2
=
R
22
1
(
R
22
1
)
∗
R
10
1
∣
R
20
1
=
(
(
a
∣
b
)
b
∗
a
∣
ϵ
)
(
(
a
∣
b
)
b
∗
a
∣
ϵ
)
∗
∅
∣
∅
=
∅
R
21
2
=
R
22
1
(
R
22
1
)
∗
R
11
1
∣
R
21
1
=
(
(
a
∣
b
)
b
∗
a
∣
ϵ
)
(
(
a
∣
b
)
b
∗
a
∣
ϵ
)
∗
(
a
∣
b
)
b
∗
∣
(
a
∣
b
)
b
∗
=
(
a
∣
b
)
(
a
(
a
∣
b
)
∣
b
)
∗
R
22
2
=
R
22
1
(
R
22
1
)
∗
R
12
1
∣
R
22
1
=
(
(
a
∣
b
)
b
∗
a
∣
ϵ
)
(
(
a
∣
b
)
b
∗
a
∣
ϵ
)
∗
(
(
a
∣
b
)
b
∗
a
∣
ϵ
)
∣
(
a
∣
b
)
b
∗
a
∣
ϵ
=
(
(
a
∣
b
)
b
∗
a
)
∗
{\displaystyle {\begin{alignedat}{00}R_{00}^{2}&=&R_{02}^{1}\left(R_{22}^{1}\right)^{\ast }R_{10}^{1}\mid R_{00}^{1}&=&a^{\ast }b^{\ast }ba&((a\mid b)b^{\ast }a\mid \epsilon )^{\ast }&\emptyset &\mid &a^{\ast }&=&a^{\ast }\\R_{01}^{2}&=&R_{02}^{1}\left(R_{22}^{1}\right)^{\ast }R_{11}^{1}\mid R_{01}^{1}&=&a^{\ast }b^{\ast }ba&((a\mid b)b^{\ast }a\mid \epsilon )^{\ast }&(a\mid b)b^{\ast }&\mid &a^{\ast }b^{\ast }b&=&a^{\ast }b(a(a\mid b)\mid b)^{\ast }\\R_{02}^{2}&=&R_{02}^{1}\left(R_{22}^{1}\right)^{\ast }R_{12}^{1}\mid R_{02}^{1}&=&a^{\ast }b^{\ast }ba&((a\mid b)b^{\ast }a\mid \epsilon )^{\ast }&((a\mid b)b^{\ast }a\mid \epsilon )&\mid &a^{\ast }b^{\ast }ba&=&a^{\ast }b^{\ast }b(a(a\mid b)b^{\ast })^{\ast }a\\R_{10}^{2}&=&R_{12}^{1}\left(R_{22}^{1}\right)^{\ast }R_{10}^{1}\mid R_{10}^{1}&=&b^{\ast }a&((a\mid b)b^{\ast }a\mid \epsilon )^{\ast }&\emptyset &\mid &\emptyset &=&\emptyset \\R_{11}^{2}&=&R_{12}^{1}\left(R_{22}^{1}\right)^{\ast }R_{11}^{1}\mid R_{11}^{1}&=&b^{\ast }a&((a\mid b)b^{\ast }a\mid \epsilon )^{\ast }&(a\mid b)b^{\ast }&\mid &b^{\ast }&=&(a(a\mid b)\mid b)^{\ast }\\R_{12}^{2}&=&R_{12}^{1}\left(R_{22}^{1}\right)^{\ast }R_{12}^{1}\mid R_{12}^{1}&=&b^{\ast }a&((a\mid b)b^{\ast }a\mid \epsilon )^{\ast }&((a\mid b)b^{\ast }a\mid \epsilon )&\mid &b^{\ast }a&=&(a(a\mid b)\mid b)^{\ast }a\\R_{20}^{2}&=&R_{22}^{1}\left(R_{22}^{1}\right)^{\ast }R_{10}^{1}\mid R_{20}^{1}&=&((a\mid b)b^{\ast }a\mid \epsilon )&((a\mid b)b^{\ast }a\mid \epsilon )^{\ast }&\emptyset &\mid &\emptyset &=&\emptyset \\R_{21}^{2}&=&R_{22}^{1}\left(R_{22}^{1}\right)^{\ast }R_{11}^{1}\mid R_{21}^{1}&=&((a\mid b)b^{\ast }a\mid \epsilon )&((a\mid b)b^{\ast }a\mid \epsilon )^{\ast }&(a\mid b)b^{\ast }&\mid &(a\mid b)b^{\ast }&=&(a\mid b)(a(a\mid b)\mid b)^{\ast }\\R_{22}^{2}&=&R_{22}^{1}\left(R_{22}^{1}\right)^{\ast }R_{12}^{1}\mid R_{22}^{1}&=&((a\mid b)b^{\ast }a\mid \epsilon )&((a\mid b)b^{\ast }a\mid \epsilon )^{\ast }&((a\mid b)b^{\ast }a\mid \epsilon )&\mid &(a\mid b)b^{\ast }a\mid \epsilon &=&((a\mid b)b^{\ast }a)^{\ast }\end{alignedat}}}
Com
q
0
{\textstyle q_{0}}
és l'estat inicial i
q
1
{\textstyle q_{1}}
és l'únic estat final, l'expressió regular
R
01
2
{\textstyle R_{01}^{2}}
denota el conjunt de totes les paraules d'entrada acceptades per l'autòmat.
↑ McNaughton , R.; Yamada , H. IRE Transactions on Electronic Computers , EC-9, 1, 3-1960, pàg. 39–47. DOI : 10.1109/TEC.1960.5221603 . ISSN : 0367-9950 .
↑ Jonathan L. Gross and Jay Yellen. Handbook of Graph Theory . CRC Press, 2004 (Discrete Mathematics and it Applications). ISBN 1-58488-090-2 . Here: sect.2.1, remark R13 on p.65
↑ Kleene, Stephen C. Automata Studies, Annals of Math. Studies , 34, 1956. Here: sect.9, p.37-40
↑ John E. Hopcroft, Jeffrey D. Ullman . Introduction to Automata Theory, Languages, and Computation . Addison-Wesley, 1979. ISBN 0-201-02988-X . Here: Section 3.2.1 pages 91-96
↑ More precisely, the number of regular-expression symbols, "a i ", "ε", "|", "* ", "·"; not counting parentheses.
↑ Gruber , Hermann; Holzer , Markus Automata, Languages and Programming , 5126, 2008, pàg. 39–50. DOI : 10.1007/978-3-540-70583-3_4 . . Theorem 16.