En informática teórica , en particular en teoría de lenguajes formales , el algoritmo de Kleene transforma un autómata finito no determinista (AFN) dado en una expresión regular . Junto con otros algoritmos de conversión, establece la equivalencia de varios formatos de descripción para lenguajes regulares . Presentaciones alternativas del mismo método incluyen el "método de eliminación" atribuido a Brzozowski y McCluskey , el algoritmo de McNaughton y Yamada , [1] y el uso del lema de Arden .
Según Gross y Yellen (2004), [2] el algoritmo se remonta a Kleene (1956). [3] Una presentación del algoritmo en el caso de autómatas finitos deterministas (AFD) se da en Hopcroft y Ullman (1979). [4] La presentación del algoritmo para AFN a continuación sigue a Gross y Yellen (2004). [2]
Dado un autómata finito no determinista M = ( Q , Σ, δ, q 0 , F ), con Q = { q 0 ,..., q n } su conjunto de estados , el algoritmo calcula
Aquí, "pasar por un estado" significa entrar y salir de él, por lo que tanto i como j pueden ser mayores que k , pero ningún estado intermedio puede serlo. Cada conjunto Ryo
ijse representa mediante una expresión regular; el algoritmo los calcula paso a paso para k = -1, 0, ..., n . Como no hay ningún estado numerado más alto que n , la expresión regular Rn
0jrepresenta el conjunto de todas las cadenas que toman M desde su estado inicial q 0 hasta q j . Si F = { q 1 ,..., q f } es el conjunto de estados aceptados , la expresión regular Rnúmero
01| ... | Rn.º
derepresenta el lenguaje aceptado por M.
Las expresiones regulares iniciales, para k = -1, se calculan de la siguiente manera para i ≠ j :
y como sigue para i = j :
En otras palabras, R−1
ijmenciona todas las letras que etiquetan una transición de i a j , y también incluimos ε en el caso donde i = j .
Después de eso, en cada paso las expresiones Ryo
ijse calculan a partir de los anteriores mediante
Otra forma de entender el funcionamiento del algoritmo es como un "método de eliminación", donde los estados de 0 a n se eliminan sucesivamente: cuando se elimina el estado k , se utiliza la expresión regular Rk -1
ij, que describe las palabras que etiquetan una ruta desde el estado i > k al estado j > k , se reescribe en Ryo
ijpara tener en cuenta la posibilidad de pasar por el estado “eliminado” k .
Por inducción sobre k , se puede demostrar que la longitud [5] de cada expresión Ryo
ijes como máximo1/3 (4 k +1 (6 s +7) - 4) símbolos, donde s denota el número de caracteres en Σ. Por lo tanto, la longitud de la expresión regular que representa el lenguaje aceptado por M es como máximo 1/3 (4 n + 1 (6 s + 7) f - f - 3) símbolos, donde f denota el número de estados finales. Esta explosión exponencial es inevitable, porque existen familias de DFA para las cuales cualquier expresión regular equivalente debe ser de tamaño exponencial. [6]
En la práctica, el tamaño de la expresión regular obtenida al ejecutar el algoritmo puede ser muy diferente dependiendo del orden en que los estados son considerados por el procedimiento, es decir, el orden en que son numerados de 0 a n .
El autómata que se muestra en la imagen se puede describir como M = ( Q , Σ, δ, q 0 , F ) con
El algoritmo de Kleene calcula las expresiones regulares iniciales como
Después de eso, el Ryo
ijse calculan a partir de Rk -1
ijpaso a paso para k = 0, 1, 2. Las igualdades del álgebra de Kleene se utilizan para simplificar las expresiones regulares tanto como sea posible.
Dado que q 0 es el estado inicial y q 1 es el único estado de aceptación, la expresión regular R2
01denota el conjunto de todas las cadenas aceptadas por el autómata.