Algoritmo de Brzozowski de minimização do DFA
https://stackoverflow.com/questions/5893690
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Estou tentando implementar o algoritmo de Brzozowski para minimizar o meu DFA a seguir, o algoritmo para o mesmo.
DFA = d(r(d(r(NFA))))
onde r() é a reversão do NFA e D() converte NFA em DFA.
Mas eu não entendo qual é o significado de r() pesquisar no google também não dá muita informação.
Alguém pode explicar o que é r() da NFA.
Qualquer outro algoritmo simples ou implementação C++ disponível, informe-me o link.
Solução
No código para reverse.c (encontrado aqui, mas agora extinto) você encontrará um comentário /* Create reversed edges */.Então eu diria isso r() é inverter a direção de todas as arestas (além de garantir que o autômato invertido tenha um estado inicial bem definido).
Outras dicas
Esse é a implementação do OpenFst.
Em esse O artigo contém um diagrama (página 15) que mostra os resultados da aplicação da operação inversa.
Uma maneira mais fácil de ajudar a entender as operações do FSM é usar uma biblioteca como OpenFst para criar e manipular as máquinas e depois visualizar os resultados usando o Graphviz.
