NFA/DFA Python Implementation NFA->DFA algorithm Implementation
- Переход по символу -1 это eps-переход
- Чтобы добавить тесты добавьте описание автомата в папку dfa_nfa_tests/automats, а затем файл с таким же названием в папку dfa_nfa_tests/strings, при этом в последнем на каждой строке пишется 1 тест: <слово>, true/false (тут слово это последовательность чисел из алфавита)
- Чтобы запустить мои тесты следует запустить файл main.py
- Реализация проверки слова автоматом сделана по принципу BFS, потому проверка заканчивается, когда в очереди не остается элементов вида (состояние, буква, был ли последний переход по eps)
- Бесконечные eps-преходы происходить не будут, так как пред началом проверки для каждого состояния находятся все состояния, в которые можно попасть некоторой последовательностью eps-переходов (например, если есть eps-переход из 0 в 1, из 1 в 2 и из 1 в 0, но нет из 0 в 2 (то есть он не задан в файле), то преобработка покажет, что из 0 можно попасть в 1 или 2, а из 1 в 2 или 0 eps-переходами). А уже в самом алгоритме проверки 2 eps-преехода подряд не делаются (то есть для примера выше после состояния 0 в очередь добавятся состояния 1 и 2, однако без возможности сделать eps-перход из них следующим шагом). Эта проверка гарантирует, что мы как минимум каждый второй шаг будем двигать головку вправо, а не делать eps-переход и исключает зачикливание eps-переходов
- Также добавлена мемоизация посещенных троек (состояние, буква, был ли последний переход по eps), это убирает повторяющиеся ветки из проверки и ускоряет работу
- Преобразование NFA к DFA реализовано по алгоритму из лекции.
- Тесты проверяют, что полученный DFA корректно работает на тествоых строчках для исходного NFA. Для тестирования используются те же директории что и для первого задания .
Их тесты также запускаются через main