NFA / DFA с переменными условиями перехода

Question

Спокойной ночи,

Предположим, у меня есть класс, который реализует NFA / DFA, чьи переходы хранятся в структуре словаря .NET, и который принимает входное слово и распознает набор слов, выводимых каким-либо образом из ввода. Кроме того, давайте предположим, что автомат является универсальным шаблоном, который может быть применен к различным словам одинаковой длины только с повторной маркировкой символов перехода. Каков наилучший способ кодирования функции перехода в Словаре, чтобы ее переходы можно было пометить в соответствии с символами входного слова во время выполнения?

Большое спасибо.

Answer 1

Пожалуйста, смотрите следующую реализацию, которая берет NFA и преобразует его в DFA (а затем в график), используя словарь, как и вы:

от NFA до DFA

Я не уверен, обладает ли она способностью динамической перемаркировки, которую вы ищете, но она очень хорошо (in-line) задокументирована, поэтому вы можете получить много идей, которые помогут вам в вашем проекте.

Существует также хорошая (более свежая) статья на тему лямбда-переходов, но ссылки на изображения этой статьи больше не действительны. Однако он поставляется с загружаемым исходным кодом FSAutomata.zip , который вы можете просмотреть после прочтения статьи:

NFA с лямбда-переходом