Skip to content

Final Year Project at King's College London

License

Notifications You must be signed in to change notification settings

StenAL/dfa-algorithms

Repository files navigation

dfa-algorithms

https://dfa.laane.xyz/

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

6CCS3PRJ Final Year Project for King's College London
Author: Sten Arthur Laane
Supervisor: Dr Agi Kurucz

About

This project aims to implement and visualize three Finite Automata algorithms used for state minimization (SM) and equivalence testing ( ET):

  • The Table-Filling Algorithm (SM, ET)
  • The n lg n Hopcroft Algorithm (SM, ET)
  • The (Nearly) Linear Algorithm (ET)

Variants of these algorithms that produce witness strings to indicate whether two DFA are equivalent are also implemented.

Additionally, the project aims to demonstrate the algorithms' worst-case performance using custom DFA datasets. These datasets are made available to users for creating their own DFAs.

Further details on the algorithms and datasets can be found in the report accompanying the project, found here.

Instructions on using the app can be found on the help page.

Development

To run or develop this software locally, a local installation of node.js 14.x is required.

The software can be run as follows:

  1. Navigate to the project directory
  2. Install necessary dependencies using npm install
  3. Run the local development server npm run start
  4. Access the site at http://localhost:3000

Tests can be run using npm run test

Contributing and Issues

Contributions are always welcome. Anyone can open issues and pull requests on GitHub

License

This project is licensed under the MIT license

About

Final Year Project at King's College London

Resources

License

Stars

Watchers

Forks