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.
Observe uma pergunta semelhante em cstheory.SE, que provavelmente não é adequada para o nosso público.
todas as respostas usam a técnica formal para escrever RE do DFA. Acredito que minha técnica de análise é comparativamente fácil e objetiva que demonstro em minha resposta: Qual é a linguagem desse autômato finito determinístico? Eu acho que seria útil algum dia. Sim, de curso em algum momento eu me usa método formal (Arden teorema) para escrever RE é questão é complexa como dada neste exemplo: Como escrever expressão regular para uma DFA
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 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 qp , q, rp,q,re , f, g, H , ie,f,g,h,iqq
Uma vez removidos, compomos juntos (enquanto preservamos as outras arestas entre e mas isso não é exibido aqui):p re , f, g, H , ie,f,g,h,ipprr
Usando o mesmo exemplo da resposta de Raphael :
removemos sucessivamente :q2q2
e depois :q3q3
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 1q1q1q1q1
( a b + ( b + a a ) ( b a )∗( a + b b ) )∗(ab+(b+aa)(ba)∗(a+bb))∗
L[i,j]é a regexp do idioma de a . Primeiro, removemos todas as arestas múltiplas:q jqEuqiqjqj
Agora, a remoção do estado. Suponha que desejemos remover o estado :qkqk
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 kεεqEuqiqkqkqjqjqkqk
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.
Se você tiver apenas um estado final e um estado inicial , a expressão final será:q sqfqfqsqs
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 , f( s , f)(s,f)es , fes,fssffes , fes,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.
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.
No exemplo, 2ª imagem, após a remoção do nó "2", há uma borda ausente - borda do loop (ab) no nó A.
@Kabamaru: Fixed. Mas agora acho que o na 3ª imagem também deveria estar , e da mesma forma talvez na expressão regular final. εεab
Você pode fazer o algoritmo funcionar para qualquer número de estados inicial e final adicionando um novo inicial e um novo estado final e conectando-os aos estados inicial e final originais por -edges. Agora remova todos os estados originais. A expressão é então encontrada na única borda restante de a . A construção não dará loops em ou pois esses estados não têm resp. bordas de saída. Ou, se você for rigoroso, eles terão rótulos representando o conjunto vazio. q - ε q + q - q + q -q+q+q-q−εεq+q+q-q−q+q+q-q−
Ainda existe um problema com o segundo exemplo: antes da simplificação, os autômatos aceitam "ba", (1, 3, 1), mas após a simplificação, não.
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çãoA=(Q,Σ,δ,q0,F)A=(Q,Σ,δ,q0,F)εεqiqi
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.FFqi→aqjqi→aqjqiqiqjqjaa∪∪++∣∣
Para resolver o sistema, você precisa de associatividade e distributividade de e (concatenação de cordas), comutatividade de e Lemma de Arden ¹:∪∪⋅⋅∪∪
Deixe- linguagens regulares com . Então,L,U,V⊆Σ∗L,U,V⊆Σ∗ε∉Uε∉U
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.QiQiqiqiQiQiAAqiqiQ0Q0q0q0
Por uma questão de clareza, denotamos conjuntos de singleton por seu elemento, ou seja, . O exemplo é devido a Georg Zetzsche.a={a}a={a}
Considere este NFA:
O sistema de equações correspondente é:
Agora conecte a terceira equação na segunda:
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=Q1L=Q1U=abU=abV=(b∪aa)⋅Q0V=(b∪aa)⋅Q0ε∉U={ab}ε∉U={ab}
e então a solução:
a expressão final é entã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.
Implementação em Javascript: github.com/devongovett/regexgen/blob/master/src/regex.js
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.