ОПЕРАЦИИ НАД ЯЗЫКАМИ
1) конкатенация языков P Q = {pq | pÎP, q Î Q}, т.е. это множество слов, получаемых всевозможными приписываниями к словам из языка Р слов из языка Q;
2) объединение P ∪ Q;
3) итерация Р*.
Заметим, что операция конкатенации не коммутативна, в отличие, от объединения, т.е. P Q≠Q P.
Множество всех языков над Х, вместе с перечисленными операциями образуют алгебру, которая называется алгеброй Клини:
< > – алгебра Клини.
Определение. Определим рекурсивно формулу, т.е. регулярное выражение f над алфавитом Х, и регулярный язык L(f),задаваемый этим выражением:
1) | e, x, Æ -- регулярные выражения (формулы). Они задают языки: | |||
L (е) =е; L (Æ) =Æ; L (х) =х; | ||||
2) | если P и Q — регулярные выражения, то | L (P Q)= L (P) L (Q); | ||
а) | P Q — регулярное выражение; | |||
б) | P ∪ Q — регулярное выражение; | L (P ∪ Q)= L (P)∪ L (Q); | ||
в) | P* — регулярное выражение; | L (P*) =P*; | ||
3) | других нет. |
В соответствии с определением языка, будем отождествлять формулу и язык, который она задаёт. Будем также считать, что операция операция «*» имеет самый высокий приоритет, а операция «∪» — самый низкий, тогда в регулярных выражениях можно опускать лишние скобки.
Примеры регулярных выражений: P ∪ Q, (P ∪ Q)*, (P * Q)*.
Некоторые эквивалентные преобразования формул
(законы алгебры Клини)
1) P ∪ Q = Q ∪ P – коммутативность объединения
2) e P = P e = Р
3) -- ассоциативность конкатенации
4) дистрибутивность конкатенации относительно объединения:
5) Разложение итерации: Р* = e ∪ * = e
т.к. Р*= е ∪P1 ∪ P2 ∪P3 … = e ∪ P е ∪P1 ∪ P2 ∪P3 …) = e Р*
6) Æ
7) e*=e
8) Æ* = e,
т.к. Æ* = Æ0 ∪ = e ∪ Æ = e.
Рассмотрим решение уравнений в алгебре Клини.
Уравнение вида
(1) X =
называется каноническим праволинейным уравнением.
Здесь P и Q – известные языки, а Х – неизвестный.
Теорема 1. Для решения уравнения (1) справедливы следующие утверждения.
1. X = P* Q есть решение (1).
2. X = P* Q есть наименьшее по включению решение (1).
Другими словами, если уравнение (1) имеет много решений, то P* Q включается в каждое из них.
3. Если Р не содержит пустого слова, т.е. если eÏP, то X = P* Q является единственным решением уравнения (1).
Рассмотрим применение этой теоремы на практике.
Пример. Построить формулу, описывающую язык, распознаваемый следующим автоматом A=(S,X,d,S0,F), где S={0,1,2,3}, X={0,1}, S0={0}, F={1,2}, функция переходов d показана на графе:
А:
Обозначим через Li множество слов, которые ведут из i-го состояния автомата в
|
заключительные состояния: Li={w | Si à tÎF}. Множества Li -- это неизвестные языки в том смысле, что регулярные выражения для них не известны. Нам требуется найти выражение для языка L0.
Для каждого состояния и соответствующего ему языка составляем уравнение. Например, для S0 язык состоит из 2-х множеств слов:
1) тех, которые начинаются с 0, и продолжением которых является множество L0 -- поскольку по 0 автомат из S0 опять переходит в S0;
2) тех, которые начинаются с 1, и продолжением которых является множество L1 -- поскольку по 1 автомат из S0 переходит в S1.
Если при этом состояние Si является заключительным, то добавляем пустое слово.
В результате получаем систему уравнений:
L0=0 L0 ∪ 1 L1
L1=0 L2 ∪ 1 L0 ∪ e (т.к. S1 – заключительное) L0 --?
L2=0 L3 ∪ 1 L2 ∪ e
L3=0 L3 ∪ 1 L3 (т.к. S3 – заключительное)
Решаем систему относительно Li, последовательно выражая Li друг через друга и подставляя их в уравнения -- аналогично решению системы линейных уравнений.
Наша цель – найти выражение для L0.
Начнем решать систему с последнего уравнения относительно неизвестного L3 (это уравнение наиболее простое в силу закона 6):
L3 = (0 ∪ 1) L3 = (0 ∪ 1) Æ = Æ
Подставим найденное L3 в уравнение для L2:
L2 = 0 L3 ∪ 1 L2 ∪ e = 0 Æ ∪ 1 L2 ∪ e =Æ ∪ 1 L2 ∪ e =1 L2 ∪ e = 1* е = 1* (по 2-му закону)
Подставим найденное L2 в уравнение для L1:
L1 = 0 L2 ∪ 1 L0 ∪ e = 01* ∪ 1 L0 ∪ e
И, наконец, подставляем найденное L1 в уравнение для L0:
L0 = 0 L0 ∪ 1 L1 = 0 L0 ∪ 1 (01* ∪ 1 L0 ∪ e) = 0 L0 ∪ 101* ∪ 11L0 ∪ 1
= (0 ∪ 11) L0 ∪ (101* ∪ 1) = (0 ∪ 11)* (101* ∪ 1).
|
Ответ: L0 = (0 ∪ 11)* (101* ∪ 1).
Основной результат в теории регулярных языков:
Теорема 2. Следующие классы языков совпадают:
1. Языки, порождаемые регулярными грамматиками;
2. Языки, распознаваемые конечными акцепторами.
3. Языки, описываемые регулярными выражениями.