Algorisme de Kleene

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.

Descripció de l'algorisme

Segons Brut i Yellen (2004), l'algoritme pot ser remuntat a Kleene (1956). Una presentació de l'algorisme en el cas de l'autòmat determinista finit (ADF) és donat a Hopcroft i Ullman (1979). La presentació de l'algorisme per AFNDs a sota segueix Brut i Yellen (2004).

Donat un autòmat finit no determinista $M=(Q,\mathrm{\Sigma },\delta ,q_0,F)$, amb $Q=\{q_0,\dots ,q_n\}$ el seu conjunt d'estats, l'algorisme computa els conjunts $R_{ij}^k$ de totes les entrades que porten $M$ de l'estat $q_i$ a $q_j$ sense passar per cap estat superior a $k$. Aquí, "passar per un estat" vol dir entrar-hi i sortir-ne, així que ambdós $i$ i $j$ poden ser superiors a $k$, però no cap estat intermedi. Cada conjunt $R_{ij}^k$ és representat per una expressió regular; l'algorisme els computa pas a pas per $k=-1,0,\dots ,n$. Com no hi ha cap estat superior a $n$, l'expressió regular $R_{0j}^n$ representa el conjunt de totes les entrades que porten $M$ del seu estat inicial $q_0$ a $q_j$. Si $F=\{q_1,\dots ,q_f\}$ és el conjunt d'estats finals, l'expressió regular $R_{01}^n\mid \dots \mid R_{0f}^n$ representa el llenguatge acceptat per $M$.

Les expressions regulars inicials, per a $k=-1$, es computen de la següent manera per a $i\ne j$:

$R_{ij}^{-1}=a_1\mid \dots \mid a_m$ on $q_j\in \delta (q_i,a_1),\dots ,q_j\in \delta (q_i,a_m)$

i com segueix per a $i=j$:

$R_{ii}^{-1}=a_1\mid \dots \mid a_m\mid ϵ$ on $q_i\in \delta (q_i,a_1),\dots ,q_i\in \delta (q_i,a_m)$

És a dir, $R_{ij}^{-1}$ representa tots els símbols d'entrada que causen una transició d'$q_i$ a $q_j$, i també incloem $ϵ$ quan $i=j$.

Seguidament, en cada pas les expressions $R_{ij}^k$ es calculen a partir de les anteriors mitjançant:

$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$ a $n$ s'eliminen successivament: quan s'elimina l'estat $k$, l'expressió regular $R_{ij}^{k-1}$, que descriu les paraules d'entrada que generen un camí de l'estat $i>k$ a l'estat $j>k$, és reescrita dins $R_{ij}^k$ a fi de tenir en compte la possibilitat de passar per l'estat "eliminat" $k$.

Per inducció en $k$, es pot veure que la longitud de cada expressió $R_{ij}^k$ és com a màxim $\frac{1}{3}(4^{k+1}(6s+7)-4)$ símbols, on $s$ denota el nombre de caràcters dins l'alfabet $\mathrm{\Sigma }$. Per tant, la longitud de l'expressió regular que representa la llengua acceptada per $M$ és com a màxim  $\frac{1}{3}(4^{n+1}(6s+7)f-f-3)$ símbols, on $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.

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$ a $n$.

Exemple

Autòmat finit determinista (AFD) de l'exemple

L'autòmat donat a l'esquema pot ser descrit com $M=(Q,\mathrm{\Sigma },\delta ,q_0,F)$ amb

• $Q=\{q_0,q_1,q_2\}$ el conjunt d'estats,
• $\mathrm{\Sigma }=\{a,b\}$ l'alfabet d'entrada,
• $\delta$ la funció de transició amb $\delta (q_0,a)=q_0$, $\delta (q_0,b)=q_1$, $\delta (q_1,a)=q_2$, $\delta (q_1,b)=q_1$, $\delta (q_2,a)=q_1$, $\delta (q_0,b)=q_1$,
• $q_0$ l'estat inicial,
• $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:

$\begin{array}{cc}{R}_{00}^{-1}& =a\mid ϵ\\ R_{01}^{-1}& =b\\ R_{02}^{-1}& =\mathrm{\varnothing }\\ R_{10}^{-1}& =\mathrm{\varnothing }\\ R_{11}^{-1}& =b\mid ϵ\\ R_{12}^{-1}& =a\\ R_{20}^{-1}& =\mathrm{\varnothing }\\ R_{21}^{-1}& =a\mid b\\ R_{22}^{-1}& =ϵ\end{array}$

Seguidament, les $R_{ij}^k$ es computen a partir de les $R_{ij}^{k-1}$ pas a pas per $k=0,1,2$. S'utilitzen igualtats de l'àlgebra de Kleene per a simplificar les expressions regulars tant com sigui possible.

Pas 0

