El algoritmo de Kleene

En la informática teórica , en particular en la teoría del lenguaje formal , 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 que sigue a continuación sigue a Gross y Yellen (2004). ^{[ 2 ]}

Dado un autómata finito no determinista M = ( Q , Σ, δ, q ₀ , F ), con Q = { q ₀ ,..., q _n } su conjunto de estados , el algoritmo calcula

los conjuntos R ^k _ij de todas las cadenas que llevan M del estado q _i al estado q _j sin pasar por ningún estado numerado superior a k .

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 R ^k _ij está representado por una expresión regular; el algoritmo las calcula paso a paso para k = -1, 0, ..., n . Como no hay ningún estado numerado mayor que n , la expresión regular R ⁿ _0j representa el conjunto de todas las cadenas que llevan a M desde su estado inicial q ₀ hasta q _j . Si F = { q ₁ ,..., q _f } es el conjunto de estados de aceptación , la expresión regular R ⁿ ₀₁ | ... | R ⁿ _0f representa el lenguaje aceptado por M.

Las expresiones regulares iniciales, para k = -1, se calculan de la siguiente manera para i ≠ j :

R ⁻¹ _ij = a ₁ | ... | a _m donde q _j ∈ δ( q _i , a ₁ ), ..., q _j ∈ δ( q _i , a _m )   

y como sigue para i = j :

R ⁻¹ _ii = a ₁ | ... | a _m | ε donde q _i ∈ δ( q _i , a ₁ ), ..., q _i ∈ δ( q _i , a _m )   

En otras palabras, R ⁻¹ _ij menciona 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 R ^k _ij se calculan a partir de las anteriores mediante

R ^k _ij = R ^{k -1} _ik ( R ^{k -1} _kk ) ^* R ^{k -1} _kj | R ^{k -1} _ij

Otra forma de entender el funcionamiento del algoritmo es como un "método de eliminación", donde los estados del 0 al n se eliminan sucesivamente: cuando se elimina el estado k , la expresión regular R ^{k -1} _ij , que describe las palabras que etiquetan un camino del estado i > k al estado j > k , se reescribe en R ^k _ij para 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 R ^k _ij es como máximo 1/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. Este crecimiento 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 el procedimiento considere los estados, es decir, el orden en que se numeren del 0 al n .

El autómata que se muestra en la imagen se puede describir como M = ( Q , Σ, δ, q ₀ , F ) con

• el conjunto de estados Q = { q ₀ , q ₁ , q ₂ },
• el alfabeto de entrada Σ = { a , b },
• la función de transición δ con δ( q ₀ , a )= q ₀ ,  δ( q ₀ , b )= q ₁ ,  δ( q ₁ , a )= q ₂ ,  δ( q ₁ , b )= q ₁ ,  δ( q ₂ , a )= q ₁ , y δ( q ₂ , b )= q ₁ ,
• el estado inicial q ₀ y
• conjunto de estados de aceptación F = { q ₁ }.

El algoritmo de Kleene calcula las expresiones regulares iniciales como

Después de eso, los R ^k _ij se calculan a partir de los R ^{k -1} _ij paso a paso para k = 0, 1, 2. Se utilizan igualdades de álgebra de Kleene para simplificar las expresiones regulares tanto como sea posible.

Paso 0

Paso 1

Paso 2

Dado que q ₀ es el estado inicial y q ₁ es el único estado de aceptación, la expresión regular R ² ₀₁ denota el conjunto de todas las cadenas aceptadas por el autómata.

• Algoritmo de Floyd-Warshall : un algoritmo sobre grafos ponderados que puede implementarse mediante el algoritmo de Kleene utilizando un álgebra de Kleene particular.
• Problema de la altura de las estrellas : ¿cuál es la profundidad mínima de anidamiento de estrellas de todas las expresiones regulares correspondientes a un autómata finito determinista (AFD) dado?
• Problema generalizado de la altura de las estrellas : si se permite un operador de complemento adicional en las expresiones regulares, ¿se puede limitar la profundidad de anidamiento de las estrellas de la salida del algoritmo de Kleene a un límite fijo?
• El algoritmo de construcción de Thompson transforma una expresión regular en un autómata finito.