Регулярные множества и регулярные выражения.

Определим еще некоторый класс языков — регулярных множеств. Соотношение его с классом А-языков определим позднее.

Пусть V_Tконечный алфавит. Регулярные множества в алфавите V_Tопределяются рекурсивно:

1) - регулярное множество;

2) {} - регулярное множество;

3) {a}регулярное множество для любого aV_T;

4) если PиQ- регулярные множества, то таковы также и множества:PQ, PQ, P*;

5) никаких других регулярных множеств нет.

По-другому можно определить регулярное множество как такое, которое можно получить из ,{} , {a} и множеств, полученных на предыдущих шагах, путем конечного числа при­менений операций "", "" и "*".

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

Регулярные выражения в алфавите V_Tи регулярные множества, которые они обозначают, определяются рекурсивно:

1) 0 - регулярное выражение, обозначающее регулярное множество .

2) 1 -регулярное выражение, обозначающее регулярное множество {},

3) если a V_T; тоa -регулярное выражение, обозначающее регулярное множество {a};

4) если pи q - регулярные выражения, обозначающие регулярные множестваPиQто:

a)(p+q)- регулярное выражение, обозначающее регулярное множество PQ ,

б) (pq)- регулярное выражение, обозначающее регулярное множествоPQ,

в) (p*) - регулярное выражение, обозначающее регулярное множествоP*;

5) никаких других регулярных выражений нет.

Как обычно, когда можно опустить лишние скобки без по­тери однозначности чтения, мы будем это делать. Так, 0+110*обозначает (0+((11)(0)*)). Мы будем придерживаться соглашения, что * обладает наивысшим приоритетом, затем • и, наконец, +.

Очевидно, что для каждого регулярного множества можно найти регулярное выражение, его обозначающее, и наоборот. К сожалению, как мы увидим дальше, одному и тому же регулярному множеству может соответствовать бесконечно много регулярных выражений.

Будем говорить, что регулярные выражения равны (обозначается значком =), если они обозначают одно и то же регу­лярное множество.

Запишем основные алгебраические тождества для регулярных выражений. Часть из них мы уже знаем, остальные легко доказываются. Если ,, -регулярные выражения, то:

1. 

2. ;

3. 

