Шаги по созданию NFA из регулярного выражения

У меня возникают проблемы с описанием каждого шага при создании NFA из регулярного выражения. Вопрос заключается в следующем:

Преобразуйте следующее регулярное выражение в не детерминированный автомат конечного состояния (NFA), четко описывая шаги алгоритма, который вы используете: (Б | а) * Ь (а | б)

Я сделал простую машину с тремя состояниями, но очень сильно от интуиции. Это вопрос из предыдущего экзамена, написанного моим лектором, который также написал следующее объяснение алгоритма Томпсона: http://www.cs.may.ie/staff/jpower/Courses/Previous/parsing/node5.html

Может ли кто-нибудь прояснить, как "четко описать каждый шаг"? Это просто похоже на набор основных правил, а не на алгоритм с шагами.

Может быть, есть алгоритм, который я где-то замалчивал, но до сих пор я только что создал их с образованной догадкой.

Ответы

Ответ 1

Короткая версия для общего подхода.
Там есть алгоритм под названием "Алгоритм построения Томпсона-МакНотона-Ямады", а иногда и просто "Конструкция Томпсона". Каждый строит промежуточные NFA, заполняя части по пути, соблюдая при этом приоритет оператора: сначала круглые скобки, затем Kleene Star (например, a *), затем конкатенация (например, ab), а затем чередование (например, a | b).

Здесь углубленное прохождение для построения (b | a) * b (a | b) NFA

Строительство верхнего уровня

  1. Обрабатывать скобки. Примечание. В реальной реализации может иметь смысл обрабатывать скобки с помощью рекурсивного вызова их содержимого. Для ясности я отложу оценку всего, что находится внутри паренов.

  2. Kleene Stars: там только один *, поэтому мы создаем заполнитель Kleene Star, называемый P (который позже будет содержать b | a). Промежуточный результат:
    Non-Deterministic Finite Automata for P*

  3. Объединение: Присоедините P к b и присоедините b к машине-заполнителю с именем Q (которая будет содержать (a | b). Промежуточный результат:
    Non-Deterministic Finite Automata for P*bQ

  4. За скобками нет чередования, поэтому мы его пропускаем.

Теперь мы сидим на машине P * bQ. (Обратите внимание, что наши заполнители P и Q являются просто машинами конкатенации.) Мы заменяем ребро P на NFA для b | a, и заменяем ребро Q на NFA для a | b посредством рекурсивного применения описанных выше шагов.

Здание П

  1. Пропускать. Никаких паренов.

  2. Пропускать. Нет звезд Клини.

  3. Пропускать. Нет контакта.

  4. Постройте машину чередования для b | a. Промежуточный результат:
    NFA for b or a

Интегрирование P

Затем мы возвращаемся к этой машине P * bQ и вырываем P-ребро. Мы имеем источник P-ребра, который служит начальным состоянием для P-машины, а пункт назначения P-ребра служит конечным состоянием для P-машины. Мы также делаем это состояние отклоненным (убираем его свойство быть состоянием принятия). Результат выглядит так:
enter image description here

Здание Q

  1. Пропускать. Никаких паренов.

  2. Пропускать. Нет звезд Клини.

  3. Пропускать. Нет контакта.

  4. Постройте машину чередования для a | b. Кстати, чередование коммутативно, поэтому a | b логически эквивалентно b | a. (Читайте: пропустите эту небольшую диаграмму сноски из лени.)

Интегрирование Q

Мы делаем то же, что и с P выше, за исключением того, что заменяем ребро Q интермедиями b | машины, которую мы построили. Это результат:
enter image description here

Тада! Я имею в виду, QED.

Хотите узнать больше?

Все изображения выше были созданы с использованием онлайн-инструмента для автоматического преобразования регулярных выражений в недетерминированные конечные автоматы. Вы можете найти его исходный код для алгоритма строительства Томпсона-Макнотона-Ямады онлайн.

Алгоритм также рассматривается в Aho Compilers: Principles, Techniques и Tools, хотя его объяснение мало на деталях реализации. Вы также можете извлечь уроки из реализации конструкции Томпсона в C превосходным Рассом Коксом, который подробно описал ее в популярной статье о сопоставлении регулярных выражений.

Ответ 2

В репозитории GitHub ниже вы можете найти реализацию Java в конструкции Thompson, где сначала создается NFA из регулярного выражения, а затем соответствующая строка сопоставляется с этим NFA:

https://github.com/meghdadFar/regex

Ответ 3

https://github.com/White-White/RegSwift

Нет больше утомительных слов. Проверьте этот репозиторий, он переводит ваше регулярное выражение в NFA и визуально показывает переходы состояний NFA.