Converter expressões regulares em NFA (mínimo) que aceitam o mesmo idioma é fácil com algoritmos padrão, por exemplo, o algoritmo de Thompson . A outra direção parece ser mais entediante e, às vezes, as expressões resultantes são confusas.

Quais algoritmos existem para converter NFA em expressões regulares equivalentes? Existem vantagens em relação à complexidade do tempo ou tamanho do resultado?

^{Esta deveria ser uma pergunta de referência. Inclua uma descrição geral do seu método, bem como um exemplo não trivial.}

Existem vários métodos para fazer a conversão de autômatos finitos em expressões regulares. Aqui vou descrever o que normalmente é ensinado na escola, que é muito visual. Eu acredito que é o mais usado na prática. No entanto, escrever o algoritmo não é uma boa idéia.

Método de remoção de estado

Esse algoritmo trata do manuseio do gráfico do autômato e, portanto, não é muito adequado para algoritmos, pois ele precisa de primitivas do gráfico, como ... remoção de estado. Vou descrevê-lo usando primitivas de nível superior.

A ideia chave

A idéia é considerar expressões regulares nas arestas e remover estados intermediários, mantendo os rótulos das arestas consistentes.

O padrão principal pode ser visto a seguir nas figuras. O primeiro possui rótulos entre que são expressões regulares queremos remover .e , f , g , h , i $p,q,r$$e,f,g,h,i$$q$

Uma vez removidos, compomos juntos (enquanto preservamos as outras arestas entre e mas isso não é exibido aqui):p $e,f,g,h,i$$p$$r$

Exemplo

Usando o mesmo exemplo da resposta de Raphael :

removemos sucessivamente :$q_2$

e depois :$q_3$

ainda precisamos aplicar uma estrela na expressão de a . Nesse caso, o estado final também é inicial; portanto, precisamos apenas adicionar uma estrela:q $q_1$$q_1$

Algoritmo

L[i,j]é a regexp do idioma de a . Primeiro, removemos todas as arestas múltiplas:q $q_i$$q_j$

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

Agora, a remoção do estado. Suponha que desejemos remover o 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]

Note-se que ambos com um lápis de papel e com um algoritmo que você deve simplificar expressões como star(ε)=ε, e.ε=e, ∅+e=e, ∅.e=∅(por mão você simplesmente não escrever a borda quando não está , ou mesmo para uma auto-loop e você ignorar quando há nenhuma transição entre e ou e )$∅$q i q k q j q $ε$$q_i$$q_k$$q_j$$q_k$

Agora, como usar remove(k)? Você não deve remover os estados finais ou iniciais de ânimo leve, caso contrário, perderá partes do idioma.

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

Se você tiver apenas um estado final e um estado inicial , a expressão final será:q $q_f$$q_s$

e := star(L[s,s]) . L[s,f] . star(L[f,s] . star(L[s,s]) . L[s,f] + L[f,f])

Se você possui vários estados finais (ou mesmo estados iniciais), não há uma maneira simples de mesclar esses, além de aplicar o método de fechamento transitivo. Normalmente, este não é um problema manual, mas é complicado ao escrever o algoritmo. Uma solução muito mais simples é enumerar todos os pares e executar o algoritmo no gráfico (já removido pelo estado) para obter todas as expressões supondo que é o único estado inicial é o único final estado, fazendo a união de todos os .e s , f s f e s , $(s,f)$$e_{s,f}$$s$$f$$e_{s,f}$

Isso e o fato de modificar linguagens de maneira mais dinâmica que o primeiro método tornam mais propenso a erros na programação. Eu sugiro usar qualquer outro método.

Contras

Existem muitos casos nesse algoritmo, por exemplo, para escolher qual nó devemos remover, o número de estados finais no final, o fato de que um estado final também pode ser inicial etc.

Observe que agora que o algoritmo está escrito, é muito parecido com o método de fechamento transitivo. Somente o contexto do uso é diferente. Não recomendo implementar o algoritmo, mas usar o método para fazer isso manualmente é uma boa idéia.

Método

O método mais legal que eu já vi é o que expressa o autômato como sistema de equações de linguagens (regulares) que podem ser resolvidas. É particularmente agradável, pois parece produzir expressões mais concisas do que outros métodos.

Seja um NFA sem varepsilon. Para cada estado , crie a equação$A= (Q,\Sigma,\delta,q_0,F)$$\varepsilon$$q_i$

$\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}$

onde é o conjunto de estados finais e significa que há uma transição de para rotulado com . Se você ler como ou (dependendo da sua definição de expressão regular), verá que essa é uma equação de expressões regulares.$F$$q_i \overset{a}{\to} q_j$$q_i$$q_j$$a$$\cup$$+$$\mid$

Para resolver o sistema, você precisa de associatividade e distributividade de e (concatenação de cordas), comutatividade de e Lemma de Arden ¹:$\cup$$\cdot$$\cup$

