Математическая теория формальных языков
Теорема Клини
Определение 5.3.1.
Назовем обобщенным конечным автоматом аналог конечного автомата, где переходы помечены не словами, а регулярными выражениями. Метка пути такого автомата - произведение регулярных выражений на переходах данного пути. Слово w допускается обобщенным конечным автоматом, если оно принадлежит языку, задаваемому меткой некоторого успешного пути.
Замечание 5.3.2.
Каждый конечный автомат можно преобразовать в обобщенный конечный автомат, допускающий те же слова. Для этого достаточно заменить всюду в метках переходов пустое слово на 1, а каждое непустое слово - на произведение его букв.
Замечание 5.3.3.
Если к обобщенному конечному автомату добавить переход с меткой 0, то множество допускаемых этим автоматом слов не изменится.
Пример 5.3.4.
Пусть . Обобщенный конечный автомат , где Q = {1,2,3}, I = {1,2}, F = {3},
допускает все слова в алфавите , кроме слов, содержащих подслово aa.
Теорема 5.3.5 (теорема Клини).
Язык L является регулярным тогда и только тогда, когда он является автоматным.
Доказательство. Пусть e - регулярное выражение. Индукцией по построению e легко показать, что задаваемый им язык является автоматным (см. теорему 3.1.1).
Обратно, пусть язык L распознается некоторым (недетерминированным) конечным автоматом с одним начальным состоянием и одним заключительным состоянием. Существует эквивалентный ему обобщенный конечный автомат , где . Если есть несколько переходов с общим началом и общим концом (такие переходы называются параллельными), заменим их на один переход, используя операцию +.
Устраним по очереди все состояния, кроме q1
и q2. При устранении состояния q нужно для каждого перехода вида , где , и для каждого перехода вида , где , добавить переход , где регулярное выражение g - метка перехода из q в q (если нет перехода из q в q, то надо добавить переход ), и снова всюду заменить параллельные переходы на один переход, используя операцию +.
После устранения всех состояний, кроме q1 и q2, получится обобщенный конечный автомат , где
Очевидно, что .
Пример 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}.
