В этой статье я рассмотрю несколько методов преобразования автоматов в регулярные выражения.
Метод удаления состояний
Алгоритм, известный как метод исключения состояний, первоначально разработанный Бжозовским и Маккласки, работает непосредственно с автоматом. Он заключается в подавлении состояний в атомате, одно за другим, при преобразовании меток переходов, так что язык, распознаваемый получающимся автоматом, остается неизменным.
На левой диаграмме показано состояние q, которое нужно подавить, состояние pi, которое предшествующим состоянием, и состояние rj, которое является конечным состоянием. Метки являются рациональными выражениями. На правой диаграмме показан автомат после подавления состояния q и новая метка перехода от pi к rj. Языки, принимаемые автоматом до и после подавления q равны.
Метод исключения состояний состоит в том, чтобы сначала дополнить множество Q (Q - множество состояний и также называется размерностью автомата) двумя новыми состояниями i и t и добавить переходы из i в каждое начальное состояние автомата и из каждого конечного состояния автомата в t. Затем все состояния в Q подавляются в соответствии с процедурой, описанной выше, и в определенном порядке. В конце остаются только состояния i и t вместе с переходом от i к t, помеченным выражением, которое является результатом алгоритма (регулярным выражением).
Пример преобразования
Алгебраический метод Бжозовского
Метод Бжозовского использует уникальный подход к генерации регулярных выражений. Мы создаем систему регулярных выражений с одним регулярным выражением, неизвестным для каждого состояния в автомате, а затем мы решаем систему для Rλ, где Rλ – регулярное выражение, связанное с начальным состоянием qλ. Эти уравнения являются характеристическими уравнениями автомата.
Построение характеристических уравнений является простым. Для каждого состояния qi в ДКА уравнение для Ri является объединением термов. Каждый член может быть построен так: для перехода a из qi в qj этот член является aRi. Если Ri – конечное состояние, λ также является одним из термов.
Это приводит к системе уравнений вида:
где ax=0 если нет перехода от Ri к Rj.
Пример преобразования №1
Характеристические уравнения следующие:
Мы решаем для R2, используя теорему Ардена:
Теорема такова:
Учитывая уравнение вида X = AX + B, где λ ∉ A, уравнение имеет решение X = A * B. Такие ситуации возникают, когда для состояния есть петля
Подставим в R1 и разрешим:
Таким образом, регулярное выражение для автомата равно a*bb*
Пример преобразования №2
Получившиеся уравнения:
R0=bR1
R1=aR2+bR3+λ
R2=aR2+bR2+λ
R3=aR2+bR3+λ
1. Преобразовываем второе уравнении
R2=aR2+bR2+λ=(a+b)* λ=(a+b)*
2. Преобразовываем третье и подставляем в него второе
R3=aR2+bR3+λ=b*(aR2+λ)=b*a(a+b)*
3. Подставляем второе и третье уравнение в первое
R1=aR2+bR3+λ=a(a+b)*+b b*a(a+b)*+ λ
4. Подставляем в нулевое уравнение
R0=bR1=b(a(a+b)*+b b*a(a+b)*+ λ)=ba(a+b)*+bb*a(a+b)*+b
Получившееся регулярное выражение: ba(a+b)*+bb*a(a+b)*+b