Участница:Наталья Юльцова — различия между версиями
(→Преобразование регулярного выражения в ДКА) |
(→Преобразование регулярного выражения в ДКА) |
||
Строка 3: | Строка 3: | ||
==Алгоритм== | ==Алгоритм== | ||
− | [[Файл:RegToAut.png|300px|thumb|right]] | + | [[Файл:RegToAut.png|300px|thumb|right|рис. 1]] |
# Преобразуем регулярное выражение в <tex>\varepsilon</tex>-НКА. | # Преобразуем регулярное выражение в <tex>\varepsilon</tex>-НКА. | ||
Строка 16: | Строка 16: | ||
Виды выражений: | Виды выражений: | ||
− | # Данное выражение имеет вид R|S для некоторых подвыражений R и S. Тогда ему соответствует автомат, представленный на рис. a. | + | # Данное выражение имеет вид <tex>R|S</tex> для некоторых подвыражений <tex>R</tex> и <tex>S</tex>. Тогда ему соответствует автомат, представленный на рис. 1.a. |
− | # Выражение имеет вид RS. Автомат для этой конкатенации представлен на рис. b. | + | # Выражение имеет вид <tex>RS</tex>. Автомат для этой конкатенации представлен на рис. 1.b. |
− | # Выражение имеет вид R* для некоторого подвыражения R. Используем автомат, представленный на рис. c. | + | # Выражение имеет вид <tex>R^*</tex> для некоторого подвыражения R. Используем автомат, представленный на рис. 1.c. |
===Пример=== | ===Пример=== | ||
− | Преобразовать регулярное выражение (0|1)*1(0|1) в ДКА. | + | Преобразовать регулярное выражение <tex>(0|1)^*1(0|1)</tex> в ДКА. |
{| class = "wikitable" | {| class = "wikitable" |
Версия 22:48, 1 января 2021
Содержание
Преобразование регулярного выражения в ДКА
Алгоритм
- Преобразуем регулярное выражение в -НКА.
- Устраним -переходы.
- Построим по НКА эквивалентное ДКА по алгоритму Томпсона.
Преобразование регулярного выражения в ε-НКА.
Рассмотрим подробнее как преобразуется регулярное выражение в
-НКА. Автомат для выражения строится композицией из автоматов, соответствующих подвыражениям.Виды выражений:
- Данное выражение имеет вид для некоторых подвыражений и . Тогда ему соответствует автомат, представленный на рис. 1.a.
- Выражение имеет вид . Автомат для этой конкатенации представлен на рис. 1.b.
- Выражение имеет вид для некоторого подвыражения R. Используем автомат, представленный на рис. 1.c.
Пример
Преобразовать регулярное выражение
в ДКА.Регулярное выражение | Автомат |
---|---|
Преобразуем регулярное выражение | в -НКА. Построим сначала автомат для . Это выражение имеет вид .|
Далее считаем, что | это подвыражение вида R, и строим выражение .|
Выражение | имеет вид RS, имеет тот же вид.|
Удалим статьи, получим НКА. | -переходы, согласно алгоритму из|
Преобразуем НКА в ДКА по алгоритму Томпсона и минимизируем ДКА |
Преобразование ДКА в регулярное выражение
Алгебраический метод Бжозовского
Создадим систему регулярных выражений для каждого состояния в ДКА, а затем решим систему для регулярных выражений
, связанных с терминальным состояниями . Строим уравнения следующим образом: для каждого состояния уравнение является объединением переходов, ведущих в это состояние. Переход a из в обозначим за . Если - терминальное состояние, то добавим в . Это приводит к системе уравнений вида:
где
= ∅ если нет перехода от к . Система может быть решена с помощью простой подстановки, за исключением случаев, когда неизвестное появляется как в правой, так и в левой части уравнения. Для этого воспользуемся теоремой Ардена:Уравнение вида R = Q + RP, где P
, имеет решение R = QP*.Пример
Найти: Регулярное выражение, удовлетворяющее данному ДКА.
Решение:
Рассмотрим первое терминальное состояние:
Воспользуемся теоремой Ардена:
Рассмотрим второе терминальное состояние :
Объединим выражения для терминальных состояний и получим искомое регулярное выражение: