Algoritmos conhecidos para passar de um DFA para uma expressão regular

28

Eu queria saber se existe um algoritmo `` melhor '' (explicarei em que sentido) iniciar a partir de um DFA e construir uma expressão regular tal que , do que o livro de Hopcroft e Ullman (1979). Lá, os conjuntos são usados ​​para representar conjuntos de seqüências de caracteres que levam o DFA do estado para sem passar por nenhum estado numerado maior que . Essa construção, embora obviamente correta e muito útil, é bastante técnica.ArL(A)=L(r)Rijkqiqjk

Estou escrevendo uma monografia sobre a teoria dos autômatos algébricos e não quero distrair meu público com muitos detalhes técnicos (pelo menos não com detalhes irrelevantes para os resultados que quero mostrar), mas quero incluir um prova da equivalência entre DFA e expressões regulares por uma questão de integridade. Para constar, estou usando o autômato Glushkov para passar de uma expressão regular para um DFA. Parecia mais intuitivo do que as -transitions, que eu não defini (de novo, porque não preciso delas).ε

Quais outros algoritmos são conhecidos para ir de um DFA para uma expressão regular? Eu valorizo ​​a simplicidade em vez da eficiência (isso é `` melhor '' para mim neste caso), mas isso não é um requisito.

Agradeço antecipadamente por sua ajuda!

Janoma
fonte
1
Não é um algoritmo diferente, mas o algoritmo pode ser expressa algebricamente, usando o k th poder de uma matriz de expressões regulares na álgebra apropriado. Talvez você ache isso mais elegante / conciso. Estou procurando uma referência. REujkk
Max
1
A algoritmo é essencialmente uma variante do algoritmo de Floyd-Warshall para o problema Todos os pares-caminho mais curto, então você pode encontrar a apresentação em termos de multiplicação de matrizes procurando por essas palavras-chave. REujk
Jan Johannsen
2
Eu concordo. É basicamente o algoritmo de Floyd-Warshall. Também pode ser derivado usando técnicas de programação dinâmica padrão (assim como Floyd-Warshall).
David #
Tenho certeza de que respondi a uma pergunta como essa antes, mas não consigo encontrá-la.
Raphael
@ Max você poderia encontrar uma referência? Estou interessado na representação matricial, na verdade deve ser mais atraente para os algebristas.
Janoma

Respostas:

17

Mais duas construções: Brzozowski-McCluskey, também conhecido como eliminação de estado [1] e eliminação gaussiana em um sistema de equações usando o Lemma de Arden. A melhor fonte para isso é provavelmente o livro de Jacques Sakarovitch [2].

[1] J. Brzozowski, E. McCluskey Jr., Técnicas de gráfico de fluxo de sinais para diagramas de estados de circuitos seqüenciais, IEEE Transactions on Electronic Computers EC-12 (1963) 67–76.

[2] J. Sakarovitch, Elementos da Teoria dos Autômatos. Cambridge University Press, 2009.

Sylvain
fonte
2
Acho que a abordagem para resolver equações usando o Lema de Arden é a mais simples e fácil de explicar, é por isso que a apresento dessa maneira em uma aula de teoria introdutória.
Jan Johannsen
O método de um sistema de equações parece brilhante. Infelizmente, a biblioteca da minha universidade não tem o livro que você mencionou (Sakarovitch), mas vou procurar em outro lugar.
Janoma
4
A comparação de construções também é encontrada no artigo de Sakarovitch "A linguagem, a expressão e o (pequeno) autômato", CIAA 2005, LNCS 3845, Springer (2006) 15-30. Veja infres.enst.fr/~jsaka/PUB/Files/LESA.pdf
Hermann Gruber
2
Além disso, observe que a ordem na qual os estados são processados ​​pode afetar bastante o tamanho da expressão regular resultante. Isso sempre é verdadeiro: se você faz o lema de Arden, McNaughton-Yamada, eliminação do estado ou outra variante. Estão disponíveis várias heurísticas simples para a escolha de um bom pedido de eliminação.
Hermann Gruber
15

O livro de Kozen "Automata & Computability" menciona uma generalização elegante desse algoritmo de Floyd-Warshall. Desde que você mencionou o recurso a algebraists, você pode achar útil. Você o encontrará nas páginas 58-59 desse texto. (Acho que o Google Livros tem uma visualização.)

Basicamente, você pode definir uma álgebra de Kleene em matrizes cujas entradas são de uma álgebra de Kleene. A adição / união de matrizes é uma adição coordenada. A multiplicação / concatenação de matrizes é como a multiplicação regular de matrizes. Kleene estrela para matrizes é definida como:2×2

[abcd]=[(a+bdc)(a+bdc)bd(d+cab)ca(d+cab)]

Você pode ver que, se a matriz esquerda é a matriz de transição de um DFA de 2 estados, a entrada da matriz direita descreve o conjunto de caminhos (de qualquer comprimento) do estado i ao estado j .i,jij

Então Kleene estrela de matrizes maiores é definida recursivamente: dividir o matriz em 4 quadrantes / submatrizes um , b , c , d , de dimensões m × m , m × ( n - m ) , ( n - m ) × m , e ( n - m ) × ( n - m ) e aplique o 2 × 2n×na,b,c,dm×mm×(nm)(nm)×m(nm)×(nm)2×2regra acima agora com os menores de matriz em vez das entradas "escalares". (De forma análoga a como a multiplicação de matriz regular pode ser definida recursivamente com base na regra para ).2×2

Então, se você tem um NFA -state e correspondente a sua matriz de transição T . Então uma expressão regular equivalente é f F ( T ) s , f , onde s é o estado inicial. T pode ser avaliado recursivamente usando a definição acima.nTfF(T)s,fsT

Kozen afirma que o caso em que você avalia a estrela da matriz recursivamente usando corresponde ao algoritmo R k i j .m=1Rijk

Outra derivação das estruturas da álgebra de Kleene sobre as matrizes aparece no Teorema da completude para álgebras de Kleene e na Álgebra de eventos regulares de Kozen.

mikero
fonte
12

De longe, o melhor procedimento que já vi é o mencionado por Sylvain. Em particular, parece produzir expressões mais concisas do que outras.

Eu escrevi este documento explicando o método para os alunos no verão passado. Está diretamente relacionado a uma palestra específica; a referência mencionada é uma definição típica de expressões regulares. Uma prova do lema de Arden está contida; está faltando um para correção do método. Como soube disso na palestra, infelizmente não tenho uma referência.

Rafael
fonte
Eu também prefiro essa prova. Acho elegante e fácil de explicar. Mesmo o lema de Arden não é difícil. Penso que este será o método que incluirei no meu documento.
Janoma
@Raphael Saw the example in cs.stackexchange and found that there is some difference between the notations. You have used both + and in document, but you have used only in the above document. I think both meant the same thing. For the consistency of notation you could consider changing that. Anyway that document saved my day :). Thanks for writing documents like this and releasing under open license.
user3162