Я пытаюсь реализовать минимизатор DFA в моем лексере, но я не могу создать DFA, который не выглядит так, как будто это уже минимальный DFA для выражения.
Я создаю DFA из NFA, который построен с использованием конструкции Thomson из регулярного выражения postfix. Это в значительной степени именно то, что описано в книге о драконах. Для создания лексера несколько NFA объединяются с помощью эпсилон-переходов из начального состояния. Именно на этом комбинированном NFA применяется алгоритм DFA.
Итак, есть ли какое-нибудь "известное" регулярное выражение, которое сгенерирует DFA, который станет хорошим испытательным стендом для устранения мертвого состояния и минимизации состояния?
Конечно, я мог бы просто взломать странный DFA и применить к нему алгоритмы, но на самом деле это не был бы правильный тестовый пример, не так ли? Если это так, что метод, который я создаю, DFA не склонен к мертвым состояниям, то эта информация будет столь же ценной, поскольку тогда я могу вообще пропустить реализацию функции исключения состояний.
Редактировать: Если вам нужны подробности реализации для точного ответа, код доступен на github , в частности NFA.cs и DFA.cs классы. Кроме того, я написал серию сообщений в блоге о алгоритме построения, который я использую, если это поможет.