dfa algorithms

algoritmos dfa

https://dfa.laane.xyz/

 Finite State Machine Educational Tools: Implementing Equivalence Testing and State Minimization Algorithms

Projeto de último ano 6CCS3PRJ para King's College London
Autor: Sten Arthur Laane
Supervisor: Dr. Agi Kurucz

Sobre

Este projeto tem como objetivo implementar e visualizar três algoritmos de Autômatos Finitos utilizados para minimização de estados (SM) e testes de equivalência (ET):

• O Algoritmo de Preenchimento de Tabela (SM, ET)
• O algoritmo n lg n Hopcroft (SM, ET)
• O Algoritmo (Quase) Linear (ET)

Também são implementadas variantes desses algoritmos que produzem strings testemunhas para indicar se dois AFD são equivalentes.

Além disso, o projeto visa demonstrar o pior desempenho dos algoritmos usando conjuntos de dados DFA personalizados. Esses conjuntos de dados são disponibilizados aos usuários para a criação de seus próprios DFAs.

Mais detalhes sobre os algoritmos e conjuntos de dados podem ser encontrados no relatório que acompanha o projeto, encontrado aqui.

Instruções sobre como usar o aplicativo podem ser encontradas na página de ajuda.

Desenvolvimento

Para executar ou desenvolver este software localmente, é necessária uma instalação local do node.js 14.x.

O software pode ser executado da seguinte forma:

1. Navegue até o diretório do projeto
2. Instale as dependências necessárias usando npm install
3. Execute o servidor de desenvolvimento local npm run start
4. Acesse o site em http://localhost:3000

Os testes podem ser executados usando npm run test

Contribuições e problemas

Contribuições são sempre bem-vindas. Qualquer pessoa pode abrir problemas e receber solicitações no GitHub

Licença

Este projeto está licenciado sob a licença MIT