Теория конечных языков и автоматов. Курс лекций П. Н. Иваньшин 2
 Скачать 0.61 Mb.
|
|
Дискретная математика. Теория конечных языков и автоматов. Курс лекций П.Н. Иваньшин 2 Оглавление 1 Регулярные языки 5 2 Автоматы 9 2.1 Детерминированные и недетерминированные автоматы . . 9 2.2 Теорема Клини . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.3 Минимальные детерминированные автоматы и синтакси- ческие моноиды . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.4 Лемма о накачке . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.5 Алгоритмы сравнения языков и автоматов . . . . . . . . . . 20 2.6 Автоматы Мили и Мура . . . . . . . . . . . . . . . . . . . . 22 3 Грамматики 27 3.1 Формальные грамматики . . . . . . . . . . . . . . . . . . . . 27 3.2 Нормальные формы Хомского и Грейбаха . . . . . . . . . . 32 3.3 Автоматы с магазинной памятью . . . . . . . . . . . . . . . 40 3.4 Контекстно-свободные языки и лемма о накачке . . . . . . 43 4 Машина Тьюринга 49 4.1 Детерминированная машина Тьюринга . . . . . . . . . . . . 49 4.2 Недетерминированные машины Тьюринга и контекстно- свободные языки . . . . . . . . . . . . . . . . . . . . . . . . . 52 4.3 Проблема остановки для машин Тьюринга . . . . . . . . . . 54 4.4 Проблемы неразрешимости для контекстно-свободных язы- ков . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 3 4 Оглавление Глава 1 Регулярные языки Определение 1. Алфавит ? набор символов. Строка или слово последовательность a 1 a 2 a 3 a 4 . . . a n , где a i ? ? Определение 2. Обозначим через ? ? множество всех слов алфавита ? , включая пустое слово. Определим бинарную операцию конкатена- ция ? на ? ? следующим образом: Пусть a 1 a 2 a 3 a 4 . . . a n и b 1 b 2 b 3 b 4 . . . b m ? ? ? , тогда a 1 a 2 a 3 a 4 . . . a n ? b 1 b 2 b 3 b 4 . . . b m = a 1 a 2 a 3 a 4 . . . a n b 1 b 2 b 3 b 4 . . . b m Пусть S, T ? ? ? , тогда S ? T = {s ? t|s ? S, t ? T }. Множество S ? T будем также обозначать через ST . Определение 3. Пусть B ? ? ? , тогда замыкание Клини B ? мно- жество всех возможных конкатенаций слов из B вместе с пустым словом, т.е. B ? = {w 1 w 2 . . . w n |w i ? B} S{?} . Условимся, что ? ? = {?} Символ ? называется звезда (звездочка) Клини. Определение 4. Пусть ? алфавит. Тогда множество L ? ? ? на- зывается языком. Определение 5. Пусть ? алфавит. Класс регулярных выраже- ний R над ? определен по следующим правилам: (i) Символ ? регулярное выражение и ?a ? ?, символ a тоже регулярное выражение. (ii) Пусть w 1 и w 2 регулярные выражения, тогда w 1 w 2 , w 1 ? w 2 , w ? 1 и (w 1 ) регулярные выражения. (iii) Не существует никаких регулярных выражений, кроме тех, что получены по правилам (i) и (ii). 5 6 Глава 1. Регулярные языки Определение 6. Класс R регулярных языков над алфавитом ? име- ет следующие свойства: (i) ? ? R, если a ? ?, то {a} ? R. (ii) Если s 1 , s 2 ? R , то s 1 S s 2 , s 1 ? s 2 , s ? 1 ? R (iii) Только множества, построенные по правилам (i) и (ii) принад- лежат R. Определение 7. Код C подмножество ? ? . Если C подмноже- ство ? ? и каждое слово множества S ? ? ? может быть получено конкатенацией элементов C, то говорят, что C код S. Код C од- нозначен, если каждая строка S однозначно представима в виде кон- катенации элементов C. Определение 8. Пусть ? алфавит. Непустой код C ? ? пре- фиксный код, если для всех слов u, v ? C, представление u = vw, где w ? ? ? влечет u = v и w = ?. Непустой код C ? ? суффиксный код, если для всех слов u, v ? C , представление u = wv, где w ? ? ? влечет u = v и w = ?. Непустой код C ? ? бипрефиксный код, если C одновременно и префиксный и суффиксный код. Непустой код C ? ? инфиксный код, если u, wuv ? C влечет w = v = ? Код C блочный код если все строки C имеют одну и ту же длину. Теорема 1. Если код суффиксный, префиксный, бипрефиксный, инфикс- ный или блочный, то он однозначен. Теорема 2. Блочный код и суффиксный, и префиксный, и бипрефикс- ный, и инфиксный. Теорема 3. Инфиксный код всегда бипрефиксный. Задачи 1. Пусть w = 10110, найти такие слова v 1 , v 2 , v 3 , v 4 , v 5 , v i 6= v j , i 6= j, что v i w = wv i , i = 1, . . . , 5. 2. Найти множества регулярных слов, соответствующих выражениям: a) a(b ? c ? d)a; b) a ? b ? c ; c) (a ? b)(c ? d); d) (ab ? ?) ? (cd) ? ; 7 e) a(bc) ? d f) bc(bc) ? ; g) (a ? b ? ? ?)(c ? d ? ) 3. Найти регулярные выражения для множеств слов: a) {ab, ac, ad}; b) {ab, ac, bb, bc}; c) {a, ab, abb, abbb, abbbb, . . .}; d) {ab, abab, ababab, abababab, ababababab, . . .}; e) {ab, abb, aab, aabb}. 4. Пусть ? = {a, b, c}. Найти регулярные выражения множеств a) Слов, содержащих ровно две буквы b. b) Слов, содержащих ровно две буквы b и ровно две буквы c. c) Слов, содержащих не меньше двух букв b. d) Слов, начинающихся и заканчивающихся на a и содержащих не менее, чем по одной букве b и c. e) Слов, содержащих ровно две буквы b и ровно две буквы a. f) Слов, содержащих четное число букв b. 5. Которые из следующих кодов однозначны? a) {ab, ba, a, b}; b) {ab, acb, accb, acccb, . . .}; c) {a, b, c, bd}; d) {ab, ba, a}; e) {a, ab, ac, ad};. f) ab ? ; g) ab ? ? baaa ; h) ab ? c ? baaac ; i) (a ? b)(b ? a); j) (a ? b ? ?)(b ? a ? ?). 6. Являются ли следующие коды однозначными? Суффиксными? a) {ab, ba}; b) {ab, abc, bc}; c) {a, b, c, bd}; d) {aba, ba, c}; e) {ab, acb, accb, acccb}. 7. Которые из следующих кодов суффиксные (префиксные)? a) ab ? ; b) ab ? c ; c) a ? bc ? ; d) (a ? b)(b ? a); e) a ? b 8. Доказать последние три теоремы первой главы. 8 Глава 1. Регулярные языки Глава 2 Автоматы 2.1 Детерминированные и недетерминирован- ные автоматы Определение 9. Детерминированный (детерминистский) авто- мат (?, Q, s 0 , ?, F ) , состоит из конечного алфавита ?, конечного набо- ра состояний Q, и отображения ? : Q Ч ? ? Q, называемого функ- цией переходов, и множества F заключительных (конечных, до- пускающих) состояний. Множество Q содержит как элемент s 0 , так и подмножество F . Примеры: 1. // s 0 b a // s 1 a,b 2. // s 0 a // b,c (( s 1 b,c )) a s 2 a,b,c vv s 2 a,b,c [[ Определение 10. Недетерминированный автомат есть набор (?, Q, s 0 , ?, F ) и состоит из конечного алфавита ?, конечного набора состояний Q, и отображения ? : QЧ? ? 2 Q , называемого функцией переходов, и множества F заключительных (конечных, допус- кающих) состояний. Множество Q содержит как элемент s 0 , так и подмножество F . Здесь множество 2 Q множество всех подмно- жеств Q. 9 10 Глава 2. Автоматы Пример: // s 0 a // a,b s 1 a // a,b s 2 a,b Определение 11. Язык M(L) принимается автоматом M если ?w = w 1 . . . w n ? M (L) , w 1 (w 2 (. . . (w n (s 0 )))) ? F , w i ? ? (i = 1, . . . , n), и наобо- рот w(s 0 ) ? F влечет w ? M(L). Теорема 4. Для каждого недетерминированного автомата существу- ет детерминированный автомат, принимающий тот же язык. Доказательство. Доказательство конструктивно. (1) Начинаем с состояния {s 0 } (2) ?a i ? ? построим a i -ребро из {s 0 } во множество всех образов s 0 под действием a i (3) Для каждого построенного множества состояний {s i 1 , . . . , s i k } и каждого a i ? ? снова строим a i -ребро из первого множества в мно- жество всех состояний, достижимых хотя бы из одного состояния s i j , (j = 1, . . . , k). (4) Продолжаем применять шаг (3) до тех пор пока не закончим стро- ить новые состояниянаборы. (5) Каждое новое состояние, содержащее элемент F приемное со- стояние нового автомата. Задачи 1. Которые из слов принимаются автоматом? a) abba. b) aabbb. c) babab. d) aaabbb. e) bbaab. 2. Найти язык, принимаемый автоматом. a) 2.1. Детерминированные и недетерминированные автоматы 11 b) c) d) 3. Найти детерминированный автомат, принимающий язык a) aa ? bb ? cc ? ; b) (a ? ba ? ba ? b) ? ; c) (a ? (ba) ? bb ? a) ? ; d) (a ? b) ? (b ? a) ? 4. Найти недетерминированный автомат, принимающий язык a) aa ? bb ? cc ? ; b) (a ? b) ? (c ? b) ? (ac) ? ; c) (a ? b) ? (aa ? bb)(a ? b) ? ; d) ((aa ? b) ? bb ? a)ac ? 5. Построить детерминированный автомат, принимающий тот же язык, что и недетерминированный. a) b) 12 Глава 2. Автоматы c) d) 2.2 Теорема Клини Теорема 5. Язык L регулярен ? L язык, принимаемый автоматом. Доказательство. (?) Докажем сначала, что для любого конечного под- множества U = {a 1 , . . . , a n } ? ? определен автомат, принимающий U. s 1 s 2 // s 0 a 1 ?? a 2 77 a n '' · · · s n Построим теперь автомат, соответствующий конкатенации языков L 1 L 2 Пусть M 1 = (?, Q 1 , s 0 , ? 1 , F 1 ) , M 2 = (?, Q 2 , s 0 0 , ? 2 , F 2 ) . Построим M = (?, Q, s 00 0 , ?, F ) . Положим Q = Q 1 S Q 2 , s 00 0 = s 0 , F = F 2 . Если a(s i ) = s j ? ? 1 и s j 6? F 1 , то a(s i ) = s j ? ? . Если a(s i ) = s j ? ? 1 и s j ? F 1 , полагаем 2.2. Теорема Клини 13 a(s i ) = s j ? ? и a(s i ) = s 0 0 ? ? . Кроме того, ? 2 ? ? . Далее если s 0 ? F 1 , отождествим s 0 0 с s 0 Рассмотрим замыкание Клини L ? языка L. Пусть M = (?, Q, s 0 , ?, F ) Построим M 0 = (?, Q 0 , s 0 0 , ? 0 , F 0 ) для L ? . Положим Q 0 = Q S{s 0 0 } . Если a(s 0 ) = s j ? ? то a(s 0 0 ) = s j ? ? 0 . Также ? ? ? 0 . Если a(s 0 ) = s j ? ? , s j ? F , то a(s 0 ) = s 0 0 ? ? 0 Построим еще автомат L 00 = L S L 0 . Пусть M(L) = (?, Q, s 0 , ?, F ) , M (L 0 ) = (?, Q 0 , s 0 0 , ? 0 , F 0 ) . Положим Q 00 = Q S Q 0 S{s 00 0 } , F 00 = F S F 0 Далее ? S ? 0 ? ? 00 . Кроме того, добавим еще ребра вида: если a(s 0 ) = s j ? ? , то a(s 00 0 ) = s j ? ? 00 . Аналогично, если a(s 0 0 ) = s j ? ? 0 , то a(s 00 0 ) = s j ? ? 00 (?) Удаление промежуточных состояний и лишних ребер по прави- лам: 1. // s i a 1 ,a 2 ,...,a k // заменяем на // s i (a 1 ?a 2 ?···?a k ) ? // 2. // s i?1 a // s i b c // s i+1 заменяем на // s i?1 ab ? c // s i+1 3. // s i a 1 %% a 2 // a n FF s i+1 // заменяем на // s i a 1 ?a 2 ?···?a n // s i+1 // 4. // s i?1 a 1 ++ s i a 3 // a 2 ll s i+1 // заменяем на // s i?1 a 1 (a 2 a 1 ) ? a 3 // s i+1 // Таким образом, язык, определяемый данным автоматом объедине- ние регулярных языков, следовательно, регулярен. Задачи 1. Построить автомат для языка ? ? \ M (L) , если известен автомат M. 2. Построить автомат для языка L 1 T L 2 , если известны автоматы M 1 и M 2 3. Пусть язык L 1 задан автоматом Язык L 2 автоматом 14 Глава 2. Автоматы Построить автоматы для языков a) L 1 S L 2 ; b) L 1 L 2 ; c) L ? 1 , L ? 2 4. Пусть язык L 1 задан автоматом Язык L 2 автоматом Построить автоматы для языков a) L 1 S L 2 ; b) L 1 L 2 ; c) L ? 1 , L ? 2 5. Пусть язык L 1 задан автоматом Язык L 2 автоматом Построить автоматы для языков a) L 1 S L 2 ; 2.3. Минимальные детерминированные автоматы и синтаксические моноиды15 b) L 1 L 2 ; c) L ? 1 , L ? 2 2.3 Минимальные детерминированные авто- маты и синтаксические моноиды Определение 12. Детерминированный автомат M минимален если число состояний M меньше или равно числу состояний любого другого детерминированного автомата, принимающего тот же язык, что и M Приведем сначала конструкцию, основанную на языке данного авто- мата. Определение 13. Пусть ? алфавит, ? ? множество всех слов над ?, L ? ? ? . Тогда для языка L определен внутренний (минималь- ный) автомат M i : Состояния M i классы эквивалентности ?x ? ? ? [x] = {y ? ? ? |R(y) = R(x)} , где R(x) множество правых контек- стов, принимаемых x под действием L, а именно, R(x) = {v ? ? ? |xv ? L} . Символ a действует на состояние [x] по правилу [x]a = [xa], где xa = ?(x, a) . При этом стартовое состояние M i [?], а приемные состояния F = {[x]|x ? L}. Определение 14. Синтаксический моноид S языка L состоит из классов эквивалентности, определенных ?x ? ? ? [[x]] = {y ? ? ? |LR(y) = LR(x)} , где LR(x) множество двусторонних контекстов, принима- емых x под действием L. То есть, LR(x) = {(u, v) ? ? ? Ч ? ? |uxv ? L} Кроме того, на S корректно определена бинарная операция [[x]][[y]] = [[xy]] S моноид, то есть полугруппа с единицей [[1]] = [[?]]. Теперь рассмотрим процедуру получения минимального автомата из данного посредством схлопывания состояний. Шаг 1. Для каждой пары состояний {p, q} определим, существует ли строка, под действием которой только одно состояние из пары переходит в конечное. Если существует, пометим эту пару как неотождествимую. Шаг 2. Для каждой пары {p, q} из оставшихся непомеченными, и каж- дого символа b ? ? рассмотрим {?(p, b), ?(q, b)}. Если ?(p, b) 6= ?(q, b) и {?(p, b), ?(q, b)} помечена на предыдущем шаге, то и {p, q} тоже помеченная пара. Повторяем второй шаг до тех пор, пока не переберем все помечивае- мые пары. 16 Глава 2. Автоматы Получим отношение эквивалентности p ? q, если {p, q} непомечен- ная пара. Рассмотрим ? 0 = ?/ ? , F 0 = F/ ? , ? 0 ([p], a) = [?(p, a)] Теорема 6. Для регулярного языка L, внутренний и минимальный ав- томаты изоморфны. Доказательство. Пусть M = (?, Q, s 0 , ?, F ) минимальный автомат, полученный методом пометок, а M i = (?, Q i , [1], ? i , F i ) внутренний автомат. Определим f : Q ? Q i по правилу f ([x]) = {w ? ? ? |?(s 0 , w) ? [x]}. Тогда f ([x]) = {w ? ? ? |?(s 0 , w) = y, y ? [x]}. Пусть [x] = [y], тогда ?(x, u) ? F ? ?(y, u) ? F для u, v ? ? ? . Пусть f ([x]) = [w] , а f([y]) = ([w 0 ]) Тогда wu ? L ? w 0 u ? L (= F i ) . Следовательно, [w] = [w 0 ] , и f корректно определена. Пусть наоборот, f([x]) = f([y]), тогда wu ? L ? w 0 u ? L (= F i ) , где ?(s 0 , w) = x и ?(s 0 , w 0 ) = y . То есть, ?(x, u) ? F ? ?(y, u) ? F и [x] = [y]. Итак, f корректно определена и взаимно- однозначна. Покажем наконец, что f(? 0 ([x], a)) = ? i (f ([x]), a) , ? 0 ([x], a) = [?(x, a)], и ? i (f ([x]), a) = f ([x])a. Пусть w ? f([x]), тогда ?(s 0 , w) = x для x ? [x]. Пусть ?(x, a) = y ? [?(x, a)] = ? 0 ([x], a) и [y] = ? 0 ([x], a) . Так как ?(s 0 , wa) = y , f([y]) i = [wa] i = [w] i a = f ([x])a = [? i (f ([x]), a)] и, следовательно, f(? 0 ([x], a)) = ? i (f ([x]), a) Определение 15. Моноид перестановок детерминированного авто- мата M(L) = (?, Q, s 0 , ?, F ) образ гомоморфизма ? : ? ? ? T M , где T M подмоноид всех отображений Q ? Q. Положим ?a ? ?, ?(a) = a, a(s i ) = s j , если ?(a, s i ) = s j . Далее, ?a, b ? ?, ab = ab. Пример: 2.3. Минимальные детерминированные автоматы и синтаксические моноиды17 s 1 b a // s 0 a >> b s 3 a rr b xx s 2 a >> b LL Тогда a = s 0 s 1 s 2 s 3 s 1 s 2 s 3 s 3 , b = s 0 s 1 s 2 s 3 s 2 s 3 s 2 s 3 Теорема 7. Пусть M(?, Q, s 0 , ?, F ) минимальный детерминирован- ный автомат, а T M моноид перестановок M, тогда T M конечен. Доказательство. Каждый представитель T M отображение из Q в Q. Если Q состоит из n элементов, то существует не более n n различных функций из Q в Q. Следовательно, порядок M не больше n n Теорема 8. Синтаксический моноид регулярного языка L изоморфен моноиду перестановок минимального детерминированного автомата M, принимающего L. Доказательство. По определению синтаксического моноида, он пред- ставляет собой моноид перестановок внутреннего минимального детер- минированного автомата. Так как все минимальные автоматы, принима- ющие один и тот же язык, изоморфны, синтаксический моноид изомор- фен моноиду перестановок минимального автомата. Задачи 1. Найти минимальный автомат, принимающий тот же язык, что и данный. a) 18 Глава 2. Автоматы b) c) d) 2. Построить минимальный автомат, принимающий язык a) aa ? (b ? c) ; b) a(b ? c) ? bb ? ; c) (abc) ? (b ? c) ; d) (a ? bc)c(ab) ? 3. Найти синтаксический моноид языка, принимаемого автоматом a) b) 2.4. Лемма о накачке 19 c) d) 2.4 Лемма о накачке Лемма 1. (Лемма о накачке) Пусть L бесконечный регулярный язык. |