Что такое алгоритм МакНотона-Ямады?

Question

Мне нужно построить DFA, используя алгоритм МакНотона-Ямады для класса CS.Проблема в том, что алгоритм является дополнительным материалом, и мне не ясно, что именно.Это метод для поиска DFA с заданным RegEx или поиск DFA плюс его минимизация?Я не могу найти информацию по этому вопросу.

Я сбит с толку, потому что процедура минимизации, которую мой преподаватель показал после того, как мы обнаружили DFA в классе, не отличается от минимизации «отметки», описанной в нашей книге .

Спасибо за ваш ответ,

Натан

Answer 1

Описание алгоритма (для регулярных выражений для NFA и NFA для DFA) приведено на http://swtch.com/~rsc/regexp/regexp1.html;, они показывают версию Томпсона и утверждают, что алгоритм Макнотона-Ямады в основном такой же, но генерирует DFAпрямо из регулярного выражения.

Answer 2

Их алгоритм обычно не рассматривается отдельно от работы Томпсона. Оригинал Томпсона превратился из регулярного выражения в симулированный NFA в памяти. Алгоритм Томпсона-МакНотона-Ямады - это расширение, которое превращает регулярное выражение в фактический NFA, сохраненный в памяти, в отличие от переходного моделирования.

Преобразование NFA в DFA (определение) не является частью расширения МакНотона или Ямады. Скорее, это делается с помощью алгоритма конструкция подмножества (он же конструкция powerset).

Вы можете увидеть алгоритм Томпсона-МакНотона-Ямады и алгоритм построения подмножеств в действии с произвольными регулярными выражениями, используя регулярное выражение из набора инструментов компиляции для инструмента NFA и DFA .

Answer 3

"... алгоритм анализа МакНотона-Ямады, в котором найдено регулярное выражение, описывающее слова, принятые конечным автоматом, чья таблица переходов задана. Неизмененный алгоритм выдаст 4n слагаемых, представляющих n-конечный автомат. число может быть уменьшено путем исключения дублирующих вычислений и отклонения высокоуровневых выражений, соответствующих невозможному пути на той же диаграмме состояний. Остальные выражения представляют серьезную проблему упрощения, поскольку пустые выражения и пустые слова генерируются алгоритмом свободно. "

Источник