dfa algorithms

dfa-алгоритмы

https://dfa.laane.xyz/

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

6CCS3PRJ Проект выпускного года Королевского колледжа Лондона
Автор: Стен Артур Лаане
Руководитель: д-р Аги Куруц

О

Целью этого проекта является реализация и визуализация трех алгоритмов конечных автоматов, используемых для минимизации состояния (SM) и тестирования эквивалентности (ET):

• Алгоритм заполнения таблиц (SM, ET)
• Алгоритм Хопкрофта n lg n (SM, ET)
• (Почти) линейный алгоритм (ET)

Также реализованы варианты этих алгоритмов, которые создают строки-свидетели, чтобы указать, эквивалентны ли два DFA.

Кроме того, цель проекта — продемонстрировать производительность алгоритмов в наихудшем случае с использованием пользовательских наборов данных DFA. Эти наборы данных доступны пользователям для создания собственных DFA.

Более подробную информацию об алгоритмах и наборах данных можно найти в отчете, сопровождающем проект, по ссылке.

Инструкции по использованию приложения можно найти на странице помощи.

Разработка

Для локального запуска или разработки этого программного обеспечения требуется локальная установка node.js 14.x.

Программное обеспечение можно запустить следующим образом:

1. Перейдите в каталог проекта
2. Установите необходимые зависимости с помощью npm install
3. Запустите локальный сервер разработки npm run start
4. Доступ к сайту по адресу http://localhost:3000

Тесты можно запускать с помощью npm run test

Вклад и проблемы

Взносы всегда приветствуются. Любой может открывать задачи и запросы на извлечение на GitHub.

Лицензия

Этот проект лицензируется по лицензии MIT.