Closed TonitaN closed 1 year ago
Но перед релизом лучше это не трогать. Когда-нибудь потом.
Ну пока что Томпсон будет эквивалентен Глушкову (как я мог сразу это не заметить) Буду думать, как считать пути с пустыми переходами.
Так, у нас тут набирается на ещё одну конференцию материала, похоже 🤣 @xendalm , прошу вас, не надо сейчас исправлять Ambiguity, можем в последний момент сломать то, что уже работает (или сделать багов там, где их не заметим).
Хахаха, добрались и до Ambiguity. Ещё остался небольшой баг - не учитывается неоднозначность при распознавании пустого слова, но в целом похоже, проблема эпсилонов дождалась своего часа. И всё оказалось на удивление логично и не заняло много времени, с той же идеей матрицы смежности (с добавленной матрицей смежности по эпсилон-переходам, но с учётом числа комбинаций по эпсилон-переходам). Вот что значит была хорошая основа...
В общем, всё ещё веселее, чем я думала.
Существует два "теоретических" алгоритма удаления эпсилон-правил. С переходом к эпсилон-замыканиям в качестве состояний и без таковых! И в каждой статье по теории автоматов подразумевается какой-то конкретный из них, причём не всегда говорится, какой именно. Поскольку у нас уже есть две реализации, предлагаю расширить возможности интерпретатора и сделать две соответствующие команды. Это должно быть несложно, с учётом модульности.
(вопрос о том, как это всё сочетается с вычислением степени неоднозначности, остаётся открытым , что как бы прямо намекает, что правильно будет искать её в исходном автомате, а не после этого преобразования)