Участница:Наталья Юльцова
Преобразование регулярного выражения в ДКА
Алгоритм
Чтобы преобразовать регулярное выражение в ДКА, нужно:
- Преобразовать регулярное выражение в -НКА.
- Устранить -переходы.
- Построим по НКА эквивалентный ДКА.
Преобразование регулярного выражения в -НКА.
Рассмотрим подробнее как преобразуется регулярное выражение в -НКА. Автомат для выражения строится композицией из автоматов, соответствующих подвыражениям.
Виды выражений:
- Данное выражение имеет вид для некоторых подвыражений и . Тогда ему соответствует автомат, представленный на рис. 1.a.
- Выражение имеет вид . Автомат для этой конкатенации представлен на рис. 1.б.
- Выражение имеет вид для некоторого подвыражения . Используем автомат, представленный на рис. 1.в.
Пример
Задача: Преобразовать регулярное выражение
в ДКА.Регулярное выражение | Автомат |
---|---|
Преобразуем регулярное выражение | в -НКА. Построим сначала автомат для . Это выражение имеет вид .|
Далее считаем, что | это подвыражение вида , и строим выражение .|
Выражение | имеет вид , имеет тот же вид.|
Удалим статьи, получим НКА. | -переходы, согласно алгоритму из|
Преобразуем НКА в ДКА по алгоритму Томпсона. |
Преобразование ДКА в регулярное выражение
Алгебраический метод Бжозовского
При преобразовании ДКА в регулярное выражение создается система регулярных выражений для каждого состояния в ДКА, а затем она решается для регулярных выражений
, связанных с терминальным состояниями . Построение уравнения происходит следующим образом: для каждого состояния уравнение является объединением переходов, ведущих в это состояние. Переход a из в обозначается за . Если - терминальное состояние, то в добавляется . Это приводит к системе уравнений вида:
где
= ∅ если нет перехода от к . Система может быть решена с помощью простой подстановки, за исключением случаев, когда неизвестное появляется как в правой, так и в левой части уравнения. Для этого можно воспользоваться теоремой Ардена:Уравнение вида
, где , имеет решение .Пример
Задача: Построить регулярное выражение, удовлетворяющее данному ДКА.
Решение:
Рассмотрим первое терминальное состояние:
Воспользуемся теоремой Ардена:
Рассмотрим второе терминальное состояние :
Объединим выражения для терминальных состояний и получим искомое регулярное выражение:
См. Также
Источники информации
- John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman «Introduction to Automata Theory, Languages, and Computation», 2/E
- Christoph Neumann «Converting Deterministic Finite Automata to Regular Expressions»