4. +()=(;

5. 11

6. 000

7. ;

8. 

9. *=*;

10. (*)*=*;

11. ** =*

12. *=*

13. 0

14. 1*=1

15. 0*=1

16. ()*()*;

17. (*)**=(+)*=(* +*)*;

18. (*)*=(+)*+1;

19. (*)*=(+)* +1;

20. Если =*, то=*+;

21. Если и, то*.

Последнее тождество является основным при решении уравнений.

Теорема (Клини). Каждому А-языку над Vсоответствует регулярное выражение надV. Каждому регулярному выражению надVсоответствует А-язык.

Идея доказательства:

L– регулярное множествоL– А-язык.

- регулярное множество (грамматика с пустым множеством правил);

 - регулярное множество (S);

аV_T- регулярное множество (Sа);

если P,Qрегулярные множества, тоPQ,PQ,P* - так же регулярные множества (легко показать через соединение двухполюсников, порождающих языки, соответствующиеPиQ.

L- А-языкL– регулярное множество.

Пусть есть А-грамматика G=< V_T,V_N, S, R>,

A_i  a₁ a₂… a_k b₁A_j1 b₂A_j2 … b_mA_jm

где a_s, b_qV_T, A_jsV_N. Обозначим X_i- язык, порождаемый грамматикой G_iв которой в качестве начального символа выбран символА_i.Тогда указанные правила эквивалентны следующему уравнению:

X_i = a₁ + a₂ + …+ a_k + b₁X_j1 + b₂ X_j2 + … + b_m X_jm.

Действительно, если X_iобозначает язык, порождаемый грамматикой G_i,когда A_i- начальный символ, то, так как возможны выводы A_i  a₁, A_i  a₂, A_i  a_k,мо­жем написать, чтоa₁, a₂,…, a_kX_iи, следовательно, X_i = a₁ + a₂ +…+ a_k +… С другой стороны, пустьA_jkx_jk, т.е.x_jkX_jk, тогда возможен выводA_i ⁺ b_kA_jk ⁺ b_kx_jk.Следовательно,b_kx_jkX_iи это верно для любой цепочкиx_jkX_jk. Поэтому, дополняя предыдущую записьX_i, можем написать:

X_i = a₁ + a₂ + …+ a_k + b₁X_j1 + b₂ X_j2 + … + b_m X_jm.

Полное доказательство проводится индукцией по числу правил грамматики.

Как по регулярному выражению построить А-грамматику?

Конкатенация моделируется последовательным соединением двухполюсников, + - параллельным соединением, * - - замыканием. Т.о., последовательно выполняя операции, получим двухполюсники, соответствующие регулярному выражению. Построенные двухполюсники можно затем упростить.

Например, регулярным выражениям (a+b)c, (a+b)*c, (ab+bc)*(ab+c) будут соответствовать диаграммы, представленные на рис. 21 а, б, в соответственно.

Рис.21

Обратная задача:

есть А-грамматика. Надо найти язык, порождаемый этой грамматикой, записанный в виде регулярного выражения.

Например, имеется А-грамматикаG₁₂с правилами:

A a AbB

B  b B  c

Обозначим язык, порождаемый грамматикой с начальным символом A-X_a, и язык, порождаемый грамматикой с начальным символомB–X_b.

Тогда соответствующие уравнения примут вид:

X_a = a X_a + b X_b

X_b = b X_b + c

Система уравнений может иметь бесконечно много решений, нас интересует минимальное по мощности решение.

Систему уравнений с регулярными коэффициентами назо­вем стандартной над множеством неизвестных ={X1,X2,...X_n}, если она имеет вид

X₁ = ₁₀ + ₁₁ X₁ + ₁₂ X₂ + ... + _1n X_n;

X₂ = ₂₀ + ₂₁ X₁ + ₂₂ X₂ + ... + _2n X_n;

…

X_n =  _n0 + _n1 X₁ + _n2 X₂ + ... + _nn X_n;

где все  _{i j} - регулярные выражения. Если какое-либоi-ое уравнение не содержит переменнуюX_j, то достаточно положить соответствующий коэффициент _{i j} = 0, если _{i j} =1, то его можно не писать.

В общем случае система уравнений имеет вид:

x₁= f₁(x₁, x₂,…,x_n)

x₂= f₂(x₁, x₂,…,x_n)

….

x_n= f_n(x₁, x₂,…,x_n)

Где f_{i -}конечная функция,x_j– конечное множество строк над V_T, на множествеx₁,x₂,…,x_nопределены операции объединения и конкатенации. Обозначимx₁,x₂,…,x_nкакХ, а системуX=F(X). Решение системыS=(S1,S2,…Sn) – совокупность подмножествV_T, такая, чтоS=F(S).

Определим S  T = _Df S₁T₁ , S₂ T₂, …, S_n  T_n.

Теорема. Система уравненийX=F(X) имеет решениеS=Fⁱ(). ЕслиS₁– другое решение, тоSS₁.

Определение: Говорим, что функция F:P(A)P(A)P(A) монотонно возрастает, если изA₁B₁иA₂B₂следует, чтоF(A₁,A₂)F(B₁,B₂).

Лемма:Операция конкатенации – монотонно возрастающая функция.

Очевидно, что операция объединения так же является монотонно возрастающей функцией.

Доказательство теоремы:

Т.к. = (,, …,), то F(). Легко показать, что еслиAB, тоF(A)F(B). ПоэтомуF()F(F()) и т.д. Получаем возрастающую последовательность: F()F²()F³()…

Пусть S=Fⁱ(). Тогда S=F(S). ЕслиT- некоторое другое решение, тоT =F(T), ноT, значит,F() F(T)=T. Очевидно, что по индукции можно доказать, чтоFⁱ() Tдля всехi, следовательно, Fⁱ()T.

Пример: Рассмотрим систему

X_a = a X_a + b X_b

X_b = b X_b + c

Для удобства работы обозначим X_a–x,X_b–y.

f₁(x,y)= ax + y;

f₂(x,y)=by+c;

f1(,)=; f2(,)=c;

f1(,c)=bc; f2(,c)=bc+c;

f1(bc,bc+c)= abc+b(b+)c f2(bc,bc+c)=(b2+b+)c

f₁(abc+b(b+)c, (b²+b+)c) =(a+)ab(bc+c)+b(b+)²c

f₂(abc+b(b+)c, (b²+b+)c) = (b³+b²+b+)c

f₁((a+)ab(bc+c)+b(b+)²c, (b³+b²+b+)c)= (a+)³ab(bc+c)+b(b³+b²+b+)c

Откуда получаем

y=b*c

x=a*bb*c

Тем не менее основным способом решения стандартной системы уравнений - ме­тод последовательного исключения неизвестных, подобным методу Гаусса. Покажем это на этом же примере.

X_a = a X_a + b X_b

X_b = b X_b + c

Из тождества 21 получаем

X_b=b*c

X_a = a X_a + b b*c= a*bb*c

Таким образом, существуют следующие основные способы задания А-языков:

А-грамматика.

Конечные лингвистические автоматы.

Стандартная система уравнений.

Регулярное выражение.