Математическая теория формальных языков


Теорема Клини - часть 2


Очевидно, что .

Пример 5.3.6.

Рассмотрим язык, распознаваемый конечным автоматом

где

и

Тот же язык порождается обобщенным конечным автоматом

где

После устранения состояния q3

получается обобщенный конечный автомат

где

Можно упростить регулярные выражения и получить

После устранения состояния q4

и упрощения регулярных выражений получается обобщенный конечный автомат

где

Следовательно, язык L(M) задается регулярным выражением

Упростив это регулярное выражение, получим

Упражнение 5.3.7. Найти регулярное выражение для языка, порождаемого грамматикой

Упражнение 5.3.8. Найти регулярное выражение для языка

Упражнение 5.3.9. Найти регулярное выражение для языка , где L1 = (aaab+c+d)*, L2 = (a*ba*ba*bc+d)*, L3 = ((a+b)*c(a+b)*cd)*

Упражнение 5.3.10 Найти регулярное выражение для дополнения языка (a+b)*bbb(a+b)* в алфавите {a,b}.

Упражнение 5.3.11 Найти регулярное выражение для дополнения языка (ab+ba)*(1+a+b) в алфавите {a,b}.

Упражнение 5.3.12 Найти регулярное выражение для дополнения языка (a+b)*(aab+abaa+abb)(a+b)* в алфавите {a,b}.

Упражнение 5.3.13 Найти регулярное выражение для дополнения языка (aa(ab)*bb(ab)*)* в алфавите {a,b}.




Начало  Назад  Вперед



Книжный магазин