Como converter autômatos finitos em expressões regulares?
On Fevereiro 16, 2021 by adminConverter expressões regulares em NFA (mínimo) que aceitam a mesma linguagem é fácil com algoritmos padrão, por exemplo, Algoritmo de Thompson . A outra direção parece ser mais entediante, porém, e às vezes as expressões resultantes são confusas.
O que algoritmos são existe para converter NFA em expressões regulares equivalentes? Existem vantagens em relação à complexidade do tempo ou ao tamanho do resultado?
Esta é uma questão de referência. Inclua uma descrição geral do seu método, bem como um exemplo não trivial.
Comentários
- Observe uma pergunta semelhante em cstheory.SE , que provavelmente não é adequado para o nosso público.
- todas as respostas usam técnica formal para escrever ER do DFA. Acredito que minha técnica por análise é comparativamente fácil e objetiva, demonstro em minha resposta : Qual é a linguagem deste autômato finito determinístico? Acho que seria útil em algum momento. Sim, claro que às vezes eu mesmo uso o método formal (teorema de Arden) escrever RE é a pergunta é complexa, como mostrado neste exemplo: Como escrever uma expressão regular para um DFA
Resposta
Existem vários métodos para fazer a conversão de autômatos finitos em expressões regulares. Descreverei aqui o que geralmente é ensinado na escola, que é muito visual. Acredito que seja o mais utilizado na prática. No entanto, escrever o algoritmo não é uma ideia tão boa.
Método de remoção de estado
Este algoritmo é sobre como lidar com o gráfico do autômato e, portanto, não é muito adequado para algoritmos, uma vez que precisa primitivos de gráfico, como … remoção de estado. Vou descrevê-lo usando primitivas de nível superior.
A ideia-chave
A ideia é considerar expressões regulares nas bordas e, em seguida, remover estados intermediários, mantendo os rótulos das bordas consistentes.
O padrão principal pode ser visto nas figuras a seguir. O primeiro tem rótulos entre $ p, q, r $ que são expressões regulares $ e, f, g, h, i $ e queremos remover $ q $.
Uma vez removido, nós compomos $ e, f, g, h, i $ juntos (enquanto preservamos as outras arestas entre $ p $ e $ r $ mas isto não é mostrado nisto):
Exemplo
Usando o mesmo exemplo que em Resposta de Raphael :
removemos sucessivamente $ q_2 $:
e depois $ q_3 $:
então ainda temos que aplicar uma estrela na expressão de $ q_1 $ a $ q_1 $. Neste caso, o estado final é também inicial, então só precisamos adicionar uma estrela:
$$ (ab + (b + aa) (ba) ^ * (a + bb)) ^ * $$
Algoritmo
L[i,j]
é o regexp do idioma de $ q_i $ a $ q_j $. Primeiro, removemos todos os mul ti-edge:
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 queremos 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]
Observe que tanto com um lápis de papel quanto com um algoritmo, você deve simplificar expressões como star(ε)=ε
, e.ε=e
, ∅+e=e
, ∅.e=∅
(Por mão você simplesmente não escreve a borda quando não é $ ∅ $, ou mesmo $ ε $ para um loop automático e você ignora quando não há transição entre $ q_i $ e $ q_k $ ou $ q_j $ e $ q_k $)
Agora, como usar remove(k)
? Você não deve remover os estados finais ou iniciais facilmente, 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 $ q_f $ e um estado inicial $ q_s $ então a expressão final é:
e := star(L[s,s]) . L[s,f] . star(L[f,s] . star(L[s,s]) . L[s,f] + L[f,f])
Se você tem vários estados finais (ou mesmo estados iniciais), então não há uma maneira simples de mesclar estes, além de aplicar o método de fechamento transitivo. Normalmente, isso não é um problema manualmente, mas é estranho ao escrever o algoritmo. Uma solução muito mais simples é enumerar todos os pares $ (s, f) $ e executar o algoritmo no gráfico (já removido de estado) para obter todas as expressões $ e_ {s, f} $ supondo que $ s $ seja o único estado inicial e $ f $ é o único estado final, fazendo a união de todos os $ e_ {s, f} $.
Isso, e o fato de que isso está modificando os idiomas mais dinamicamente do que o primeiro método, tornam isso mais sujeito a erros durante a programação. Eu sugiro o uso de qualquer outro método.
Contras
Existem muitos casos neste 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 foi escrito, ele se parece muito com o método de fechamento transitivo.Apenas o contexto de uso é diferente. Não recomendo implementar o algoritmo, mas usar o método para fazer isso manualmente é uma boa ideia.
Comentários
- No exemplo, 2ª imagem, depois de remover o nó ” 2 “, há uma borda ausente – borda do loop (ab) no nó A.
- @Kabamaru: Fixo. Mas agora acho que $ \ varepsilon $ na 3ª imagem também deve ser
ab
, e talvez da mesma forma na expressão regular final. - Você pode fazer o algoritmo trabalhe para qualquer número de estados iniciais e finais adicionando um novo $ q ^ + $ inicial e um novo estado final $ q ^ – $, e conectando-os aos estados inicial e final originais por $ \ varejpsilon $ -edges. Agora remova todos os estados originais. A expressão é então encontrada na única aresta restante de $ q ^ + $ a $ q _- $. A construção não dará loops em $ q ^ + $ ou $ q _- $, pois esses estados não têm resp de entrada. bordas de saída. Ou se você for estrito, eles terão rótulos que representam o conjunto vazio.
- Ainda há um problema com o segundo exemplo: antes da simplificação, o autômato aceita ” ba “, (1, 3, 1) mas após a simplificação não ‘ t.
Resposta
Método
O método mais legal que vi é aquele que expressa o autômato como sistema de equações de linguagens (regulares) que podem ser resolvido. É particularmente interessante, pois parece produzir expressões mais concisas do que outros métodos.
Seja $ A = (Q, \ Sigma, \ delta, q_0, F) $ um NFA sem $ \ varejpsilon $ – transições. Para cada estado $ q_i $, crie a equação
$ \ 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 $ F $ é o conjunto de estados finais e $ q_i \ overset {a} {\ to} q_j $ significa que há uma transição de $ q_i $ para $ q_j $ marcado com $ a $ . Se você ler $ \ cup $ como $ + $ ou $ \ mid $ (dependendo da definição de sua expressão regular), verá que esta é uma equação de expressões regulares.
Para resolver o sistema, você precisa de associatividade e distributividade de $ \ cup $ e $ \ cdot $ (concatenação de string), comutatividade de $ \ cup $ e Lema de Arden ¹:
Seja $ L, U, V \ subseteq \ Sigma ^ * $ línguas regulares com $ \ varepsilon \ notin U $. Então,
$ \ qquad \ displaystyle L = UL \ cup V \ quad \ Longleftrightarrow \ quad L = U ^ * V $
A solução é um conjunto de expressões regulares $ Q_i $, um para cada estado $ q_i $. $ Q_i $ descreve exatamente aquelas palavras que podem ser aceitas por $ A $ quando iniciado em $ q_i $; portanto, $ Q_0 $ (se $ q_0 $ é o estado inicial) é o expressão desejada.
Exemplo
Por motivos de clareza, denotamos os conjuntos de singleton por seu elemento, ou seja, $ a = \ {a \} $. exemplo é devido a Georg Zetzsche.
Considere t seu NFA:
[ fonte ]
O sistema de equação correspondente é:
$ \ qquad \ begin {align} Q_0 & = aQ_1 \ cup bQ_2 \ xícara \ varejpsilon \\ Q_1 & = bQ_0 \ xícara aQ_2 \\ Q_2 & = aQ_0 \ xícara bQ_1 \ end {align} $
Agora insira 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 $ L = Q_1 $, $ U = ab $ e $ V = (b \ cup aa) \ cdot Q_0 $. Observe que todas as três linguagens são regulares e $ \ varepsilon \ notin U = \ {ab \} $, permitindo-nos aplicar o lema. Agora, conectamos este resultado à primeira equação:
$ \ 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 Arden “s Lemma)} \ end {align} $
Assim, encontramos uma expressão regular para a linguagem aceita 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 exclusivamente determinado; resolver o sistema de equações com uma sequência diferente de manipulações leva a outras expressões equivalentes!
- Para uma prova de Arden ” s Lema, veja aqui .
Comentários
- O que é a complexidade de tempo desse algoritmo? Existe um limite para o tamanho da expressão produzida?
- @jmite: Não faço ideia. Eu não ‘ não acho que ‘ d tento implementar isso (outros métodos parecem ser mais viáveis a este respeito), mas uso como um método de caneta e papel.
- Aqui ‘ sa implementação do Prolog deste algoritmo: github.com / wvxvw / intro-to-automata-theory / blob / master / automata / … , mas seu predicado
maybe_union/2
poderia usar mais trabalho (especialmente eliminando prefixo comum) para fazer expressões regulares mais organizadas. Outra maneira de ver esse método é entendê-lo como uma tradução de regex para uma gramática linear direita, onde linguagens com unificação semelhante a Prolog ou correspondência de padrão semelhante a ML são transdutores muito bons, então ‘ não é apenas um algoritmo de caneta e papel 🙂 - Apenas uma pergunta. O ε na primeira equação é porque Qo é um estado inicial ou porque ‘ é um estado final? Aplica-se da mesma forma se eu tiver dois estados finais?
- @PAOK Verifique a definição de $ Q_i $ acima (a linha); é ‘ s porque $ q_0 $ é um estado final.
Resposta
Método algébrico de Brzozowski
Este é o mesmo método descrito na resposta de Rafael , mas a partir de um ponto de visualização de um algoritmo sistemático e, em seguida, de fato, do algoritmo. É fácil e natural implementar, uma vez que você sabe por onde começar. Também pode ser mais fácil manualmente se desenhar todos os autômatos for impraticável por algum motivo. / p>
Ao escrever um algoritmo, você deve se lembrar que as equações devem ser sempre lineares para que você tenha uma boa representação abstrata das equações, coisa que você pode esquecer quando estiver resolvendo manualmente.
A ideia do algoritmo
Não vou descrever como funciona, pois está bem feito na resposta do Rafael que eu sugiro a leitura antes. Em vez disso, concentro-me na ordem em que você deve resolver as equações sem fazer muitos co mputações ou casos extras.
Começando com a solução engenhosa $ X = A ^ * B $ da regra de Arden “para a equação da linguagem $ X = AX∪B $ podemos considerar o autômato como um conjunto de equações da forma:
$$ X_i = B_i + A_ {i, 1} X_1 +… + A_ {i, n} X_n $$
podemos resolver isso por indução em $ n $ atualizando os arrays $ A_ {i, j} $ e $ B_ {i, j} $ de acordo. Na etapa $ n $, temos:
$$ X_n = B_n + A_ {n, 1} X_1 +… + A_ {n, n} X_n $$
e A regra de Arden nos dá:
$$ X_n = A_ {n, n} ^ * (B_n + A_ {n, 1} X_1 +… + A_ {n, n-1} X_ {n -1}) $$
e definindo $ B “_n = A_ {n, n} ^ * B_n $ e $ A” _ {n, i} = A_ {n, n} ^ * A_ {n, i} $ obtemos:
$$ X_n = B “_n + A” _ {n, 1} X_1 +… + A “_ {n, n-1} X_ {n -1} $$
e podemos então remover todas as necessidades de $ X_n $ no sistema definindo, 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} $$
Quando resolvemos $ X_n $ quando $ n = 1 $, obtemos uma equação como esta:
$$ X_1 = B” _1 $$
sem $ A “_ {1, i} $. Assim, obtivemos nossa expressão regular.
O algoritmo
Graças a isso, podemos construir o algoritmo. Para ter a mesma convenção que na indução acima, diremos que o estado inicial é $ q_1 $ e que o número de estados é $ m $. Primeiro, a inicialização para preencher $ B $:
for i = 1 to m: if final(i): B[i] := ε else: B[i] := ∅
e $ 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 muito simbólico para um algoritmo, este é bem adequado para uma implementação. Aqui está uma implementação deste algoritmo em Ocaml (link quebrado) . Observe que, além da função brzozowski
, tudo deve ser impresso ou usado no exemplo de Raphael. Observe que existe uma função surpreendentemente eficiente de simplificação de expressões regulares simple_re
.
Comentários
- O link está morto …
- Implementação em Javascript: github.com/devongovett/regexgen/blob/master/src/regex.js
- Obrigado por esta ótima explicação. Se bem entendi, o seu pseudocódigo de inicialização assume que para dados i e j existe no máximo um a tal que (i, a, j) é uma transição. Isso é correto se concordarmos em rotular esta transição com o regexp que corresponde a todas as letras em Σ esse rótulo faz a transição de i para j no autômato de letras, mas então sua notação a em Σ é um pouco estranha, pois não é realmente uma letra. Se formos letra por letra, podemos ter várias transições de i para j e ter que faça a união de seus rótulos no corpo do loop.
Resposta
Método de fechamento transitivo
Este método é fácil de escrever em um formulário de um algoritmo, mas gera expressões regulares absurdamente grandes e é impraticável se você fizer isso manualmente, principalmente porque isso é muito sistemático. No entanto, é uma solução boa e simples para um algoritmo.
A ideia-chave
Deixe $ R ^ k_ {i, j} $ representar a expressão regular para as strings que vão de $ q_i $ a $ q_j $ usando os estados $ \ {q_1,…, q_k \} $. Seja $ n $ o número de estados do autômato.
Suponha que você já conheça a expressão regular $ R_ {i, j} $ de $ q_i $ a $ q_j $ sem o estado intermediário $ q_k $ (exceto para extremidades), para todos $ i, j $. Então você pode adivinhar como adicionar outro estado afetará a nova expressão regular $ R “_ {i, j} $: ela muda apenas se você tiver transições diretas para $ q_k $, e pode ser expressa assim:
$$ R “_ {i, j} = R_ {i, j} + R_ {i, k}. R_ {k, k} ^ *. R_ {k, j} $$
($ R $ é $ R ^ {k-1} $ e $ R “$ é $ R ^ k $.)
Exemplo
Usaremos o mesmo exemplo da resposta de Raphael . No início, você só pode usar as transições diretas.
Aqui está o primeiro passo (note que um loop self com um rótulo $ a $ teria transformado o primeiro $ ε $ em $ (ε + a) $.
$$ R ^ 0 = \ begin {bmatrix} ε & a & b \\ b & ε & a \\ a & b & ε \ end {bmatrix} $$
Na segunda etapa, podemos usar $ q_0 $ (que é renomeado para $ q_1 $ para nós, porque $ R ^ 0 $ já é usado para o propósito acima). Veremos como $ R ^ 1 $ funciona.
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 $.
Por que isso? É porque ir de $ q_2 $ para $ q_2 $ usando apenas $ q_1 $ como um estado intermediário pode ser feito ficando aqui ($ ε $) ou indo para $ q_1 $ ($ a $), fazendo um loop lá ($ ε ^ * $) e voltando ($ b $).
$$ R ^ 1 = \ begin {bmatrix} ε & a & b \\ b & ε + ba & a + bb \\ a & b + aa & ε + ab \ end {bmatrix} $$
Você pode calcular assim $ R ^ 2 $ e $ R ^ 3 $, também, e $ R ^ 3_ {1,1 } $ fornecerá a expressão final porque $ 1 $ é inicial e final. Observe que muitas simplificações de expressões foram feitas aqui. Caso contrário, o primeiro $ a $ de $ R ^ 0 $ seria $ (∅ + a) $ e o primeiro $ a $ de $ R ^ 1 $ seria $ ((∅ + 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)
Então a expressão final é (supondo que $ q_s $ é o estado inicial):
e := ∅ for i = 1 to n: if final(i): e := e + R[s,i,n]
Mas você pode imaginar ele gera expressões regulares feias. De fato, você pode esperar coisas como $ (∅) ^ * + (a + (∅) ^ *) (ε) ^ * (a + ∅) $ que representa o mesmo idioma que $ aa $. Observe que simplificar uma expressão regular é útil na prática.
Deixe uma resposta