¿Cómo convertir autómatas finitos a expresiones regulares?

115

Convertir expresiones regulares en NFA (mínimo) que acepten el mismo lenguaje es fácil con algoritmos estándar, por ejemplo, el algoritmo de Thompson . Sin embargo, la otra dirección parece ser más tediosa, y a veces las expresiones resultantes son desordenadas.

¿Qué algoritmos existen 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. Incluya una descripción general de su método, así como un ejemplo no trivial.

Rafael
fuente
2
Tenga en cuenta una pregunta similar en cstheory.SE que probablemente no sea adecuada para nuestra audiencia.
Raphael
todas las respuestas usan una técnica formal para escribir RE desde DFA. Creo que mi técnica de análisis es comparativamente fácil y objetiva. Demuestro en mi respuesta: ¿Cuál es el lenguaje de este autómata finito determinista? Siento que sería útil alguna vez. Sí, por supuesto, en algún momento yo mismo uso el método formal (teorema de Arden) para escribir RE. Esta pregunta es compleja, como se da en este ejemplo: Cómo escribir expresiones regulares para un DFA
Grijesh Chauhan

Respuestas:

94

Existen varios métodos para realizar la conversión de autómatas finitos a expresiones regulares. Aquí describiré el que generalmente se enseña en la escuela y que es muy visual. Creo que es el más usado en la práctica. Sin embargo, escribir el algoritmo no es una buena idea.

Método de eliminación del estado

Este algoritmo se trata de manejar el gráfico del autómata y, por lo tanto, no es muy adecuado para los algoritmos, ya que necesita primitivas de gráficos como ... la eliminación del estado. Lo describiré usando primitivas de nivel superior.

La idea clave

La idea es considerar expresiones regulares en los bordes y luego eliminar estados intermedios mientras se mantienen las etiquetas de los bordes consistentes.

El patrón principal se puede ver a continuación en las figuras. El primero tiene etiquetas entre que son expresiones regulares e , f , g , h , i y queremos eliminar q .p,q,re,f,g,h,iq

autómata pqr

Una vez eliminados, componimos juntos (conservando los otros bordes entre p y r, pero esto no se muestra en esto):e,f,g,h,ipr

ingrese la descripción de la imagen aquí

Ejemplo

Usando el mismo ejemplo que en la respuesta de Raphael :

1-2-3 autómata

eliminamos sucesivamente :q2

1-3 autómata

y luego :q3

1 autómata

entonces todavía tenemos que aplicar una estrella en la expresión de a q 1 . En este caso, el estado final también es inicial, por lo que realmente solo necesitamos agregar una estrella:q1q1

(ab+(b+aa)(ba)(a+bb))

Algoritmo

L[i,j]es la expresión regular del lenguaje de a q j . Primero, eliminamos todos los bordes múltiples:qiqj

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 :qk

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]

star(ε)=εe.ε=e∅+e=e∅.e=∅q i q k q j q kεqiqkqjqk

Ahora, ¿cómo usarlo remove(k)? No debe eliminar a la ligera los estados finales o iniciales, de lo contrario, perderá partes del lenguaje.

for i = 1 to n:
  if not(final(i)) and not(initial(i)):
    remove(i)

Si solo tiene un estado final y un estado inicial , la expresión final es:q sqfqs

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 simple de fusionarlos, aparte 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 mucho más simple es enumerar todos los pares y ejecutar el algoritmo en el gráfico (ya eliminado) para obtener todas las expresiones suponiendo que es el único estado inicial es el único final estado, luego haciendo la unión de todos .e s , f s f e s , f(s,f)es,fsfes,f

Esto, y el hecho de que esto está modificando los lenguajes más dinámicamente que el primer método lo hace 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 también puede ser inicial, etc.

Tenga en cuenta que ahora que el algoritmo está escrito, esto 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.

jmad
fuente
1
En el ejemplo, segunda imagen, después de eliminar el nodo "2", falta un borde - borde del bucle (ab) en el nodo A.
Panos Kal.
@Kabamaru: Corregido. Pero ahora creo que el en la tercera imagen también debería ser , y de manera similar tal vez en la expresión regular final. εab
Lógica errante
Puede hacer que el algoritmo funcione para cualquier número de estados iniciales y finales agregando un nuevo inicial y un nuevo estado final , y conectándolos a los estados iniciales y finales originales mediante -edges. Ahora elimine todos los estados originales. Luego, la expresión se encuentra en el borde único restante de a . La construcción no dará bucles en o ya que estos estados no tienen respuesta entrante. bordes salientes O si eres estricto, tendrán etiquetas que representan el conjunto vacío. q - ε q + q - q + q -q+qεq+qq+q
Hendrik Jan
1
Todavía hay un problema con el segundo ejemplo: antes de la simplificación, el autómata acepta "ba", (1, 3, 1) pero después de la simplificación no lo hace.
wvxvw
50

