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,\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 ${\textstyle i}$ i ${\textstyle j}$ poden ser superiors a $k$, però no cap estat intermedi. Cada conjunt ${\textstyle R_{ij}^{k}}$ és representat per una expressió regular; l'algorisme els computa pas a pas per ${\textstyle k=-1,0,\dots ,n}$. Com no hi ha cap estat superior a ${\textstyle n}$, l'expressió regular ${\textstyle R_{0j}^{n}}$ representa el conjunt de totes les entrades que porten $M$ del seu estat inicial ${\textstyle q_{0}}$ a ${\textstyle q_{j}}$. Si ${\textstyle F=\{q_{1},\dots ,q_{f}\}}$ és el conjunt d'estats finals, l'expressió regular ${\textstyle R_{01}^{n}\mid \dots \mid R_{0f}^{n}}$ representa el llenguatge acceptat per ${\textstyle M}$.

Les expressions regulars inicials, per a ${\textstyle k=-1}$, es computen de la següent manera per a ${\textstyle i\neq 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 ${\textstyle i=j}$:

$R_{ii}^{-1}=a_{1}\mid \dots \mid a_{m}\mid \epsilon$ on $q_{i}\in \delta (q_{i},a_{1}),\dots ,q_{i}\in \delta (q_{i},a_{m})$

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

Seguidament, en cada pas les expressions ${\textstyle 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 ${\textstyle 0}$ a ${\textstyle n}$ s'eliminen successivament: quan s'elimina l'estat ${\textstyle k}$, l'expressió regular ${\textstyle R_{ij}^{k-1}}$, que descriu les paraules d'entrada que generen un camí de l'estat ${\textstyle 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" ${\textstyle k}$.

Per inducció en ${\textstyle k}$, es pot veure que la longitud de cada expressió ${\textstyle R_{ij}^{k}}$ és com a màxim ${\textstyle {\frac {1}{3}}\left(4^{k+1}\left(6s+7\right)-4\right)}$ símbols, on ${\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 ${\textstyle M}$ és com a màxim  ${\textstyle {\frac {1}{3}}\left(4^{n+1}\left(6s+7\right)f-f-3\right)}$ símbols, on ${\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.

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 ${\textstyle 0}$ a ${\textstyle n}$.

Exemple

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

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

• ${\textstyle Q=\{q_{0},q_{1},q_{2}\}}$ el conjunt d'estats,
• ${\textstyle \Sigma =\{a,b\}}$ l'alfabet d'entrada,
• $\delta$ la funció de transició amb ${\textstyle \delta (q_{0},a)=q_{0}}$, ${\textstyle \delta (q_{0},b)=q_{1}}$, ${\textstyle \delta (q_{1},a)=q_{2}}$, ${\textstyle \delta (q_{1},b)=q_{1}}$, ${\textstyle \delta (q_{2},a)=q_{1}}$, ${\textstyle \delta (q_{0},b)=q_{1}}$,
• ${\textstyle 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{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 ${\textstyle R_{ij}^{k}}$ es computen a partir de les ${\textstyle R_{ij}^{k-1}}$ pas a pas per ${\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

${\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

${\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

${\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 ${\textstyle q_{0}}$ és l'estat inicial i ${\textstyle q_{1}}$ és l'únic estat final, l'expressió regular ${\textstyle R_{01}^{2}}$ denota el conjunt de totes les paraules d'entrada acceptades per l'autòmat.