Операции над конечными автоматами

1.

Операции над конечными
автоматами

2.

• Операции над конечными автоматами
эквивалентны операциям над конечными
множествами, т.к. конечные автоматы
являются распознавателями регулярных
множеств (регулярных языков).

3.

• Теорема. Регулярные множества замкнуты
относительно операций итерации,
произведения, усеченной итерации,
объединения, дополнения, разности и
пересечения.

4.

• Доказательство.
• 1. Операция итерации языка L.
• Для того чтобы получить операцию итерации
языка L*, в исходном автомате необходимо
выполнить следующие преобразования:
• а) удалить цикл в начальном состоянии;
• б) удалить цикл в заключительных состояниях;
• в) объединить полученные начальное и
заключительное состояния.

5.

• 2. Произведение двух языков L1 u L2.
• Пусть язык L1 распознается автоматом А1 а
язык L2 - автоматом А2.
• Операцию произведения исходных языков
L=L1 L2 можно реализовать двумя
способами. В первом случае в исходных
автоматах необходимо выполнить
следующие преобразования:
• а) удалить циклы в заключительных
состояниях автомата А1;

6.

• б) заключительное состояние автомата A1
объединить с начальным состоянием
автомата А2. Тогда в новом автомате А,
распознающем язык L, начальным
состоянием будет начальное состояние
автомата А1 а во множество F войдут
заключительные состояния автомата А2.

7.

• Другой способ связан с выполнением следующих
преобразований исходных автоматов:
• а) удалить циклы из начального состояния автомата
А2;
• б) каждому заключительному состоянию автомата
А1 поставить в соответствие отдельный экземпляр
автомата А2;
• в) заключительные состояния автомата А1
объединить с начальным состоянием
соответствующего экземпляра автомата А2. В новом
автомате А начальным состоянием будет начальное
состояние автомата A1, а во множество F войдут
заключительные состояния всех экземпляров
автомата А2.

8.

• 3. Операция усечённой итерации языка L.
• L+=LL* = L*L.
• Эта операция реализуется как произведение L* L
или LL* .
• 4. Объединение двух языков L1 и L2.
• Для реализации операции L = L1 и L2 в исходных
автоматах необходимо выполнить следующие
преобразования:
• а) удалить циклы в начальных состояниях автоматов
A1и А2;
• б) объединить полученные начальные состояния
автоматов А1 и А2 в одно состояние, которое будет
начальным состоянием нового автомата А.
Заключительными состояниями нового автомата
будет множество F = F1 U F2.

9.

5. Операция дополнения языка L.
Для произвольного языка L справедливо отношение L с Σ*.
Тогда дополнение языка L определяется отношением L =
Σ* \ L.
Алгоритм построения конечного автомата, распознающего
язык L:
а) все заключительные состояния в исходном автомате
необходимо сделать незаключительными, а
незаключительные состояния - заключительными;
б) начальное состояние р0 остаётся без изменения, но в
новом автомате оно должно быть включено во множество
заключительных состояний F, если исходный автомат не
распознавал пустую цепочку, или исключено из
множества F, если исходный автомат допускал пустую
цепочку;

10.

• в) вводится дополнительное состояние f,
которое включается во множество
заключительных состояний нового автомата;
• г) из каждого состояния исходного автомата в
состояние f проводятся дуги, каждая из
которых соответствует символам входного
алфавита, не читаемым автоматом в данном
состоянии;
• д) в состоянии f строятся петли для всех
символов алфавита, чтобы обеспечить чтение
произвольного окончания цепочек
• языка L

11.

• 6. Разность двух языков L1 u L2.
• L = L1 \ L2 = L1 U L2
• 7. Пересечение двух языков L1 и L2:
• L = L1 L2 = L1 U L2 .