Deixe- linguagens regulares com . Então,$L,U,V \subseteq \Sigma^*$$\varepsilon \notin U$

$\qquad \displaystyle L = UL \cup V \quad \Longleftrightarrow \quad L = U^*V$

A solução é um conjunto de expressões regulares , uma para cada estado . descreve exatamente aquelas palavras que podem ser aceitas por quando iniciadas em ; portanto, (se for o estado inicial) é a expressão desejada.$Q_i$$q_i$$Q_i$$A$$q_i$$Q_0$$q_0$

Exemplo

^{Por uma questão de clareza, denotamos conjuntos de singleton por seu elemento, ou seja, . O exemplo é devido a Georg Zetzsche.$a = \{a\}$}

Considere este NFA:

^{[ fonte ]}

O sistema de equações correspondente é:

$\qquad \begin{align} Q_0 &= aQ_1 \cup bQ_2 \cup \varepsilon \\ Q_1 &= bQ_0 \cup aQ_2 \\ Q_2 &= aQ_0 \cup bQ_1 \end{align}$

Agora conecte a terceira equação na 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 a última etapa, aplicamos o lema de Arden com , e . Observe que todos os três idiomas são regulares e , permitindo aplicar o lema. Agora, conectamos esse resultado à primeira equação:$L = Q_1$$U = ab$$V = (b \cup aa) \cdot Q_0$$\varepsilon \notin U = \{ab\}$

$\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{(by Arden's Lemma)} \end{align}$

Assim, encontramos uma expressão regular para o idioma aceito pelo autômato acima, a saber

$\qquad \displaystyle ((a + bb)(ab)^*(b + aa) + ba)^*.$

Observe que é bastante sucinto (compare com o resultado de outros métodos), mas não é determinado exclusivamente; resolver o sistema de equações com uma sequência diferente de manipulações leva a outro equivalente! -- expressões.

1. Para uma prova do Lema de Arden, veja aqui .

Método algébrico de Brzozowski

Esse é o mesmo método descrito na resposta de Raphael , mas do ponto de vista de um algoritmo sistemático e, de fato, do algoritmo. É fácil e natural de implementar depois que você sabe por onde começar. Também pode ser mais fácil à mão se desenhar todos os autômatos for impraticável por algum motivo.

Ao escrever um algoritmo, lembre-se de que as equações devem ser sempre lineares para que você tenha uma boa representação abstrata das equações, algo que você pode esquecer quando estiver resolvendo manualmente.

A ideia do algoritmo

Não vou descrever como funciona, pois é bem feito na resposta de Raphael, que sugiro ler antes. Em vez disso, concentro-me em qual ordem você deve resolver as equações sem fazer muitos cálculos ou casos extras.

$X=A^*B$$X=AX∪B$

$n$$A_{i,j}$$B_{i,j}$$n$

e o governo de Arden nos dá:

$B'_n = A_{n,n}^* B_n$$A'_{n,i}=A_{n,n}^*A_{n,i}$

$X_n$$i,j<n$

$X_n$$n=1$

$A'_{1,i}$

O algoritmo

$q_1$$m$$B$

for i = 1 to m:
  if final(i):
    B[i] := ε
  else:
    B[i] := ∅

$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] := ∅

e então a solução:

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]

a expressão final é então:

e := B[1]

Implementação

Mesmo que pareça um sistema de equações que pareça simbólico demais para um algoritmo, este é adequado para uma implementação. Aqui está uma implementação desse algoritmo no Ocaml (link quebrado) . Observe que, além da função brzozowski, tudo é para imprimir ou usar no exemplo de Raphael. Observe que há uma função surpreendentemente eficiente de simplificação de expressões regulares simple_re.

Método de fechamento transitivo

Esse método é fácil de escrever na forma de um algoritmo, mas gera expressões regulares absurdamente grandes e é impraticável se você o fizer manualmente, principalmente porque isso é sistemático demais. É uma solução boa e simples para um algoritmo.

A ideia chave

$R^k_{i,j}$$q_i$$q_j$$\{q_1, …, q_k\}$$n$

$R_{i,j}$$q_i$$q_j$$q_k$$i,j$$R'_{i,j}$$q_k$

$R$$R^{k-1}$$R'$$R^k$

Exemplo

Usaremos o mesmo exemplo da resposta de Rafael . No início, você pode usar apenas as transições diretas.

$a$$ε$$(ε+a)$

$q_0$$q_1$$R^0$$R^1$

$q_2$$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$

$q_2$$q_2$$q_1$$ε$$q_1$$a$$ε^*$$b$

$R^2$$R^3$$R^3_{1,1}$$1$$a$$R^0$$(∅+a)$$a$$R^1$$((∅+a)+ε(ε)^*a)$

Algoritmo

Inicialização:

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

Fechamento 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)

$q_s$

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

$(∅)^*+(a+(∅)^*)(ε)^*(a + ∅)$$aa$