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 (NFA) 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 .
Descripción del algoritmo
Según Gross y Yellen (2004), [2] el algoritmo se remonta a Kleene (1956). [3] Hopcroft y Ullman (1979) ofrecen una presentación del algoritmo en el caso de autómatas finitos deterministas (DFA). [4] La presentación del algoritmo para NFA 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
- los conjuntos Rk
ijde todas las cadenas que toman M del estado q i al q j sin pasar por ningún estado numerado más alto que 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 Rk
ijestá representado por una expresión regular; el algoritmo los calcula paso a paso para k = -1, 0, ..., n . Dado que 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 de aceptación , la expresión regular Rn
01| ... | Rn
0frepresenta el idioma aceptado por M .
Las expresiones regulares iniciales, para k = -1, se calculan de la siguiente manera para i ≠ j :
- R−1
ij= a 1 | ... | a m donde q j ∈ δ ( q yo , a 1 ), ..., q j ∈ δ ( q yo , a m )
y de la siguiente manera para i = j :
- R−1
ii= a 1 | ... | a m | ε donde q yo ∈ δ ( q yo , una 1 ), ..., q yo ∈ δ ( q yo , una m )
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 Rk
ij se calculan a partir de los anteriores por
- Rk
ij= Rk -1
ik( Rk -1
kk) * Rk -1
kj| Rk -1
ij
Otra manera 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 el estado k se retira, 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 Rk
ijpara tener en cuenta la posibilidad de pasar por el estado k "eliminado" .
Por inducción sobre k , se puede demostrar que la longitud [5] de cada expresión Rk
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 idioma 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 que 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 el que los estados son considerados por el procedimiento, es decir, el orden en el que se numeran de 0 a n .
Ejemplo
El autómata que se muestra en la imagen se puede describir como M = ( Q , Σ, δ, q 0 , F ) con
- el conjunto de estados Q = { q 0 , q 1 , q 2 },
- el alfabeto de entrada Σ = { a , b },
- la función de transición δ con δ ( q 0 , a ) = q 0 , δ ( q 0 , b ) = q 1 , δ ( q 1 , a ) = q 2 , δ ( q 1 , b ) = q 1 , δ ( q 2 , a ) = q 1 , y δ ( q 2 , b ) = q 1 ,
- el estado de inicio q 0 , y
- conjunto de estados de aceptación F = { q 1 }.
El algoritmo de Kleene calcula las expresiones regulares iniciales como
R−1
00= a | ε R−1
01= b R−1
02= ∅ R−1
10= ∅ R−1
11= b | ε R−1
12= a R−1
20= ∅ R−1
21= a | B R−1
22= ε
Después de eso, la Rk
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.
- Paso 0
R0
00= R−1
00( R−1
00) * R−1
00| R−1
00= ( a | ε) ( a | ε) * ( a | ε) | a | ε = a * R0
01= R−1
00( R−1
00) * R−1
01| R−1
01= ( a | ε) ( a | ε) * B | B = a * b R0
02= R−1
00( R−1
00) * R−1
02| R−1
02= ( a | ε) ( a | ε) * ∅ | ∅ = ∅ R0
10= R−1
10( R−1
00) * R−1
00| R−1
10= ∅ ( a | ε) * ( a | ε) | ∅ = ∅ R0
11= R−1
10( R−1
00) * R−1
01| R−1
11= ∅ ( a | ε) * B | b | ε = b | ε R0
12= R−1
10( R−1
00) * R−1
02| R−1
12= ∅ ( a | ε) * ∅ | a = a R0
20= R−1
20( R−1
00) * R−1
00| R−1
20= ∅ ( a | ε) * ( a | ε) | ∅ = ∅ R0
21= R−1
20( R−1
00) * R−1
01| R−1
21= ∅ ( a | ε) * B | a | B = a | B R0
22= R−1
20( R−1
00) * R−1
02| R−1
22= ∅ ( a | ε) * ∅ | ε = ε
- Paso 1
R1
00= R0
01( R0
11) * R0
10| R0
00= a * b ( b | ε) * ∅ | un * = a * R1
01= R0
01( R0
11) * R0
11| R0
01= a * b ( b | ε) * ( b | ε) | a * b = a * b * b R1
02= R0
01( R0
11) * R0
12| R0
02= a * b ( b | ε) * a | ∅ = a * b * ba R1
10= R0
11( R0
11) * R0
10| R0
10= ( b | ε) ( b | ε) * ∅ | ∅ = ∅ R1
11= R0
11( R0
11) * R0
11| R0
11= ( b | ε) ( b | ε) * ( b | ε) | b | ε = b * R1
12= R0
11( R0
11) * R0
12| R0
12= ( b | ε) ( b | ε) * a | a = b * a R1
20= R0
21( R0
11) * R0
10| R0
20= ( a | b ) ( b | ε) * ∅ | ∅ = ∅ R1
21= R0
21( R0
11) * R0
11| R0
21= ( a | b ) ( b | ε) * ( b | ε) | a | B = ( a | b ) b * R1
22= R0
21( R0
11) * R0
12| R0
22= ( a | b ) ( b | ε) * a | ε = ( a | b ) b * a | ε
- Paso 2
R2
00= R1
02( R1
22) * R1
20| R1
00= a * b * ba (( a | b ) b * a | ε) * ∅ | un * = a * R2
01= R1
02( R1
22) * R1
21| R1
01= a * b * ba (( a | b ) b * a | ε) * ( a | b ) b * | a * b * b = a * b ( a ( a | b ) | b ) * R2
02= R1
02( R1
22) * R1
22| R1
02= a * b * ba (( a | b ) b * a | ε) * (( a | b ) b * a | ε) | a * b * ba = a * b * b ( a ( a | b ) b * ) * a R2
10= R1
12( R1
22) * R1
20| R1
10= b * a (( a | b ) b * a | ε) * ∅ | ∅ = ∅ R2
11= R1
12( R1
22) * R1
21| R1
11= b * a (( a | b ) b * a | ε) * ( a | b ) b * | b * = ( a ( a | b ) | b ) * R2
12= R1
12( R1
22) * R1
22| R1
12= b * a (( a | b ) b * a | ε) * (( a | b ) b * a | ε) | b * a = ( a ( a | b ) | b ) * a R2
20= R1
22( R1
22) * R1
20| R1
20= (( a | b ) b * a | ε) (( a | b ) b * a | ε) * ∅ | ∅ = ∅ R2
21= R1
22( R1
22) * R1
21| R1
21= (( a | b ) b * a | ε) (( a | b ) b * a | ε) * ( a | b ) b * | ( a | b ) b * = ( a | b ) ( a ( a | b ) | b ) * R2
22= R1
22( R1
22) * R1
22| R1
22= (( a | b ) b * a | ε) (( a | b ) b * a | ε) * (( a | b ) b * a | ε) | ( a | b ) b * a | ε = (( a | b ) b * a ) *
Dado que q 0 es el estado inicial y q 1 es el único estado aceptado, la expresión regular R2
01 denota el conjunto de todas las cadenas aceptadas por el autómata.
Ver también
- Algoritmo de Floyd – Warshall : un algoritmo en gráficos ponderados que puede ser implementado por el algoritmo de Kleene usando un álgebra de Kleene particular.
- Problema de altura de estrella : ¿cuál es la profundidad de anidación de estrellas mínima de todas las expresiones regulares correspondientes a un DFA determinado?
- Problema generalizado de altura de la estrella : si se permite un operador de complemento adicionalmente en las expresiones regulares, ¿se puede limitar la profundidad de anidación de las estrellas de la salida del algoritmo de Kleene a un límite fijo?
- Algoritmo de construcción de Thompson : transforma una expresión regular en un autómata finito
Referencias
- ^ McNaughton, R .; Yamada, H. (marzo de 1960). "Expresiones regulares y gráficos de estado para autómatas". Transacciones IRE en computadoras electrónicas . EC-9 (1): 39–47. doi : 10.1109 / TEC.1960.5221603 . ISSN 0367-9950 .
- ^ a b Jonathan L. Gross y Jay Yellen, ed. (2004). Manual de teoría de grafos . Matemáticas discretas y sus aplicaciones. Prensa CRC. ISBN 1-58488-090-2. Aquí: sección 2.1, observación R13 en la p.65
- ^ Kleene, Stephen C. (1956). "Representación de eventos en redes nerviosas y automatización finita" (PDF) . Automata Studies, Annals of Math. Estudios . Universidad de Princeton Prensa. 34 . Aquí: sección 9, p. 37-40
- ^ John E. Hopcroft, Jeffrey D. Ullman (1979). Introducción a la teoría, los lenguajes y la computación de los autómatas . Addison-Wesley. ISBN 0-201-02988-X. Aquí: Sección 3.2.1 páginas 91-96
- ^ Más precisamente, el número de símbolos de expresión regular, " a i ", "ε", "|", " * ", "·"; sin contar los paréntesis.
- ^ Gruber, Hermann; Holzer, Markus (2008). Aceto, Luca; Damgård, Ivan; Goldberg, Leslie Ann; Halldórsson, Magnús M .; Ingólfsdóttir, Anna; Walukiewicz, Igor (eds.). "Autómatas finitos, conectividad Digraph y tamaño de expresión regular" . Autómatas, lenguajes y programación . Apuntes de conferencias en Ciencias de la Computación. Springer Berlín Heidelberg. 5126 : 39–50. doi : 10.1007 / 978-3-540-70583-3_4 . ISBN 9783540705833.. Teorema 16.