$\begin{array}{ccccccccccc}{R}_{00}^0& =& R_{00}^{-1}{\left(R_{00}^{-1}\right)}^{\ast }{R}_{00}^{-1}\mid R_{00}^{-1}& =& (a\mid ϵ)& (a\mid ϵ{)}^{\ast }& (a\mid ϵ)& \mid & a\mid ϵ& =& a^{\ast }\\ R_{01}^0& =& R_{00}^{-1}{\left(R_{00}^{-1}\right)}^{\ast }{R}_{01}^{-1}\mid R_{01}^{-1}& =& (a\mid ϵ)& (a\mid ϵ{)}^{\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 ϵ)& (a\mid ϵ{)}^{\ast }& \mathrm{\varnothing }& \mid & \mathrm{\varnothing }& =& \mathrm{\varnothing }\\ R_{10}^0& =& R_{10}^{-1}{\left(R_{00}^{-1}\right)}^{\ast }{R}_{00}^{-1}\mid R_{10}^{-1}& =& \mathrm{\varnothing }& (a\mid ϵ{)}^{\ast }& (a\mid ϵ)& \mid & \mathrm{\varnothing }& =& \mathrm{\varnothing }\\ R_{11}^0& =& R_{10}^{-1}{\left(R_{00}^{-1}\right)}^{\ast }{R}_{01}^{-1}\mid R_{11}^{-1}& =& \mathrm{\varnothing }& (a\mid ϵ{)}^{\ast }& b& \mid & b\mid ϵ& =& b\mid ϵ\\ R_{12}^0& =& R_{10}^{-1}{\left(R_{00}^{-1}\right)}^{\ast }{R}_{02}^{-1}\mid R_{12}^{-1}& =& \mathrm{\varnothing }& (a\mid ϵ{)}^{\ast }& \mathrm{\varnothing }& \mid & a& =& a\\ R_{20}^0& =& R_{20}^{-1}{\left(R_{00}^{-1}\right)}^{\ast }{R}_{00}^{-1}\mid R_{20}^{-1}& =& \mathrm{\varnothing }& (a\mid ϵ{)}^{\ast }& (a\mid ϵ)& \mid & \mathrm{\varnothing }& =& \mathrm{\varnothing }\\ R_{21}^0& =& R_{20}^{-1}{\left(R_{00}^{-1}\right)}^{\ast }{R}_{01}^{-1}\mid R_{21}^{-1}& =& \mathrm{\varnothing }& (a\mid ϵ{)}^{\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}& =& \mathrm{\varnothing }& (a\mid ϵ{)}^{\ast }& \mathrm{\varnothing }& \mid & ϵ& =& ϵ\end{array}$

Pas 1

$\begin{array}{ccccccccccc}{R}_{00}^1& =& R_{01}^0{\left(R_{11}^0\right)}^{\ast }{R}_{10}^0\mid R_{00}^0& =& a^{\ast }b& (b\mid ϵ{)}^{\ast }& \mathrm{\varnothing }& \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 ϵ{)}^{\ast }& (b\mid ϵ)& \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 ϵ{)}^{\ast }& a& \mid & \mathrm{\varnothing }& =& 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 ϵ)& (b\mid ϵ{)}^{\ast }& \mathrm{\varnothing }& \mid & \mathrm{\varnothing }& =& \mathrm{\varnothing }\\ R_{11}^1& =& R_{11}^0{\left(R_{11}^0\right)}^{\ast }{R}_{11}^0\mid R_{11}^0& =& (b\mid ϵ)& (b\mid ϵ{)}^{\ast }& (b\mid ϵ)& \mid & b\mid ϵ& =& b^{\ast }\\ R_{12}^1& =& R_{11}^0{\left(R_{11}^0\right)}^{\ast }{R}_{12}^0\mid R_{12}^0& =& (b\mid ϵ)& (b\mid ϵ{)}^{\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 ϵ{)}^{\ast }& \mathrm{\varnothing }& \mid & \mathrm{\varnothing }& =& \mathrm{\varnothing }\\ R_{21}^1& =& R_{21}^0{\left(R_{11}^0\right)}^{\ast }{R}_{11}^0\mid R_{21}^0& =& (a\mid b)& (b\mid ϵ{)}^{\ast }& (b\mid ϵ)& \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 ϵ{)}^{\ast }& a& \mid & ϵ& =& (a\mid b)b^{\ast }a\mid ϵ\end{array}$

Pas 2

$\begin{array}{ccccccccccc}{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 ϵ{)}^{\ast }& \mathrm{\varnothing }& \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 ϵ{)}^{\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 ϵ{)}^{\ast }& ((a\mid b)b^{\ast }a\mid ϵ)& \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 ϵ{)}^{\ast }& \mathrm{\varnothing }& \mid & \mathrm{\varnothing }& =& \mathrm{\varnothing }\\ 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 ϵ{)}^{\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 ϵ{)}^{\ast }& ((a\mid b)b^{\ast }a\mid ϵ)& \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 ϵ)& ((a\mid b)b^{\ast }a\mid ϵ{)}^{\ast }& \mathrm{\varnothing }& \mid & \mathrm{\varnothing }& =& \mathrm{\varnothing }\\ 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 ϵ)& ((a\mid b)b^{\ast }a\mid ϵ{)}^{\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 ϵ)& ((a\mid b)b^{\ast }a\mid ϵ{)}^{\ast }& ((a\mid b)b^{\ast }a\mid ϵ)& \mid & (a\mid b)b^{\ast }a\mid ϵ& =& ((a\mid b)b^{\ast }a{)}^{\ast }\end{array}$

Com $q_0$ és l'estat inicial i $q_1$ és l'únic estat final, l'expressió regular $R_{01}^2$ denota el conjunt de totes les paraules d'entrada acceptades per l'autòmat.