dfa algorithms

DFA-Algorithmen

https://dfa.laane.xyz/

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

6CCS3PRJ Abschlussprojekt für das King's College London
Autor: Sten Arthur Laane
Betreuer: Dr. Agi Kurucz

Um

Dieses Projekt zielt darauf ab, drei endliche Automaten-Algorithmen zu implementieren und zu visualisieren, die für Zustandsminimierung (SM) und Äquivalenztests (ET) verwendet werden:

• Der Tabellenfüllalgorithmus (SM, ET)
• Der n-lg-n-Hopcroft-Algorithmus (SM, ET)
• Der (fast) lineare Algorithmus (ET)

Es werden auch Varianten dieser Algorithmen implementiert, die Zeugenzeichenfolgen erzeugen, um anzuzeigen, ob zwei DFA gleichwertig sind.

Darüber hinaus zielt das Projekt darauf ab, die Worst-Case-Leistung der Algorithmen mithilfe benutzerdefinierter DFA-Datensätze zu demonstrieren. Diese Datensätze werden den Benutzern zur Erstellung ihrer eigenen DFAs zur Verfügung gestellt.

Weitere Details zu den Algorithmen und Datensätzen finden Sie im projektbegleitenden Bericht, den Sie hier finden.

Hinweise zur Nutzung der App finden Sie auf der Hilfeseite.

Entwicklung

Um diese Software lokal auszuführen oder zu entwickeln, ist eine lokale Installation von node.js 14.x erforderlich.

Die Software kann wie folgt ausgeführt werden:

1. Navigieren Sie zum Projektverzeichnis
2. Installieren Sie die erforderlichen Abhängigkeiten mit npm install
3. Führen Sie den lokalen Entwicklungsserver npm run start aus
4. Greifen Sie auf die Website unter http://localhost:3000 zu

Tests können mit npm run test ausgeführt werden

Beiträge und Probleme

Beiträge sind jederzeit willkommen. Jeder kann Issues öffnen und Anfragen auf GitHub stellen

Lizenz

Dieses Projekt ist unter der MIT-Lizenz lizenziert