dfa algorithms

algorithmes-dfa

https://dfa.laane.xyz/

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

Projet de fin d'année 6CCS3PRJ pour King's College de Londres
Auteur : Sten Arthur Laane
Superviseur : Dr Agi Kurucz

À propos

Ce projet vise à implémenter et visualiser trois algorithmes d'automates finis utilisés pour la minimisation d'état (SM) et les tests d'équivalence (ET) :

• L'algorithme de remplissage de table (SM, ET)
• L'algorithme n lg n Hopcroft (SM, ET)
• L'algorithme (presque) linéaire (ET)

Des variantes de ces algorithmes qui produisent des chaînes témoins pour indiquer si deux DFA sont équivalents sont également implémentées.

De plus, le projet vise à démontrer les performances des algorithmes dans le pire des cas à l'aide d'ensembles de données DFA personnalisés. Ces ensembles de données sont mis à disposition des utilisateurs pour créer leurs propres DFA.

De plus amples détails sur les algorithmes et les ensembles de données peuvent être trouvés dans le rapport accompagnant le projet, disponible ici.

Les instructions d'utilisation de l'application sont disponibles sur la page d'aide.

Développement

Pour exécuter ou développer ce logiciel localement, une installation locale de node.js 14.x est requise.

Le logiciel peut être exécuté comme suit :

1. Accédez au répertoire du projet
2. Installez les dépendances nécessaires à l'aide de npm install
3. Exécutez le serveur de développement local npm run start
4. Accédez au site à http://localhost:3000

Les tests peuvent être exécutés à l'aide de npm run test

Contribution et problèmes

Les contributions sont toujours les bienvenues. Tout le monde peut ouvrir des tickets et tirer des requêtes sur GitHub

Licence

Ce projet est sous licence MIT