Método

El mejor método que he visto es uno que expresa el autómata como sistema de ecuaciones de lenguajes (regulares) que se pueden resolver. Es particularmente agradable, ya que parece producir expresiones más concisas que otros métodos.

Deje un NFA sin -transitions. Para cada estado , crea la ecuaciónε q iA=(Q,Σ,δ,q0,F)εqi

Qi=qiaqjaQj{{ε}, qiF, else

donde es el conjunto de estados finales y significa que hay una transición de a etiquetada con . Si lee como o (dependiendo de su definición de expresión regular), verá que esta es una ecuación de expresiones regulares.Fqiaqjqiqja+

Para resolver el sistema necesita asociatividad y distributividad de y (concatenación de cadenas), conmutatividad de y Lema de Arden ¹:

Let lenguajes regulares con . Entonces,L,U,VΣεU

L=ULVL=UV

La solución es un conjunto de expresiones regulares , una para cada estado . describe exactamente esas palabras que pueden ser aceptadas por cuando se inicia en ; por lo tanto, (si es el estado inicial) es la expresión deseada.QiqiQiAqiQ0q0


Ejemplo

En aras de la claridad, denotamos conjuntos singleton por su elemento, es decir, . El ejemplo se debe a Georg Zetzsche.a={a}

Considere este NFA:

ejemplo nfa
[ fuente ]

El sistema de ecuaciones correspondiente es:

Q0=aQ1bQ2εQ1=bQ0aQ2Q2=aQ0bQ1

Ahora conecta la tercera ecuación en la segunda:

Q1=bQ0a(aQ0bQ1)=abQ1(baa)Q0=(ab)(baa)Q0

Para el último paso, aplicamos el Lema de Arden con , y . Tenga en cuenta que los tres idiomas son regulares y , lo que nos permite aplicar el lema. Ahora conectamos este resultado en la primera ecuación:L=Q1U=abV=(baa)Q0εU={ab}

Q0=a(ab)(baa)Q0baQ0bb(ab)(baa)Q0ε=((abb)(ab)(baa)ba)Q0ε=((abb)(ab)(baa)ba)(by Arden's Lemma)

Por lo tanto, hemos encontrado una expresión regular para el lenguaje aceptado por el autómata anterior, a saber

((a+bb)(ab)(b+aa)+ba).

Tenga en cuenta que es bastante sucinto (compárese con el resultado de otros métodos) pero no está determinado de forma exclusiva; resolver el sistema de ecuaciones con una secuencia diferente de manipulaciones conduce a otro - ¡equivalente! - expresiones.


  1. Para una prueba del Lema de Arden, vea aquí .
Rafael
fuente
1
¿Cuál es la complejidad temporal de este algoritmo? ¿Hay un límite en el tamaño de la expresión producida?
jmite
@ jmite: no tengo idea. No creo que intente implementar esto (otros métodos parecen ser más factibles a este respecto), pero lo uso como un método de lápiz y papel.
Raphael
1
Aquí hay una implementación de Prolog de este algoritmo: github.com/wvxvw/intro-to-automata-theory/blob/master/automata/… pero su maybe_union/2predicado 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 la expresión regular a la gramática lineal derecha, donde los lenguajes con unificación similar a Prolog o coincidencia de patrones similares a ML hacen un muy buen transductor, por lo que no es solo un bolígrafo y papel algoritmo :)
wvxvw
Solo una pregunta. La ε en la primera ecuación es porque Qo es un estado inicial o porque es un estado final. De la misma manera si tengo dos estados finales se aplica?
Georgio3
@PAOK Verifique la definición de arriba (la línea); es porque es un estado final. Qiq0
Raphael
28

Método algebraico de Brzozowski

Este es el mismo método que el descrito en la respuesta de Raphael , pero desde el punto de vista de un algoritmo sistemático, y luego, de hecho, el algoritmo. Resulta fácil y natural de implementar una vez que sabes por dónde empezar. También puede ser más fácil a mano si dibujar algún autómata no es práctico por alguna razón.

Al escribir un algoritmo, debe recordar que las ecuaciones deben ser siempre lineales para que tenga una buena representación abstracta de las ecuaciones, algo que puede olvidar cuando resuelve 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 que debe resolver las ecuaciones sin hacer demasiados cálculos adicionales o casos adicionales.

A partir de la ingeniosa solución de la regla de Arden a la ecuación del lenguaje , podemos considerar el autómata como un conjunto de ecuaciones de la forma:X=ABX=AXB

Xi=Bi+Ai,1X1++Ai,nXn

podemos resolver esto por inducción en actualizando las matrices y consecuencia. En el paso , tenemos:nAi,jBi,jn

Xn=Bn+An,1X1++An,nXn

y la regla de Arden nos da:

Xn=An,n(Bn+An,1X1++An,n1Xn1)

y configurando y obtenemos:Bn=An,nBnAn,i=An,nAn,i

Xn=Bn+An,1X1++An,n1Xn1

y luego podemos eliminar todas las necesidades de en el sistema configurando, para :Xni,j<n

Bi=Bi+Ai,nBn
Ai,j=Ai,j+Ai,nAn,j

Cuando hemos resuelto cuando , obtenemos una ecuación como esta:Xnn=1

X1=B1

sin . Así obtuvimos nuestra expresión regular.A1,i

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 y que el número de estado es . Primero, la inicialización para llenar :q1mB

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 resolució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 parece un sistema de ecuaciones que parece demasiado simbólico para un algoritmo, este es 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 imprimir o usar para el ejemplo de Raphael. Tenga en cuenta que existe una función sorprendentemente eficiente de simplificación de expresiones regulares simple_re.

jmad
fuente
44
Link está muerto ...
Columbo
Implementación en Javascript: github.com/devongovett/regexgen/blob/master/src/regex.js
cakraww
24

Método de cierre transitivo

Este método es fácil de escribir en forma de algoritmo, pero genera expresiones regulares absurdamente grandes y no es práctico si lo hace a mano, principalmente porque esto es demasiado sistemático. Sin embargo, es una solución buena y simple para un algoritmo.

La idea clave

Deje que represente la expresión regular para las cadenas que van de a usando los estados . Sea el número de estados del autómata.Ri,jkqiqj{q1,,qk}n

Suponga que ya conoce la expresión regular de a sin el estado intermedio (excepto las extremidades), para todo . Entonces puede adivinar cómo agregar otro estado afectará la nueva expresión regular : solo cambia si tiene transiciones directas a , y se puede expresar así:Ri,jqiqjqki,jRi,jqk

Ri,j=Ri,j+Ri,k.Rk,k.Rk,j

( es y es .)RRk1RRk

Ejemplo

Usaremos el mismo ejemplo que en la respuesta de Raphael . Al principio, solo puedes usar las transiciones directas.

Aquí está el primer paso (tenga en cuenta que un bucle automático con una etiqueta habría transformado el primer en .aε(ε+a)

R0=[εabbεaabε]

En el segundo paso podemos usar (que se renombra en para nosotros, porque ya se usa para el propósito anterior). Veremos cómo funciona .q0q1R0R1

De a : .q2q2R2,21=R2,20+R2,10R1,10R1,20=ε+bεa=ε+ba

¿Porqué es eso? Esto se debe a que pasar de a usando solo como estado intermedio puede realizarse permaneciendo aquí ( ) o yendo a ( ), girando allí ( ) y volviendo ( ).q2q2q1εq1aεb

R1=[εabbε+baa+bbab+aaε+ab]

También puede calcular así y , y le dará la expresión final porque es inicial y final. Tenga en cuenta que aquí se ha hecho mucha simplificación de expresiones. De lo contrario, la primera de sería y la primera de sería .R2R3R1,131aR0(+a)aR1((+a)+ε(ε)a)

Algoritmo

Inicializacion:

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

Clausura transitiva:

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 es el estado inicial):qs

e := ∅
for i = 1 to n:
  if final(i):
    e := e + R[s,i,n]

Pero puedes imaginar que genera expresiones regulares feas. De hecho, puede esperar cosas como que representa el mismo lenguaje que . Tenga en cuenta que simplificar una expresión regular es útil en la práctica.a a()+(a+())(ε)(a+)aa

jmad
fuente