1. Алфавит, слова, операции над словами

Вид материала

Документы

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

Подобный материал:

• Исполнительный кодекс Республики Молдова, 2184.07kb.
• Статьи 4 изложить в следующей редакции: "Статья Ответственность физических, юридических,, 41.3kb.
• Республика Молдова, 777.62kb.
• Федеральный закон, 404.04kb.
• Подготовка к операции по прорыву блокады проводилась в глубокой тайне, 18.04kb.
• Игра «Алфавит» Чтобы узнать тему нашего занятия вы должны расшифровать слова. (зашифрованные, 50.79kb.
• «День культуры и славянской письменности», 78.75kb.
• Выполнили: Фурманова Диана 3класс, 121.65kb.
• Работа со словами с непроверяемыми написаниями, 134.51kb.
• Календарно-тематический план учебная дисциплина: «Математика», 34.71kb.

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

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

Пусть 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, P Q, 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


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

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

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

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

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