Теория конечных языков и автоматов. Курс лекций П. Н. Иваньшин 2
 Скачать 0.61 Mb.
|
|
Лемма 14. Пусть A ? ? w , где A ? N, и высота соответствующего дерева разбора с корнем A равна n. Тогда длина w не больше 2 n?1 Доказательство. Индукция по высоте дерева разбора. Если n = 1, то вывод имеет вид A ? a, и длина w = a равна 1 = 2 0 . Пусть утверждение верно для n = k. Рассмотрим вывод A ? ? w с деревом разбора высоты k + 1 . Тогда A ? BC ? ? uv = w , где B ? ? u , C ? ? v и дерево разбора для двух последних выводов имеет высоту k. То есть, по предположению индукции, строки u и v имеют длину не больше 2 k?1 . Значит w длины не больше 2 · 2 k?1 = 2 k = 2 (k+1)?1 44 Глава 3. Грамматики Теорема 21. (Лемма о накачке) Пусть L контекстно-свободный язык. Тогда существует такое число M ? N, что любое слово длин- нее M в L представимо в форме xuvwy, где uw 6= ?, |uvw| ? M, и xu n wv n y ? L для всех n ? 0. Доказательство. Пусть L \ {?} непустой язык, порожденный грам- матикой ? = (N, T, S, P ) в нормальной форме Хомского, причем |P | = p. Положим M = 2 p . Пусть существует слово w ? L длины не меньше M. Тогда по предыдущему утверждению, соответствующее дерево разбора выше p. Следовательно, в дереве разбора существует путь S ? · · · ? a, где a буква, длины больше p, и a ? w. Поскольку ? содержит только p различных правил, некоторые нетерминалы встречаются в правилах вывода w слева чаще одного раза. Пусть C первый такой нетерминал. Тогда определен вывод S ? ? ?C? ? ? xuCvy ? ? xuwvy, где ? ? ? x , ? ? ? y , C ? ? uCv и C ? w. Однако, используя эти выводы мы можем получить вывод S ? xuCvy ? ? xuuCvvy ? ? xu n wv n y для каждого n ? N \ {0}. Так как первое правило вывода имеет вид C ? AB ? ? uCv , и нет пустых слов, либо u либо v непусто. Зафиксируем букву a в слове uwv; можно пройти от нее обратно до S по дереву разбора использую по од- ному разу выводы C ? ? uCv и C ? w. Следовательно, длина этого пути не больше p, значит |uwv| ? M. Следствие 1. Язык L = {a m b m a m |m ? 1} не контекстно-свободный язык. Доказательство. Пусть m настолько велико, что длина a m b m a m больше M . Тогда a m b m a m = puqvr , где pu n qv n r ? L , для всех n ? 1. Пусть либо u, либо v, либо оба u и v содержат и a и b, то (a i b j ) n должно быть подсловом pu n qv n r , что невозможно. Следовательно, u и v состоят целиком из a или b . Обе эти строки на могут быть одинаковыми, иначе при возведении их в степень количество одних букв будет расти, а других не изменится. Следовательно, u состоит из a, v из b. С другой стороны, u состоит из a в начале каждого слова a m b m a m , а v из a в конце каждого такого же слова, полученное противоречие доказывает утверждение. Теорема 22. Множество контекстно-свободных языков замкнуто от- носительно операций конкатенации, объединения и замыкания Клини. 3.4. Контекстно-свободные языки и лемма о накачке 45 Доказательство. Пусть L 1 и L 2 порождены грамматиками ? 1 = (N 1 , T 1 , S 1 , P 1 ) и ? 2 = (N 2 , T 2 , S 2 , P 2 ) , соответственно. Пусть N 1 и N 2 различны. Этого всегда можно добиться переименованием букв. Язык L 1 L 2 можно представить как язык, порожденный грамматикой ? = (N, T, S, P ) , где N = N 1 S N 2 S{S} , T = T 1 S T 2 , а P = P 1 S P 2 S{S ? S 1 S 2 } . Если u ? L 1 , v ? L 2 , то S 1 ? ? u в ? 1 , S 2 ? ? v в ? 2 , и применяя левый вывод, получим S ? S 1 S 2 ? ? uS 2 ? ? uv в ?. Язык L 1 S L 2 порожден грамматикой ? = (N, T, S, P ), где N = N 1 S N 2 S{S} , T = T 1 S T 2 , и P = P 1 S P 2 S{S ? S 1 , S ? S 2 } . Пусть w ? L 1 S L 2 . Тогда w ? L 1 или w ? L 2 . Если w ? L 1 , то S 1 ? ? w в ? 1 , и S ? S 1 ? ? w в ?. Если w ? L 2 , то S 2 ? ? w в ? 2 , и S ? S 2 ? ? w в ?. Язык L ? 1 порожден грамматикой ? = (N, T, S, P ), где N = N 1 S{S} , T = T 1 , и P = P 1 S P 2 S{S ? S 1 S, S ? ?} . Пусть w 1 , w 2 , w 3 , . . . , w n ? L 1 Теперь используя правила S ? S 1 S и S ? ?, мы получаем вывод S ? ? S n 1 = S 1 S 1 S 1 · · · S 1 . Дальше левыми выводами получаем S ? ? S 1 S 1 S 1 · · · S 1 ? ? w 1 S 1 S 1 · · · S 1 ? ? w 1 w 2 S 1 · · · S 1 ? ? w 1 w 2 · · · w n в ?. Сле- довательно, L ? 1 = L Теорема 23. Множество контекстно-свободных языков незамкнуто относительно операций пересечения и дополнения. Доказательство. Достаточно рассмотреть языки {a n b n a m |m, n ? 0} и {a n b m a m |m, n ? 0} . Первый порожден грамматикой с правилами P = {S ? BC, B ? aBb, B ? ?, C ? aC, C ? ?} , второй P = {S ? AB, A ? aA, A ? ?, B ? bBa, B ? ?} Теорема 24. Пересечение регулярного и контекстно-свободного языков контекстно-свободный язык. Доказательство. Пусть автомат с магазинной памятью M = (?, Q, s, I, ?, F ), где ? алфавит, Q множество состояний, s начальное состоя- ние, I множество стековых символов, F множество конечных со- стояний, ? функция перехода. Рассмотрим детерминированный ав- томат M 1 = (? 1 , Q 1 , q 0 , ? 1 , F 1 ) , где ? 1 алфавит, Q 1 множество со- стояний, q 0 начальное состояние, F 1 множество приемных состоя- ний, и ? 1 функция перехода. Определим автомат с магазинной па- мятью следующим образом: M 2 = (? 2 , Q 2 , s 2 , I 2 , ? 2 , F 2 ) , где s 2 = (s, q 0 ) , ? 2 = ? 1 S ? , I 2 = I , Q 2 = Q Ч Q 1 , и F 2 = F Ч F 1 . Определим ? 2 как (((s i , q j ), a, X), ((s m , q n ), b)) ? ? 2 ? ((s i , a, X), (s m , b)) ? ? и ? 1 (q j , u) = q n в M 1 . Строка w принимается M 2 ? ((s, q 0 ), w, ?) ` ? 2 ((s a , q b ), ?) ? M 2 , где s a и q b приемные состояния M и M 1 , соответственно. Таким образом, w принимается как автоматом с магазинной памятью M, так и регулярным автоматом M 1 46 Глава 3. Грамматики Определение 37. Нетерминал контекстно-свободной грамматики бес- полезен, если он не фигурирует ни в одном выводе S ? ? w , w ? ? ? Иначе, нетерминал полезен. Теорема 25. Для данной контекстно-свободной грамматики можно найти и удалить все бесполезные нетерминалы. Доказательство. Сначала удалим любой такой нетерминал U, что нет ни одного вывода ? ? w , w ? ? ? . Для этого, определим X по правилам: 1) Для каждого нетерминала V , такого что V ? w правило для w ? ? ? , положим V ? X. 2) Если V ? V 1 V 2 · · · V n , где V i ? X или ? ? для 1 ? i ? n, опять V ? X Продолжим применять 2) до тех пор пока не прекратим добавлять новые нетерминалы к X. Каждый нетерминал U, не принадлежащий X не имеет ни одного вывода вида U ? ? w . Если S 6? X, то язык, порож- денный данной контекстно-свободной грамматикой, пуст и доказатель- ство закончено. Нет ни одного полезного терминала. Пусть S ? X. Все правила, содержащие нетерминала не из X удалим из множества P . Удалим теперь каждый нетерминал U, недостижимый из S, т.е. нет ни одного вывода S ? ? W , в котором U элемент строки W . Для каждого нетерминала U построим множество Y U : 1) Если V ? W и U элемент строки W , то V ? Y U 2) Если R ? T , где элемент Y U присутствует в строке T , то R ? Y U Продолжим применять 2) до тех пор пока не закончим добавлять нетерминалы к Y U . Если S ? Y U , то U достижим из S. Иначе, U недо- стижим из S. Удалим все правила, содержащие нетерминалы, недости- жимые из S. Теорема 26. Существует алгоритм определения того, является ли данный контекстно-свободный язык L пустым Доказательство. Контекстно-свободный язык L пуст ? L не содержит полезных терминалов. Теорема 27. Пусть даны w ? ? ? , и контекстно-свободная грамматика G . Тогда существует алгоритм определения принадлежит ли w L(G). Доказательство. Пусть G представлена в нормальной форме Хомского. Пусть длина w равна n ? 1. Вывод S ? ? w имеет длину k ? 2 n?1 , поскольку G в нормальной форме Хомского. Следовательно, достаточно проверить все выводы длины k ? 2 n?1 3.4. Контекстно-свободные языки и лемма о накачке 47 Теорема 28. Пусть G контекстно-свободная грамматика в нор- мальной форме Хомского с p правилами. Язык L(G) бесконечен ? су- ществует такая строка ? ? L(G), что 2 p < |?| < 2 p+1 Доказательство. Пусть существует слово длины больше 2 p , тогда по Лемме о накачке, L(G) бесконечен. Иначе, пусть ? кратчайшее слово длины большей 2 p+1 . По Лемме о накачке, ? = xu i wv i y , где длина uvw ? 2 p и µ = xu i?1 wv i?1 y ? L(G) . Но |µ| > |?| ? |uv| ? 2 p . Также |µ| < |?| и w кратчайшее слово длины не меньше 2 p+1 . Следовательно, |µ| < 2 p+1 Задачи 1. Пусть грамматика ? = (N, T, S, P ) состоит из N = {S, A, B}, T = {a, b, c} , и P состоит из правил S ? AB, A ? acA, B ? bcB, B ? bB, A ? aBa, B ? ?, A ? a. Построить грамматику, порождающую L ? 2. Пусть L 1 язык, порожденный грамматикой ? 1 = (N, T, S, P 1 ) , где N = {S, A, B} , T = {a, b, c}, и P 1 состоит из правил S ? aA, A ? aAB, A ? a, B ? b, B ? ?, а L 2 язык, порожденный грамматикой ? 2 = (N, T, S, P 2 ) , где N = {S, A, B} , T = {a, b, c}, и P 2 состоит из правил S ? AB, A ? abaA, A ? ?, B ? Bcacc, B ? ?. Найти грамматику, порождающую L 1 L 2 3.Пусть L 1 язык, порожденный грамматикой ? 1 = (N, T, S, P ) , где N = {S, A, B} , T = {a, b, c}, и P 1 состоит из правил S ? AdB, A ? abaA, A ? ?, B ? Bcacb, B ? ?, а L 2 язык, порожденный грамматикой ? 2 = (N, T, S, P 2 ) , где N = {S, A, B} , T = {a, b, c}, и P 2 состоит из правил S ? AB, A ? acA, B ? bcB, B ? bB, A ? aAa, B ? ?, A ? ?. Найти грамматику, порождающую L 1 S L 2 48 Глава 3. Грамматики 4. Является ли язык контекстно-свободным? Если да, то построить грамматику, порождающую его. a) L = {a m b n c 2n |m, n = 1, 2, . . .} b) L = {ww R w|w ? a, b ? } c) L = {w ? {a, b, c} ? |w состоит из одинакового числаaиb}. d) L = {a n b 2n c n |n = 1, 2, . . .} Глава 4 Машина Тьюринга 4.1 Детерминированная машина Тьюринга Определение 38. Детерминированная машина Тьюринга набор (Q, ?, ?, ?, s 0 , h) , где Q множество состояний, ? конечное множество символов на ленте, включающее в себя алфавит ? и символ пустой ячейки ], s 0 начальное состояние, h конечное состояние, ? функция из Q Ч ? в Q Ч ? Ч N, где N состоит из L, что озна- чает переход к левой ячейке от рассматриваемой, R к правой и ] отсутствие перехода. Определение 39. Слово w ? ? ? принимается машиной Тьюрин- га T если, начиная со стартового состояния по прочтении w маши- на переходит в конечное. Язык, принимаемый машиной Тьюринга T множество всех таких слов. Представим правило (s i , a, s j , b, R) как s i a (b,R) (( s j Теорема 29. Любой регулярный язык распознается некоторой маши- ной Тьюринга. Пример: Автомату 49 50 Глава 4. Машина Тьюринга s 1 a b // s 0 a 88 b && s 3 s 2 b UU a DD Соответствует машина Тьюринга s 1 a (a,R) UU b (b,R) // s 0 a (a,R) 99 b (b,R) %% ] (],]) s 3 ] (],]) ++ ] s 2 b (b,R) UU a (a,R) DD Определение 40. Языки, принимаемые машинами Тьюринга называ- ются рекурсивно-перечислимыми. Примеры: 1. Построим машину Тьюринга, описывающую язык {a n b n |n ? N \ {0}}. Прочитываем первую букву a, меняем ее на A: (s 0 , a, s 1 , A, R) Прочитываем все a пока не встретим букву b, которую заменим на B и повернем назад: (s 1 , a, s 1 , a, R), (s 1 , B, s 1 , B, R), (s 1 , b, s 2 , B, L). Возвращаясь ко второй a, проходим через все B и a, не меняя их: (s 2 , B, s 2 , B, L), (s 2 , a, s 2 , a, L). 4.1. Детерминированная машина Тьюринга 51 После встречи A снова идем по слову вперед (s 2 , A, s 0 , A, R). Пусть процесс считывания a закончен (s 0 , B, s 3 , B, R). В состоянии s 3 не воспринимаем ничего, кроме B и ]: (s 3 , B, s 3 , B, R), (s 3 , ], h, ], ]). s 1 a (a,R) B (B,R) b (B,L) 33 s 2 a (a,L) B (B,L) ff A (A,R) kk // s 0 a (A,R) 88 B (B,R) %% s 2 B (B,R) UU ] (],]) ,, h 2. Аналогично строится машина Тьюринга для языка {a n b n c n |n ? N \ {0}}. s 1 a (a,R) B (B,R) b (B,L) ++ s 2 b (b,R) C (C,R) dd c (C,L) kk // s 0 a (A,R) 77 B (B,R) && s 3 B (B,L) RR b (b,L) 33 a (a,L) ++ C (C,L) ss A (A,R) oo s 2 B (B,R) LL C (C,R) kk ] (],]) ++ h Задачи 1. Построить машину Тьюринга, принимающую язык a) ab ? c ? (b ? ac) ; b) abc(b ? ac) ? b ; c) (aa ? bb ? ) ? 2. Построить машину Тьюринга, принимающую строки, состоящие из одинакового количества a и b. 52 Глава 4. Машина Тьюринга 3. Построить машину Тьюринга, которая по введенной строке печа- тает ее в обратном порядке. 4. Построить машину Тьюринга, принимающую все четные палин- дромы. 5. Построить машину Тьюринга, принимающую все нечетные палин- дромы. 6. Построить машину Тьюринга, принимающую все строки вида a n b n a n , n ? N \ {0}. 7. Построить машину Тьюринга, принимающую строки вида ww, w ? {a, b} ? 4.2 Недетерминированные машины Тьюрин- га и контекстно-свободные языки Определение 41. Машина Тьюринга недетерминированная, если ? конечное подмножество (Q Ч ?) Ч (Q Ч ? Ч N). Теорема 30. Любой контекстно-свободный язык принимается некото- рой недетерминированной машиной Тьюринга. Доказательство. Для каждого из правил автомата с магазинной памя- тью построим соответствующую команду машины Тьюринга. 1. ((a, s, E), (t, D)) В состоянии s, прочитываем a, выводим E, пе- реходим в состояние t и перемещаем в стек D. 2. ((a, s, ?), (t, D)) В состоянии s, прочитываем a, переходим в со- стояние t и перемещаем в стек D. 3. ((?, s, ?), (s, D)) В состоянии s перемещаем в стек D. 4. ((a, s, E), (t, ?)) В состоянии s, прочитываем a, выводим E и пе- реходим в состояние t. 5. ((?, s, E), (s, ?)) В состоянии s выводим E. 6. ((a, s, ?), (t, ?)) В состоянии s, прочитываем a и переходим в со- стояние t. 7. ((a, s, ?), (s, ?)) В состоянии s, прочитываем a. 1. Переходим в первую ячейку после O, стираем E и вписываем D. Возвращаемся к a и стираем a. Переходим в состояние t. 2. Переходим в первую ячейку после O, вписываем D. Возвращаемся к a и стираем a. Переходим в состояние t. 3. Переходим в первую ячейку после O, вписываем D. Возвращаемся к первоначальной букве. Переходим в состояние s. 4. Переходим в первую ячейку после O, стираем E. Возвращаемся к a и стираем a. Переходим в состояние t. 4.2. Недетерминированные машины Тьюринга и контекстно-свободные языки53 5. Переходим в первую ячейку после O, стираем E. Возвращаемся к первоначальной ячейке. Переходим в состояние s. 6. Стираем a. Переходим в состояние t. 7. Стираем a. Переходим в состояние s. Теорема 31. Язык, принимаемый недетерминированной машиной Тью- ринга T , принимается и детерминированной машиной Тьюринга T 0 Доказательство. Поскольку T недетерминированна, и ?(s, x) ? (QЧ?Ч N ) , ?(s, x) состоит из k элементов, которые обозначим через ? 0 (s, x), ? 1 (s, x), ? 2 (s, x), . . . , ? k?1 (s, x). Таким образом, каждый элемент ? i (s, x) корректно определен. Напри- мер, для ? 0 (s, x) = (s 0 , b, R) получим правило (s, x, s 0 , b, R) , и для ? 1 (s, x) = (s 00 , C, L) имеем правило (s, x, s 00 , C, L) Пронумеруем элементы каждого ?(s i , a i ) для всех состояний s i и каж- дого a i ? ? . Следовательно, если мы находимся в состоянии s, получа- ем ввод x, и номер j, мы можем воспользоваться ? j (s, x) для упроще- ния используемого правила. Пусть нам никогда не потребуется больше n + 1 числа для нумерации элементов ?(s i , a i ) , тогда для любой после- довательности натуральных чисел m 1 , m 2 , . . . , m p , каждое из которых не больше n, мы можем последовательно применить ? m 1 , ? m 2 |