DFA Minimization алгоритм Бжозовского

Question

Я пытаюсь реализовать алгоритм Бжозовского для минимизации моего DFA Ниже приведен алгоритм для того же.

DFA = d(r(d(r(NFA)))) 

, где r() - инверсия NFA, а D() - NFA в DFA.

Но я не понимаю, в чем смысл r() Поиск в Google также не дает много информации.

Может кто-нибудь объяснить, что такое r() NFA.

Любая другая простая реализация алгоритма или C ++, пожалуйста, дайте мне знать ссылку.

Answer 1

Эта является реализацией из OpenFst.

В эта бумага представляет собой диаграмму (стр. 15), на которой показаны результаты применения операции реверса.

Более простой способ понять операции FSM - это использовать библиотеку, такую ​​как OpenFst, для создания и управления машинами, а затем визуализировать результаты с помощью Graphviz.

Answer 2

В коде reverse.c (найден здесь , но теперь не существует) вы найдете комментарий /* Create reversed edges */. Таким образом, я бы сказал, что r() меняет направление всех ребер (плюс проверяет, что обратный автомат имеет четко определенное начальное состояние).