¿Cómo convertir autómatas finitos en expresiones regulares?
On febrero 16, 2021 by adminConvertir expresiones regulares en NFA (mínimo) que aceptan el mismo idioma es fácil con algoritmos estándar, p. ej. Algoritmo de Thompson . Sin embargo, la otra dirección parece ser más tediosa y, a veces, las expresiones resultantes son confusas.
Qué algoritmos son ¿Existe para convertir NFA en expresiones regulares equivalentes? ¿Hay ventajas con respecto a la complejidad del tiempo o el tamaño del resultado?
Se supone que esta es una pregunta de referencia. Por favor, incluya una descripción general de su método, así como una ejemplo no trivial.
Comentarios
- Note una pregunta similar en cstheory.SE que probablemente no sea adecuado para nuestra audiencia.
- Todas las respuestas utilizan una técnica formal para escribir RE de DFA. Creo que mi técnica de análisis es comparativamente fácil y objetiva, lo demuestro en mi respuesta : ¿Cuál es el lenguaje de este autómata finito determinista? Creo que sería útil en algún momento. Sí, por supuesto que en algún momento yo mismo uso el método formal (teorema de Arden) escribir RE es La pregunta es compleja como la que se muestra en este ejemplo: Cómo escribir una expresión regular para un DFA
Respuesta
Existen varios métodos para realizar la conversión de autómatas finitos a expresiones regulares. Aquí describiré el que se suele enseñar en la escuela, que es muy visual. Creo que es el más utilizado en la práctica. Sin embargo, escribir el algoritmo no es una buena idea.
Método de eliminación de estados
Este algoritmo trata sobre el manejo del gráfico del autómata y, por lo tanto, no es muy adecuado para algoritmos, ya que necesita gráficos primitivos como … eliminación de estado. Lo describiré usando primitivas de nivel superior.
La idea clave
La idea es considerar expresiones regulares en los bordes y luego eliminar los estados intermedios mientras se mantienen las etiquetas de los bordes consistentes.
El patrón principal se puede ver en las siguientes figuras. El primero tiene etiquetas entre $ p, q, r $ que son expresiones regulares $ e, f, g, h, i $ y queremos eliminar $ q $.
Una vez eliminado, componimos $ e, f, g, h, i $ juntos (conservando los otros bordes entre $ p $ y $ r $ pero esto no se muestra sobre esto):
Ejemplo
Usando el mismo ejemplo que en Respuesta de Raphael :
eliminamos sucesivamente $ q_2 $:
y luego $ q_3 $:
entonces todavía tenemos que aplicar una estrella en la expresión de $ q_1 $ a $ q_1 $. En este caso, el estado final es también inicial, así que realmente solo necesitamos agregar una estrella:
$$ (ab + (b + aa) (ba) ^ * (a + bb)) ^ * $$
Algoritmo
L[i,j]
es la expresión regular del idioma desde $ q_i $ a $ q_j $. Primero, eliminamos todas las mul ti-bordes:
for i = 1 to n: for j = 1 to n: if i == j then: L[i,j] := ε else: L[i,j] := ∅ for a in Σ: if trans(i, a, j): L[i,j] := L[i,j] + a
Ahora, la eliminación del estado. Supongamos que queremos eliminar el estado $ q_k $:
remove(k): for i = 1 to n: for j = 1 to n: L[i,i] += L[i,k] . star(L[k,k]) . L[k,i] L[j,j] += L[j,k] . star(L[k,k]) . L[k,j] L[i,j] += L[i,k] . star(L[k,k]) . L[k,j] L[j,i] += L[j,k] . star(L[k,k]) . L[k,i]
Tenga en cuenta que tanto con un lápiz de papel como con un algoritmo debe simplificar expresiones como star(ε)=ε
, e.ε=e
, ∅+e=e
, ∅.e=∅
(por mano, simplemente no escribe el borde cuando no es $ ∅ $, o incluso $ ε $ para un bucle automático y lo ignora cuando no hay transición entre $ q_i $ y $ q_k $ o $ q_j $ y $ q_k $)
Ahora, ¿cómo usar remove(k)
? No debe eliminar los estados finales o iniciales a la ligera, de lo contrario, perderá partes del idioma.
for i = 1 to n: if not(final(i)) and not(initial(i)): remove(i)
Si solo tiene un estado final $ q_f $ y uno estado inicial $ q_s $ entonces la expresión final es:
e := star(L[s,s]) . L[s,f] . star(L[f,s] . star(L[s,s]) . L[s,f] + L[f,f])
Si tiene varios estados finales (o incluso estados iniciales), entonces no hay una forma sencilla de fusionar estos, además de aplicar el método de cierre transitivo. Por lo general, esto no es un problema a mano, pero es incómodo al escribir el algoritmo. Una solución alternativa mucho más simple es enumerar todos los pares $ (s, f) $ y ejecutar el algoritmo en el gráfico (ya eliminado) para obtener todas las expresiones $ e_ {s, f} $ suponiendo que $ s $ es el único estado inicial y $ f $ es el único estado final, luego hacer la unión de todos $ e_ {s, f} $.
Esto, y el hecho de que esto está modificando lenguajes más dinámicamente que el primer método lo hacen más propenso a errores al programar. Sugiero usar cualquier otro método.
Contras
Hay muchos casos en este algoritmo, por ejemplo, para elegir qué nodo debemos eliminar, el número de estados finales al final , el hecho de que un estado final puede ser inicial, también, etc.
Tenga en cuenta que ahora que el algoritmo está escrito, se parece mucho al método de cierre transitivo.Solo el contexto del uso es diferente. No recomiendo implementar el algoritmo, pero usar el método para hacerlo a mano es una buena idea.
Comentarios
- En el ejemplo, segunda imagen, después de eliminar el nodo » 2 «, falta un borde – borde del bucle (ab) en el nodo A.
- @Kabamaru: arreglado. Pero ahora creo que $ \ varepsilon $ en la tercera imagen también debería ser
ab
, y tal vez de manera similar en la expresión regular final. - Puede hacer que el algoritmo trabajar para cualquier número de estados inicial y final agregando un nuevo $ q ^ + $ inicial y un nuevo estado final $ q ^ – $, y conectándolos a los estados inicial y final originales mediante $ \ varepsilon $ -edges. Ahora elimine todos los estados originales. Luego, la expresión se encuentra en el único borde restante desde $ q ^ + $ a $ q _- $. La construcción no dará bucles en $ q ^ + $ o $ q _- $ ya que estos estados no tienen resp. bordes salientes. O si eres estricto, tendrán etiquetas que representan el conjunto vacío.
- Todavía hay un problema con el segundo ejemplo: antes de la simplificación, los autómatas aceptan » ba «, (1, 3, 1) pero después de la simplificación no ‘ t.
Respuesta
Método
El método más bonito que he visto es uno que expresa el autómata como sistema de ecuaciones de lenguajes (regulares) que pueden estar solucionado. Es particularmente agradable ya que parece producir expresiones más concisas que otros métodos.
Sea $ A = (Q, \ Sigma, \ delta, q_0, F) $ un NFA sin $ \ varepsilon $ – transiciones. Para cada estado $ q_i $, crea la ecuación
$ \ qquad \ displaystyle Q_i = \ bigcup \ limits_ {q_i \ overset {a} {\ to} q_j} aQ_j \ cup \ begin {cases} \ {\ varepsilon \} &, \ q_i \ in F \\ \ emptyset &, \ text {else} \ end {cases} $
donde $ F $ es el conjunto de estados finales y $ q_i \ overset {a} {\ to} q_j $ significa que hay una transición de $ q_i $ a $ q_j $ etiquetada con $ a $ . Si lee $ \ cup $ como $ + $ o $ \ mid $ (según la definición de su expresión regular), verá que esta es una ecuación de expresiones regulares.
Para resolver el sistema, necesita asociatividad y distributividad de $ \ cup $ y $ \ cdot $ (concatenación de cadenas), conmutatividad de $ \ cup $ y Lema de Arden ¹:
Sea $ L, U, V \ subseteq \ Sigma ^ * $ lenguajes regulares con $ \ varepsilon \ notin U $. Luego,
$ \ qquad \ displaystyle L = UL \ cup V \ quad \ Longleftrightarrow \ quad L = U ^ * V $
La solución es un conjunto de expresiones regulares $ Q_i $, uno para cada estado $ q_i $. $ Q_i $ describe exactamente aquellas palabras que pueden ser aceptadas por $ A $ cuando comienzan en $ q_i $; por lo tanto $ Q_0 $ (si $ q_0 $ es el estado inicial) expresión deseada.
Ejemplo
En aras de la claridad, denotamos conjuntos singleton por su elemento, es decir, $ a = \ {a \} $. ejemplo se debe a Georg Zetzsche.
Considere t su NFA:
[ fuente ]
El sistema de ecuaciones correspondiente es:
$ \ qquad \ begin {align} Q_0 & = aQ_1 \ cup bQ_2 \ taza \ varepsilon \\ Q_1 & = bQ_0 \ cup aQ_2 \\ Q_2 & = aQ_0 \ cup bQ_1 \ end {align} $
Ahora inserta la tercera ecuación en la segunda:
$ \ qquad \ begin {align} Q_1 & = bQ_0 \ cup a (aQ_0 \ cup bQ_1) \\ & = abQ_1 \ cup (b \ cup aa) Q_0 \\ & = (ab) ^ * ( b \ cup aa) Q_0 \ end {align} $
Para el último paso, aplicamos el Lema de Arden con $ L = Q_1 $, $ U = ab $ y $ V = (b \ cup aa) \ cdot Q_0 $. Tenga en cuenta que los tres idiomas son regulares y $ \ varepsilon \ notin U = \ {ab \} $, lo que nos permite aplicar el lema. Ahora conectamos este resultado a la primera ecuación:
$ \ qquad \ begin {align} Q_0 & = a (ab) ^ * (b \ cup aa ) Q_0 \ cup baQ_0 \ cup bb (ab) ^ * (b \ cup aa) Q_0 \ cup \ varepsilon \\ & = ((a \ cup bb) (ab) ^ * (b \ cup aa) \ cup ba) Q_0 \ cup \ varepsilon \\ & = ((a \ cup bb) (ab) ^ * (b \ cup aa) \ cup ba) ^ * \ qquad \ text {(por el lema de Arden)} \ end {align} $
Por lo tanto, hemos encontrado una expresión regular para el lenguaje aceptado por el autómata anterior, a saber
$ \ qquad \ displaystyle ((a + bb) (ab) ^ * (b + aa) + ba) ^ *. $
Tenga en cuenta que es bastante conciso (compárese con el resultado de otros métodos) pero no determinado de forma única; resolver el sistema de ecuaciones con una secuencia diferente de manipulaciones conduce a otras – ¡equivalentes! – expresiones.
- Para una prueba de Arden » s Lema, consulte aquí .
Comentarios
- ¿Qué Cuál es la complejidad temporal de este algoritmo? ¿Existe un límite en el tamaño de la expresión producida?
- @jmite: No tengo ni idea. No ‘ no creo que ‘ intente implementar esto (otros métodos parecen ser más factibles en este sentido) pero lo uso como un método de lápiz y papel.
- Aquí ‘ una implementación de Prolog de este algoritmo: github.com / wvxvw / intro-to-automata-theory / blob / master / automata / … pero su
maybe_union/2
predicado podría usar más trabajo (especialmente wrt eliminando el prefijo común) para hacer expresiones regulares más ordenadas. Otra forma de ver este método es entenderlo como una traducción de expresiones regulares a gramática lineal a la derecha, donde los lenguajes con unificación similar a Prolog o coincidencia de patrones similar a ML son muy buenos transductores, por lo que ‘ no es solo un algoritmo de lápiz y papel 🙂 - Solo una pregunta. La ε en la primera ecuación se debe a que Qo es un estado inicial o porque ‘ es un estado final. ¿Se aplica la misma forma si tengo dos estados finales?
- @PAOK Verifique la definición de $ Q_i $ arriba (la línea); es ‘ s porque $ q_0 $ es un estado final.
Respuesta
Método algebraico de Brzozowski
Este es el mismo método que el descrito en respuesta de Raphael , pero desde un punto de vista de un algoritmo sistemático, y luego, de hecho, el algoritmo. Resulta fácil y natural de implementar una vez que se sabe por dónde empezar. También puede ser más fácil a mano si dibujar todos los autómatas no es práctico por alguna razón.
Al escribir un algoritmo tienes que recordar que las ecuaciones deben ser siempre lineales para que tengas una buena representación abstracta de las ecuaciones, cosa que puedes olvidar cuando estás resolviendo a mano.
La idea del algoritmo
No describiré cómo funciona, ya que está bien hecho en la respuesta de Raphael , que sugiero leer antes. En cambio, me concentro en el orden en el que debes resolver las ecuaciones sin hacer demasiados ejercicios adicionales. mputaciones o casos adicionales.
A partir de la ingeniosa solución de la Arden «s rule » $ X = A ^ * B $ a la ecuación del lenguaje $ X = AX∪B $ podemos considerar el autómata como un conjunto de ecuaciones de la forma:
$$ X_i = B_i + A_ {i, 1} X_1 +… + A_ {i, n} X_n $$
Podemos resolver esto por inducción en $ n $ actualizando las matrices $ A_ {i, j} $ y $ B_ {i, j} $ en consecuencia. En el paso $ n $, tenemos:
$$ X_n = B_n + A_ {n, 1} X_1 +… + A_ {n, n} X_n $$
y La regla de Arden nos da:
$$ X_n = A_ {n, n} ^ * (B_n + A_ {n, 1} X_1 +… + A_ {n, n-1} X_ {n -1}) $$
y configurando $ B «_n = A_ {n, n} ^ * B_n $ y $ A» _ {n, i} = A_ {n, n} ^ * A_ {n, i} $ obtenemos:
$$ X_n = B «_n + A» _ {n, 1} X_1 +… + A «_ {n, n-1} X_ {n -1} $$
y luego podemos eliminar todas las necesidades de $ X_n $ en el sistema configurando, para $ i, j < n $:
$$ B «_i = B_i + A_ {i, n} B» _n $$ $$ A «_ {i, j} = A_ {i, j} + A_ {i, n} A «_ {n, j} $$
Cuando hayamos resuelto $ X_n $ cuando $ n = 1 $, obtenemos una ecuación como esta:
$$ X_1 = B» _1 $$
sin $ A «_ {1, i} $. Así obtuvimos nuestra expresión regular.
El algoritmo
Gracias a esto, podemos construir el algoritmo. Para tener la misma convención que en la inducción anterior, diremos que el estado inicial es $ q_1 $ y que el número de estados es $ m $. Primero, la inicialización para llenar $ B $:
for i = 1 to m: if final(i): B[i] := ε else: B[i] := ∅
y $ A $:
for i = 1 to m: for j = 1 to m: for a in Σ: if trans(i, a, j): A[i,j] := a else: A[i,j] := ∅
y luego la solución:
for n = m decreasing to 1: B[n] := star(A[n,n]) . B[n] for j = 1 to n: A[n,j] := star(A[n,n]) . A[n,j]; for i = 1 to n: B[i] += A[i,n] . B[n] for j = 1 to n: A[i,j] += A[i,n] . A[n,j]
la expresión final es entonces:
e := B[1]
Implementación
Incluso si puede parecer un sistema de ecuaciones que parece demasiado simbólico para un algoritmo, este es muy adecuado para una implementación. Aquí hay una implementación de este algoritmo en Ocaml (enlace roto) . Tenga en cuenta que, aparte de la función brzozowski
, todo es para imprimir o para usar en el ejemplo de Raphael. Tenga en cuenta que hay una función sorprendentemente eficiente de simplificación de expresiones regulares simple_re
.
Comentarios
- Enlace muerto …
- Implementación en Javascript: github.com/devongovett/regexgen/blob/master/src/regex.js
- Gracias por esta gran explicación. Si he entendido bien, su pseudocódigo de inicialización asume que para iyj dados hay como máximo uno tal que (i, a, j) es una transición. Esto es correcto si aceptamos etiquetar esta transición con la expresión regular que coincide con todas las letras en Σ esa etiqueta cambia de i a j en el autómata de letras, pero entonces tu notación a en Σ es un poco extraña ya que no es realmente una letra. Si vamos letra por letra, podemos tener varias transiciones de i a j y tenemos que hacen la unión de sus etiquetas en el cuerpo del bucle.
Respuesta
Método de cierre transitivo
Este método es fácil de escribir en un formulario de un algoritmo, pero genera expresiones regulares absurdamente grandes y no es práctico si lo hace a mano, principalmente porque es demasiado sistemático. Sin embargo, es una solución buena y simple para un algoritmo.
La idea clave
Deje que $ R ^ k_ {i, j} $ represente la expresión regular para las cadenas que van desde $ q_i $ a $ q_j $ usando los estados $ \ {q_1,…, q_k \} $. Sea $ n $ el número de estados del autómata.
Suponga que ya conoce la expresión regular $ R_ {i, j} $ de $ q_i $ a $ q_j $ sin el estado intermedio $ q_k $ (excepto las extremidades), para todos los $ i, j $. Luego, puede adivinar cómo la adición de otro estado afectará a la nueva expresión regular $ R «_ {i, j} $: cambia solo si tiene transiciones directas a $ q_k $, y se puede expresar así:
$$ R «_ {i, j} = R_ {i, j} + R_ {i, k}. R_ {k, k} ^ *. R_ {k, j} $$
($ R $ es $ R ^ {k-1} $ y $ R «$ es $ R ^ k $.)
Ejemplo
Usaremos el mismo ejemplo que en la respuesta de Raphael . Al principio, solo puede usar las transiciones directas.
Este es el primer paso (tenga en cuenta que un ciclo propio con una etiqueta $ a $ habría transformado el primer $ ε $ en $ (ε + a) $.
$$ R ^ 0 = \ begin {bmatrix} ε & a & b \\ b & ε & a \\ a & b & ε \ end {bmatrix} $$
En el segundo paso podemos usar $ q_0 $ (que se renombra a $ q_1 $ para nosotros, porque $ R ^ 0 $ ya se usa para el propósito anterior). Veremos cómo funciona $ R ^ 1 $.
De $ q_2 $ a $ q_2 $: $ R ^ 1_ {2,2} = R ^ 0_ {2,2} + R ^ 0_ {2,1} {R ^ 0_ {1,1}} ^ * R ^ 0_ {1,2} = ε + b ε ^ * a = ε + ba $.
Esto se debe a que se puede pasar de $ q_2 $ a $ q_2 $ usando solo $ q_1 $ como estado intermedio permaneciendo aquí ($ ε $) o yendo a $ q_1 $ ($ a $), haciendo un bucle allí ($ ε ^ * $) y regresando ($ b $).
$$ R ^ 1 = \ begin {bmatrix} ε & a & b \\ b & ε + ba & a + bb \\ a & b + aa & ε + ab \ end {bmatrix} $$
También puedes calcular $ R ^ 2 $ y $ R ^ 3 $, y $ R ^ 3_ {1,1 } $ le dará la expresión final porque $ 1 $ es tanto inicial como final. Tenga en cuenta que aquí se ha simplificado mucho las expresiones. De lo contrario, el primer $ a $ de $ R ^ 0 $ sería $ (∅ + a) $ y el primer $ a $ de $ R ^ 1 $ sería $ ((∅ + a) + ε (ε) ^ * a ) $.
Algoritmo
Inicialización:
for i = 1 to n: for j = 1 to n: if i == j: R[i,j,0] := ε else: R[i,j,0] := ∅ for a in Σ: if trans(i, a, j): R[i,j,0] := R[i,j,0] + a
Cierre transitivo:
for k = 1 to n: for i = 1 to n: for j = 1 to n: R[i,j,k] := R[i,j,k-1] + R[i,k,k-1] . star(R[k,k,k-1]) . R(k,j,k-1)
Entonces la expresión final es (suponiendo que $ q_s $ es el estado inicial):
e := ∅ for i = 1 to n: if final(i): e := e + R[s,i,n]
Pero puedes imaginar genera expresiones regulares feas. De hecho, puede esperar cosas como $ (∅) ^ * + (a + (∅) ^ *) (ε) ^ * (a + ∅) $ que representa el mismo idioma que $ aa $. Tenga en cuenta que simplificar una expresión regular es útil en la práctica.
Deja una respuesta