Название: Информатика (формальные языки и грамматики) - Методическая разработка(С.Е. Рояк)

Жанр: Информатика

Просмотров: 1363


Занятие  7.  регулярные множества и автоматные языки

 

Цель занятия: иметь представления об основных свойствах регулярных выражений. Знать основные интерпретации регулярных множеств. Уметь преобразовывать регулярные выражения в конечные автоматы, уметь строить по любому конечному автомату эквивалентное ему регулярное выражение.

 

Методические указания

 

Что необходимо знать:

· определение регулярных выражений;

· алгебру регулярных выражений;

· алгоритм построения по любому регулярному выражению эквивалентный ему конечный автомат и алгоритм обратного преобразования.

 

Основные определения

 

1. Если V = (a1,a2, …,an) – произвольный словарь, то:

а) Æ – регулярное выражение;

б) ai Î V – регулярное выражение;

в) {e} – регулярное выражение;

г) если r и s – регулярное выражение, то

      r + s   – регулярное выражение;

      rs       – регулярное выражение;

      r*       – регулярное выражение;

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

2. Примеры регулярных выражений :

(a + b)*aab = { waab | w Î {a,b}*};

1(1 + 0)*   =  { 1w | w Î {0,1}*}.

3. Графическое представление регулярных выражений,

например, (ab+a) (ab+b)*a графически можно представить:

 

4. Основные аксиомы:

Если r,q и s – регулярные выражения, то

1. r + s = s + r

2. (r + s)+q = r + (s + q) = r + s + q

3. r(s + q) = rs + rq

4. (s + q)r = sr + qr

5. r(sq) = (rs)q = rsq

6. r{e} = {e}r = r

7. r + Æ = Æ + r = r

8. rÆ = Ær = Æ

9.  q + q = q

10. q*q* = q*

11. qq* = q*q

12. (q*)* =q*

13. {e}* = {e}

14. Æ* = Æ

15. (rq)*r = r(qr)*

16. (q* + r*)* = (q*r*)* = (q + r)*

17. (q*r)* = (q + r)*r + {e} и (qr*)* = q(q + r)* + {e}

18. если q = r*s, то q = rq + s

19. если e Ï r и q = rq + s, то q=r*s

 

5. (Теорема Клини). Класс регулярных языков совпадает с классом непустых А-языков. Более того, по всякой А-грамматике G, порождающей непустой язык, можно построить регулярное выражение r, задающее L(G), а по всякому регулярному выражению r – А-грамматику G, порождающую задаваемый этим выражением язык.

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

А-грамматике:

1) по данной модифицированной грамматике построить граф;

2) путь в графе от начальной вершины к конечной записать в виде регулярного выражения, используя терминальные символы, размечающие дуги графа, операции: конкатенации – для последовательности символов, лежащих на этом пути, и итерации для циклов;

3) все пути, идущие из начальной вершины к конечной, соединяются операцией +, которая в регулярных выражениях обозначает объединение.

 

Например: Дана модифицированная грамматика

G=<{a,b},{S,A,B,K},S,{S→ aA| bA| aB| aK; A→ aA| bA| aB;

                   B →bK; K→ e}>.

Ей соответствует граф V=<{S,A,B,K}, {SA(a), SA(b), SB(a), SK(a), AA(a), AA(b), AB(a), BK(b)}>

(выражение SA(a) означает дугу в графе SA с разметкой a).

 

Таким образом, пути в графе SA(a)AA(a)*AB(a)BK(b) из вершины S в вершину К будет соответствовать регулярное выражение aa*ab. Пути SA(a)AA(b)*AB(a)BK(b) – ab*ab;

Пути SA(b)AA(a)*AB(a)BK(b) –ba*ab;

Пути SA(b)AA(b)*AB(a)BK(b) –bb*ab;

Пути SB(a)BK(b) – аb;

Пути SK(a) – a.

Объединяем все пути операцией + и получаем выражение aa*ab + ab*ab + ba*ab + bb* ab + ab + a. Используя аксиомы, данное выражение приводится к виду (a + b)*ab + a.

 

Задачи и упражнения

 

1. Для регулярного выражения (a+b)*aba+ab*aba:

построить синтаксическую схему РВ;

упростить РВ по аксиомам;

построить синтаксическую схему УРВ;

построить схему переходов между состояниями для

               УРВ;

построить конечный автомат;

построить грамматику;

определить язык.

 

2. Дан язык L={banw½n³0, wÎ{a, b}*} U {bkw½k³1,

    wÎ{a, b}*} U {b}

L®GA®КА®ДКА®МКА,

L®РВ®УРВ®КА,

сравните результаты, полученные в a) и b).

3. Дан граф конечного автомата

а) КА®ДКА®МКА®РВ,

b) КА®РВ®УРВ

с) сравните результаты, полученные в a) и b).

 

 

4. Дан граф конечного автомата

 

Подпись:  а) КА®ДКА®МКА®РВ,

b) КА®РВ®УРВ,

c) сравните результаты, полученные в a) и b),

d) определите язык, распознаваемый данным конечным автоматом.

 

5. Построить детерминированный конечный автомат, распознающий заданный язык L. Для полученного автомата построить эквивалентную леволинейную и эквивалентную праволинейную грамматики. Привести пример цепочки x Î L, показать процесс распознавания автоматом этой цепочки, а также построить вывод этой цепочки в обеих грамматиках:

а) (cab)+ U (b)* U bc*

b) (ba)*c* ∩(a*c*b*)+

c) ac*(ba)* U (ca)*cb*

d) (ab)*(cc)* ∩(b*c*a*)*

Тема  3.  Свойства КС-языков и грамматик