Некоторые эквивалентные преобразования формул




ОПЕРАЦИИ НАД ЯЗЫКАМИ

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) других нет.  

 

В соответствии с определением языка, будем отождествлять формулу и язык, который она задаёт. Будем также считать, что операция операция «*» имеет самый высокий приоритет, а операция «∪» — самый низкий, тогда в регулярных выражениях можно опускать лишние скобки.

 

Примеры регулярных выражений: PQ, (PQ)*, (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-го состояния автомата в

w

заключительные состояния: 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).

 
 
Р Q

 


Ответ: L0 = (0 ∪ 11)* (101* ∪ 1).

 

Основной результат в теории регулярных языков:

Теорема 2. Следующие классы языков совпадают:

1. Языки, порождаемые регулярными грамматиками;

2. Языки, распознаваемые конечными акцепторами.

3. Языки, описываемые регулярными выражениями.

 

 



Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2017-06-30 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: