Операции над регулярными множествами

1.

Операции над
регулярными
множествами

2.

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

3.

Удаление циклов из начального состояния
конечного автомата
• Теорема. Для произвольного конечного
автомата существует эквивалентный автомат
без циклов в начальном состоянии.
• Доказательство. Пусть задан произвольный
конечный автомат: А = (К, Σ,δ, р0, F).
• Для того чтобы удалить цикл в начальном
состоянии конечного автомата, введём новое
состояние q0 и сделаем его начальным. Затем
из состояния q0 проведём дуги в те состояния
автомата, куда были направлены дуги из
состояния р0 в исходном автомате. В результате
преобразования получим автомат А1 без циклов
в начальном состоянии.

4.

• Формальная запись алгоритма
преобразования имеет вид:
• A1 = ( K ᴗ q0}, Σ, δ ᴗ q0a—>pi | p0a --->pi ϵ δ}, q0, F
ᴗ q0| p0 ϵ F}).
• Любая цепочка a1, a2...an принадлежащая
языку L(A), распознается автоматом А
следующей последовательностью команд:
• P0a1—>P1, P1a2 -> Р2, …. Pn-1an—> Pn, pn ϵ F.
• Эта же цепочка автоматом A1 распознается
следующей последовательностью команд:
• q0a1->p1, p1a2->р2, ..., pn-1an->pn, pn ϵ F.
• Таким образом, автоматы А и A 1
эквивалентны.

5.

Пример 1
• Удалить цикл в начальном состоянии
конечного автомата, граф которого
приведён на рисунке:

6.

• Решение. Этот конечный автомат
распознает цепочки регулярного
множества, заданного регулярным
выражением
• а* (bc)+d*
• Приведем формальное описание исходного
автомата А:
• А = (К, Σ, δ, р0, F), в котором
• К = {р0, р1 р2, р3}
• Σ = {а, Ь, с, d};

7.

• δ: р0а р0;
• Р0b р1
• p1c p2;
• Р2b p1
• P2d p3;
• Р3d р3;
• р0 - начальное состояние;
• F=(P2,P3).

8.

• Граф конечного автомата без циклов в
начальном состоянии имеет вид,
представленный на рисунке:

9.

• Формальное описание этого автомата
A1 = (К1 Σ,δ1 q0, F) имеет вид:
• К1 = (q0, р0, p1 p2, p3);
• Σ = {а, Ь, с, d}; функция переходов δ1
включает следующие команды:

10.

• δ1:
• q0a p0; q0b p1
• p0a р0; p0b p1
• p1c p2; р2b p1
• p2d p3; р3d р3
• q0 - начальное состояние автомата.
• Множество заключительных состояний
нового автомата осталось без изменения: F
= {р2, р3}

11.

• Если взять произвольную цепочку
• x=aabcd ϵ L, то ее можно распознать как в
автомате А, так и в автомате А1.
• Последовательность команд автомата А,
позволяющая распознать цепочку:
• δ: q0а p0; р0а p0; q0b p1; p1c p2; p2d
p3; р3 ϵ F. Последовательность команд
автомата A1, позволяющая распознать
цепочку:
• δ1:q0a p0; р0а р0; р0b p1; p1c p2; р2d
p3; р3 ϵ F. Следовательно, автоматы А и А1
эквивалентны и L(A)=L(A1).