Algoritmo de Brzozowski para minimização do DFA

15

O algoritmo de minimização do DFA de Brzozowski cria um DFA mínimo para o DFA :G

  1. reverter todas as arestas em , tornando o estado inicial um estado de aceitação e os estados de aceitação iniciais, para obter um NFA N para o idioma reverso,GN
  2. usando construção de conjunto de potências para obter para o idioma reverso,G
  3. inverter as bordas (e troca de aceitação inicial) em para obter um NFA N para o idioma original, eGN
  4. fazendo construção de conjunto de potências para obter .Gmin

Obviamente, como alguns DFAs têm um DFA reverso grande exponencial, esse algoritmo é executado no tempo exponencial, na pior das hipóteses, em termos do tamanho da entrada, portanto, vamos acompanhar o tamanho do DFA reverso.

Se é o tamanho do DFA de entrada, n é o tamanho do DFA mínimo e m o tamanho do DFA reverso mínimo, qual é o tempo de execução do algoritmo de Brzozowski em termos de N , n e m ?NnmNnm

Em particular, sob que relação entre e m o algoritmo de Brzozowski supera os algoritmos de Hopcroft ou Moore?nm

Ouvi dizer que em exemplos típicos na prática / aplicação , o algoritmo de Brzozowski supera os outros. Informalmente, como são esses exemplos típicos?

Artem Kaznatcheev
fonte
seria útil se você incluísse as estimativas O (f (n)) desses algoritmos. eles são todos O (n log (n)) no caso "médio"? Nesse caso, o debate sobre seu desempenho relativo pode ser principalmente um teste aplicado, dependendo das características estatísticas / estrutura da entrada ... parece provável que Brzozowski corra rapidamente quando a NFA inversa é "não grande" ...?
vzn
Tenha cuidado com a execução do algoritmo, pois você poderá tentar introduzir um estado de início virtual ao executar 1. e 3., o que levará a resultados incorretos - veja aqui . (Não é errado na pergunta, você só tem que ter cuidado para não errar.)
A.Schulz

Respostas:

5

Aqui está uma resposta parcial sobre sua terceira pergunta. De fato, talvez o algoritmo de Brzozowski realmente não supere todos os outros algoritmos com tanta clareza na minimização do DFA.

Em [1], os autores investigam o desempenho prático dos algoritmos de minimização de DFA / NFA. Os algoritmos são de Hopcroft, Brzozowski e duas variantes do Watson. Eles concluem que não há um vencedor claro, mas o algoritmo de Hopcroft tem um desempenho melhor para DFAs com pequenos alfabetos. Para as NFAs, Brzozowski é claramente o mais rápido.

O artigo em si é bastante curto e claramente escrito. Há também discussões e referências adicionais que podem ser úteis.


[1] Almeida M., Moreira N. e Reis R. Sobre o desempenho de algoritmos de minimização de autômatos, Quarta Conferência sobre Computabilidade na Europa, junho de 2008.

Juho
fonte
Obrigado, vou dar uma olhada no artigo e ver se consigo usar as referências para encontrar uma resposta completa.
Artem Kaznatcheev
5

A maioria dos itens abaixo é de Parsing Theory itens de Sippu e Soisalon-Soininen.

Seja o conjunto de estados do DFA. Seja T o alfabeto de entrada. Let | M | = O ( | T || Q | ) é o tamanho da máquina. O Exercício 3.40 fornece um algoritmo O ( | T || Q | 2 ) para minimização de estado. Como a Wikipedia descreve , o algoritmo de Hopcroft tem um tempo de execução de O ( | T || Q |logQT|M|=O(|T||Q|)O(|T||Q|2) e o algoritmo de Moore tem um tempo de execução de O ( | T | 2| Q | ) .O(|T||Q|log|T|)O(|T|2|Q|)

O teorema 3.30 afirma que a construção do subconjunto pode ser feita em produzindo um autômato do tamanho O ( 2 | T | + log | Q | ) (na verdade, se o autômato resultante tem | T | estados, o tempo de execução é ( | T | + | T || MO(2|T|+log|T|+log|Q|)O(2|T|+log|Q|)|T|(|T|+|T||M|)|Q|) As duas reversões e a segunda determinação são, portanto, irrelevantes no tempo de execução; portanto, o tempo de execução assintótico do algoritmo de Brzozowski é o mesmo da construção do subconjunto.

Isso significa que, na pior das hipóteses, o algoritmo de Brzozowski é exponencialmente mais lento que os outros três algoritmos. Observe que o pior caso realmente ocorre: o exemplo clássico da NFA para o idioma tem k + 1 estados e seu DFA mínimo correspondente tem O ( 2 k ) , enquanto o inverso da NFA é determinístico, portanto, executar o algoritmo de Brzozowski nesse NFA invertido aciona o pior comportamento possível.(a|b)akk+1O(2k)

No entanto, se a construção do subconjunto gerar um autômato de tamanho , então o tempo de execução também é O ( | T | 2| Q | 2 ) , o que geralmente ocorre nas entradas da vida real. Além disso, se o cuidado adequado for tomado ao calcular o fechamento de um estado, isso poderá ser feito muito mais rapidamente na maioria dos casos (ou seja, nos casos em que o fechamento é pequeno), economizando um fator | T ||T|=O(|T|)O(|T|2|Q|2)|T|na prática (pelo mesmo motivo pelo qual os fechamentos transitivos podem ser calculados rapidamente em exemplos do mundo real). Além disso, se os autômatos de entrada e intermediários são esparsos, o que significa que os estados têm poucas transições, então um fator é salvo, o que fornece um tempo de execução O ( | T || Q | ) em entradas 'boas'.|Q|O(|T||Q|)

Infelizmente, não estou familiarizado o suficiente com os algoritmos de Hopcroft ou Moore para fornecer uma análise de seus tempos de execução em casos típicos. A Wikipedia fala sobre um tempo de execução em alguns casos, o que tornaria os três algoritmos comparáveis.O(|T|loglog|T|)

Alex ten Brink
fonte
1

De Felice e Nicaud mostram que os algoritmos de Brzozowski são assintoticamente hiper-polinomiais. David mostrou que, para várias distribuições nos estados finais, o algoritmo de Hopcroft é mais lento que o algoritmo de Moore.

Referências

S. De Felice e C. Nicaud, "O algoritmo de Brzozowski é genericamente super polinomial para autômatos determinísticos". Em Anais da 17ª Conferência Internacional sobre Desenvolvimentos em Teoria da Linguagem (DLT 2013) , Notas de Aula em Ciência da Computação, pp. 170–190, 2013. ( PDF )

J. David, "Complexidade média dos algoritmos de Moore e Hopcroft". Ciência da Computação Teórica , 417: 50–65, 2012. ( Science Direct )

nevro
fonte