Как преобразовать NFA с перекрывающимися циклами в регулярное выражение?

11

Если я правильно понимаю, NFA обладают той же выразительной силой, что и регулярные выражения. Зачастую считывание эквивалентных регулярных выражений из NFA легко: вы переводите циклы в звезды, соединения в качестве альтернатив и так далее. Но что делать в этом случае:

введите описание изображения здесь
[ источник ]

Перекрывающиеся циклы затрудняют понимание того, что принимает этот автомат (в терминах регулярных выражений). Есть ли хитрость?

Zell
источник
2
Было бы хорошо, если бы вы могли указать на диаграмме, каково начальное и конечное состояния: маленькая стрелка в начальное состояние и двойной круг в качестве конечного состояния. Кроме того, трудно понять, где вы идете не так, если вы не указали, что вы пробовали.
Дэйв Кларк
Возможно, этот документ может помочь вам: он четко объясняет, как преобразовать NFA в RE.
Вор
1
Почему это сложно? Вы пробовали один из канонических алгоритмов? Какой лучший анзац ты можешь сделать?
Рафаэль
3
Я отредактировал, чтобы сделать вопрос (imho) интересным и полезным для этого сайта. Посмотрите историю изменений, чтобы сформировать мнение.
Рафаэль
1
У меня есть готовый ответ, который превращает ваш NFA в регулярное выражение, но я удалил его: ответ Рафаэля дает вам метод, который вам нужен, чтобы сделать это самостоятельно (он также дает ссылку на пример), так что вы можете получить некоторую практику, если вы хотеть. Если вы все еще хотите мое решение, я восстановлю ответ.
Алекс тен Бринк

Ответы:

5

Вместо того, чтобы «зачитывать», вы должны использовать один из нескольких канонических методов для этого. Безусловно, самое приятное, что я видел, это тот, который выражает автомат как систему уравнений (регулярных) языков, которую можно решить. Это особенно приятно, поскольку, кажется, дает более краткие выражения, чем другие методы.

Я написал этот документ, объясняющий метод для студентов прошлым летом. Это напрямую связано с конкретной лекцией; упомянутая ссылка является типичным определением регулярных выражений. Доказательство леммы Ардена (необходимый результат) содержится; один для правильности метода отсутствует. Как я узнал об этом в лекции, к сожалению, у меня нет ссылки.

qi

Qi=qiaqjaQj{{ε}, qiF, else

Fqiaqjqiqja+

QiqiQ0q0

Приложение к данному автомату оставлено в качестве упражнения; полный пример включен в вышеупомянутый связанный документ .

Смотрите также здесь, где я разместил аналогичный ответ.

Рафаэль
источник
1
Смотрите этот справочный вопрос для других общих методов.
Рафаэль
3

Если бы была просто цепочка состояний без петли, вы бы знали, что делать?

Если бы существовал простой цикл без этого перекрывающегося ветвления, знаете ли вы, что делать?

(Если ответ «нет», сначала подумайте об этих случаях.)

Теперь идея состоит в том, чтобы постепенно преобразовать автомат, чтобы привести его в форму, в которой вы сможете определить эти паттерны: цепочки, петли и расходящиеся пути, которые в конечном итоге сходятся (что приводит к чередованию). На каждом этапе преобразования следите за тем, чтобы преобразованный автомат все еще распознавал один и тот же язык.

Имейте в виду , что это не -deterministic автомат. Тот, который вы опубликовали, оказывается детерминированным, но он не должен оставаться таким, когда вы преобразуете его.

q2q1fq2gq3q4q2q5q4jq5gq3

q3,q4,q5q3q3(hjg)

Позаботьтесь, чтобы проверить, какие состояния являются окончательными. Это может помочь не беспокоиться об этом сначала и сделать один большой цикл, а затем дублировать части, которые заканчиваются частично в цикле.

Это не обязательно является наиболее эффективным методом, или тот, который генерирует простейшую регулярное выражение, но это просто.

Жиль "ТАК - прекрати быть злым"
источник
3

Сплит q_1

Юкка Суомела
источник
И это отвечает на вопрос как?
Рафаэль
1
Если вы переписываете конечный автомат таким образом, теперь тривиально прочитать эквивалентное регулярное выражение.
Юкка Суомела
1
Возможно, вам следует включить это в текст ответа. Это всегда работает?
Рафаэль
@ Рафаэль: Это работает в этом случае. :) Основная идея этого трюка заключается в следующем: мы сделали циклы «правильно вложенными». То есть у нас нет структуры цикла [(])но [()].
Юкка Суомела