Теория конечных языков и автоматов. Курс лекций П. Н. Иваньшин 2
 Скачать 0.61 Mb.
|
|
, с использованием правил P , то S ? ? w по правилам P 0 . Если n = 1, то S ? w правило из P 0 , так как w = ?. Пусть n = k и S ? ? w вывод из k шагов. Пусть S ? A 1 A 2 A 3 . . . A m первый вывод, в котором A i ? N S T . Тогда S ? A 1 A 2 A 3 . . . A m ? ? w вывод S ? ? w По лемме 5 существуют выводы A i ? ? w i в ?, для i = 1, . . . , m, где w = w 1 w 2 . . . w m , причем в каждом выводе меньше k шагов. По индукции, если w i 6= ? , существуют выводы A i ? ? w i в ? 0 для i = 1, . . . , m (заметим, что если A i терминал, то A i = w i и A i ? ? w i содержит 0 шагов). Положим A 0 i = A i если w i 6= ? , и A 0 i = ? если w i = ? . Тогда S ? A 0 1 A 0 2 A 0 3 . . . A m вывод в ? 0 и S ? A 0 1 A 0 2 A 0 3 . . . A m ? ? w 1 A 0 2 A 0 3 . . . A 0 m ? ? w 1 w 2 A 0 3 . . . A 0 m ? ? . . . ? ? w 1 w 2 . . . w m вывод в ? 0 Определение 30. Тривиальное правило правило вида A ? B, A, B ? N Лемма 8. Если L(?) язык, порожденный грамматикой ? = (N, T, S, P ), не содержит ?, то существует такая грамматика ? 0 без ?-правил и тривиальных правил, что L(? 0 ) = L(?) Доказательство. Предположим сразу, что ? не содержит ?-правил по Лемме 7. Построим ? 0 удалив все тривиальные правила и для A 1 ? A 2 ? A 3 ? . . . ? A m ? ? B , где A i ? A i+1 тривиальные правила и B ? w, включим A 1 ? B По построению L(? 0 ) ? L(?) Докажем обратное включение. Пусть S ? ? w вывод в ?. По индук- ции по количеству применения тривиальных правил в выводе покажем, что существует вывод S ? ? w в ? 0 . Очевидно, что при отсутствии три- виальных правил этот вывод может быть осуществлен и в ? 0 . Пусть в выводе использовано k тривиальных правил. Допустим, что вывод w левый. Пусть S ? ? w имеет вид S ? ? V 1 A 1 V 2 ? w 1 A 1 V 2 ? w 1 A 2 V 2 ? w 1 A 3 V 2 ? . . . ? w 1 A m V 2 ? ? w 1 w 0 V 2 ? w 1 w 0 w 2 , где A 1 ? A 2 ? A 3 ? . . . ? A m последняя последовательность тривиальных правил в выводе и A m ? w 0 . Тогда существуют выводы V 1 ? ? w 1 , V 2 ? ? w 2 в ? и вывод S ? ? V 1 A 1 V 2 ? ? w 1 A 1 V 2 ? w 1 w 0 V 2 ? ? w 1 w 0 w 2 34 Глава 3. Грамматики содержит меньше тривиальных правил, причем все правила правила P S P 0 . Следовательно, по гипотезе индукции, определен вывод S ? ? w в ? 0 Лемма 9. Если язык L(?), порожденный грамматикой ? = (N, T, S, P ), не содержит ?, то существует такая грамматика ? 0 = (N, T, S, P 0 ) , в которой каждое правило имеет вид либо A ? A 1 A 2 A 3 . . . A m для n ? 2, где A, A 1 , A 2 , A 3 . . . , A m ? N , либо A ? a, где A ? N, a ? T , что L(?) = L(? 0 ) Доказательство. Пусть мы уже удалили все ?-правила и тривиальные правила. Следовательно, оставшиеся элементы P имеют вид A ? A 1 A 2 A 3 . . . A m , где m ? 2 и A i ? N S T или A ? a, где A ? N, a ? T . Если A 1 , A 2 , A 3 , . . . , A m ? N , то правило имеет нужный нам вид. Предположим обратное, тогда для каждого символа A i = a i , a i ? T , введем новый нетерминал X a i . За- меним правило A ? A 1 A 2 A 3 . . . A m на A ? A 0 1 A 0 2 A 0 3 . . . A 0 m , где A 0 i = A i , если A i ? N , и A i = X a i , если A i ? T . Следовательно, строку V 1 a 1 V 2 a 2 V 3 a 3 . . . V n a n V n+1 , где V i ? N ? , и a i ? T , заменяем строкой V 1 X a 1 V 2 X a 2 V 3 X a 3 . . . V n X a n V n+1 и добавляем правила X a i ? a i для 1 ? i ? n. Пусть ? 0 = (N, T, S, P 0 ) новая грамматика. Докажем, что L(?) = L(? 0 ) . L(?) ? L(? 0 ) поскольку A ? V 1 a 1 V 2 a 2 V 3 a 3 . . . V n a n V n+1 в ? можно заменить на A ? V 1 X a 1 V 2 X a 2 V 3 X a 3 . . . V n X a n V n+1 ? V 1 a 1 V 2 X a 2 V 3 X a 3 . . . V n X a n V n+1 ? V 1 a 1 V 2 a 2 V 3 X a 3 . . . V n X a n V n+1 ? V 1 a 1 V 2 a 2 V 3 a 3 . . . V n a n V n+1 в ? 0 Пусть теперь в выводе S ? ? w 1 ww 2 , где U ? ? w 1 , A ? ? w и V i ? v i правила ? S ? ? U AU ? U V 1 X a 1 V 2 X a 2 . . . V n X a n V n+1 V ? ? w 1 v 1 a 1 v 2 a 2 v 3 a 3 . . . v n a n v n+1 w 2 = w 1 ww 2 , где A ? V 1 X a 1 V 2 X a 2 . . . V n X a n V n+1 3.2. Нормальные формы Хомского и Грейбаха 35 правило ? 0 , но не ?, и вывод выглядит следующим образом: S ? U AV ? ? w 1 AV ? w 1 V 1 X a 1 V 2 X a 2 . . . V n X a n V n+1 V ? ? w 1 v 1 X a 1 V 2 X a 2 . . . V n X a n V n+1 V ? w 1 v 1 a 1 V 2 X a 2 . . . V n X a n V n+1 V ? ? w 1 v 1 a 1 v 2 X a 2 . . . V n X a n V n+1 V ? w 1 v 1 a 1 v 2 a 2 V 3 X a 3 . . . V n X a n V n+1 V ? w 1 v 1 a 1 v 2 a 2 v 3 a 3 . . . v n a n V n+1 V ? ? w 1 v 1 a 1 v 2 a 2 v 3 a 3 . . . v n a n v n+1 V ? ? w 1 ww 2 Заменим его на S ? ? U V 1 a 1 V 2 a 2 . . . V n a n V n+1 V ? ? w 1 V 1 a 1 V 2 a 2 . . . V n a n V n+1 V ? ? w 1 v 1 a 1 V 2 a 2 . . . V n a n V n+1 V ? ? w 1 v 1 a 1 v 2 a 2 . . . a n V n+1 V ? ? w 1 v 1 a 1 v 2 a 2 . . . a n v n+1 V ? ? w 1 v 1 a 1 v 2 a 2 . . . a n v n+1 w 2 ? ? w 1 ww 2 Таким образом, мы получили вывод S ? ? w 1 ww 2 в ?. Следовательно, L(? 0 ) ? L(?) Лемма 10. (Нормальная форма Хомского) Если язык L(?), порожден- ный грамматикой ? = (N, T, S, P ), не содержит ?, то существует грамматика ? 0 , в которой каждое правило имеет вид либо A ? BC, либо A ? a, где A, B, C ? N, a ? T , и L(?) = L(? 0 ) 36 Глава 3. Грамматики Доказательство. По лемме 9, можем считать, что каждое правило ? имеет вид либо A ? A 1 A 2 A 3 . . . A m , A, A 1 , A 2 , A 3 , . . . , A m ? N либо A ? a , A ? N, a ? T . Построим ? 0 , заменив правила вида A ? A 1 A 2 A 3 . . . A m на множество правил A ? A 1 X 1 , X 1 ? A 2 X 2 , . . ., X m?2 ? A m?1 A m , где каждая замена правила использует новое множество символов. Вывод A ? A 1 X 2 ? A 1 A 2 X 3 ? ? A 1 A 2 A 3 . . . A m в ? 0 влечет L(?) ? L(? 0 ) Если вывод S ? ? w в ? 0 использует правила только из ?, то w ? L(? 0 ) Пусть используются еще и правила из ? 0 , и W m последняя строка в выводе, содержащая символ не из ?, то есть W m ? W m+1 ? ? w , и W m ? W m+1 имеет вид UX m?2 V ? U A m?1 A m V . Следовательно, вывод использует множество правил A ? A 1 X 1 , X 1 ? A 2 X 2 , . . ., X m?2 ? A m?1 A m и представляется в виде S ? ? U AV ? ? U A 1 X 1 V ? ? ? ? U A 0 1 X 1 V ? ? U A 0 1 A 0 2 X 2 V ? ? ? ? U A 0 1 A 0 2 X 2 V ? ? U A 0 1 A 0 2 A 3 X 3 V ? ? ? ? U A 0 1 A 0 2 A 0 3 X 3 V ? ? ? ? U A 0 1 . . . A m?2 X m?2 V ? ? U A 0 1 · · · A 0 m?2 X m?2 V ? ? w ? W m+1 , где U 0 = U A 0 1 A 0 2 A 0 3 · · · A 0 m?2 и A i ? ? A 0 i вывод ?. Если вывод S ? ? w все еще не вывод ?, снова рассмотрим последнюю строку вывода, содержа- щую символ из ? 0 \? , и продолжим этот процесс до тех пор пока не исклю- чим все подобные подстроки. Таким образом, w ? ? и L(? 0 ) ? L(?) Определение 31. Пусть теперь L(?) содержит ?. Добавим к ? 0 два нетерминала S 0 и ?, где S 0 новый стартовый символ и правила S 0 ? S? и ? ? ?. Полученная грамматика называется грамматикой в ? -дополненной форме Хомского. Теорема 18. Пусть дана контекстно-свободная грамматика ?, содер- жащая ?, тогда существует такая контекстно-свободная грамматика в ?-дополненной форме Хомского ? 0 , что L(?) = L(? 0 ) Определение 32. Удаление левой рекурсии удаление правил вида A ? Aa Пусть в грамматике ? без ?-правил A ? AV 1 , A ? AV 2 , . . . , A ? AV n 3.2. Нормальные формы Хомского и Грейбаха 37 есть множество всех правил, правая часть которых начинается с A. Пусть A ? U 1 , A ? U 2 , . . . , A ? U m ? остальные правила. Построим грамматику ? 0 добавив новый нетерминал A 0 и осуще- ствив следующее: 1) Удалим все правила вида A ? AV i для 1 ? i ? n. 2) Введем новые правила A ? U i A 0 для 1 ? i ? n. 3) Введем новые правила A 0 ? V i A 0 и A 0 ? V i Лемма 11. L(? 0 ) = L(?) Доказательство. Пусть правило, начинающееся с A, имеет вид A ? U i A для 1 ? i ? n, и A ? AV (1) ? AV (2) V (1) ? ? AV (k) . . . V (2) V (1) ? U (i) V (k) . . . V (2) V (1) , где V (j) ? {V 1 , V 2 , . . . , V n } для все 1 ? j ? k и U (i) ? {U 1 , U 2 , . . . , U m } . следовательно, используя левый вывод, каждый вывод, содержащий A имеет вид wAW ? wAV (1) W ? wAV (2) V (1) W ? ? ? ? wAV (k) . . . V (2) V (1) W ? wU (i) V (k) . . . V (2) V (1) W. Но A ? AV (1) ? AV (2) V (1) ? ? ? ? AV (k) . . . V (2) V (1) ? U (i) V (k) . . . V (2) V (1) можно заменить на A ? U (i) A 0 ? U (i) V (k) A 0 ? U (i) V (k) V (k ? 1)A 0 ? ? ? ? U (i) V (k) . . . V (2) A 0 ? U (i) V (k) . . . V (2) V (1) Приписав w слева, а W справа от каждой строки в выводе, получим wAW ? ? wU (i) V (k) . . . V (2) V (1) W в ? 0 . Следовательно, L(?) ? L(? 0 ) Доказательство L(? 0 ) ? L(?) аналогично. Лемма 12. Пусть A ? UBV правило грамматики ? и B ? W 1 , B ? W 2 , . . ., B ? W m множество всех правил с B слева. Пусть ? 0 грамматика без правила A ? UBV , но с добавленными правилами A ? U W i V для 1 ? i ? m, тогда L(?) = L(? 0 ) Доказательство. Правило A ? UW i V всегда можно заменить на пра- вило A ? UBV , которое предшествует правилу B ? W i . Следовательно, L(? 0 ) ? L(?) Обратное включение доказывается аналогично. 38 Глава 3. Грамматики Лемма 13. (Нормальная форма Грейбаха) Любая контекстно-свободная грамматика, непорождающая ? может быть выражена так, что каж- дое правило вывода имеет вид A ? aW, где a ? T , а W строка, которая либо пуста, либо состоит из тер- миналов и/или нетерминалов. Доказательство. Пронумеруем все нетерминалы, начиная со стартового символа S. Обозначим все нетерминалы через A 1 , A 2 , A 3 , . . . , A m . Наша первая цель изменить каждое правило так, чтобы оно приняло вид 1)A ? aW, где a ? T , а W строка, которая либо пуста, либо состоит из терминалов и/или нетерминалов, или 2)A i ? A j Y, где i < j, а Y строка, которая состоит из терминалов и/или нетермина- лов. Напомним, что процедуры удаления левой рекурсии и нетерминалов из лемм 11, 12 не меняют языка грамматики. По индукции, для i = 1, поскольку S = A 1 автоматически имеет мень- ший порядковый номер, чем любой другой нетерминал, нужно рассмот- реть только S ? SY . Тогда S справа от ? можно удалить по правилу удаления левой рекурсии. Пусть утверждение верно для A i , i < k. До- кажем его для i = k. В каждом случае A k ? A j Y правило для k > j, используем процедуру из леммы 12 для удаления A j . Если A k ? A k Y правило, воспользуемся правилом из леммы 11 для удаления A k с правой стороны. Итак, можем считать, что каждое правило представлено в одном из следующих двух видов: 1)A ? aW, где a ? T , а W строка, которая либо пуста, либо состоит из терминалов и/или нетерминалов, или 2)A i ? A j Y, где i < j, а Y строка, которая состоит из терминалов и/или нетерми- налов. Каждое правило с A m слева должно иметь вид A m ? aW , посколь- ку нет нетерминалов с номером, большим m. Если нет правил вида A m?1 ? A m W 0 , воспользуемся процедурой Леммы 12 для удаления A m В результате получим правило в виде A m ? bW 00 . Пусть k наибольшее 3.2. Нормальные формы Хомского и Грейбаха 39 из таких чисел, что A k ? A j Y правило, для которого k < j. Снова применив Лемму 12 для удаления A j , получим правило типа A k ? aW После завершения этого процесса, получим A i ? aW, где a ? T , а W строка, которая либо пуста, либо состоит из терминалов и/или нетерминалов для каждого i. Рассмотрим теперь нетерминалы B i , полученные при применении Леммы 11. По построению B i , не существует правил вида B i ? B j W . Следовательно, правила с B i слева от ? имеют тип либо B i ? aW , либо B i ? A j W . Повторяя уже приведенный выше процесс, получим правила вида B i ? aW Теорема 19. Каждая контекстно-свободная грамматика ?, язык ко- торой не содержит ? может быть представлена в нормальной форме Грейбаха. Доказательство. Каждое правило может быть представлено в виде A ? aW, где a ? T , а W строка, которая либо пуста, либо состоит из терми- налов и/или нетерминалов. Далее каждый терминал b в W заменим на нетерминал A b и добавим правила A b ? b Определение 33. Для каждой контекстно-свободной грамматики, со- держащей ?, построим грамматику в расширенной нормальной фор- ме Грейбаха, принимающей пустое слово, просто добавив правило S ? ? после применения процедур из предыдущей леммы. Задачи 1. Пусть ? = (N, T, S, P ) грамматика, для которой N = {S, A, B}, T = {a, b} , а P состоит из правил S ? ABABABA, A ? Aa, A ? ?, B ? b. a) Найти нормальную форму Хомского ?. b) Найти нормальную форму Грейбаха ?. 2. Пусть ? = (N, T, S, P ) грамматика, для которой N = {S, A, B}, T = {a, b} , а P состоит из правил S ? SS, B ? aa, S ? BS, B ? bb, S ? SB, 40 Глава 3. Грамматики A ? ab, S ? ?, A ? ba, S ? ASA. a) Найти нормальную форму Хомского ?. b) Найти нормальную форму Грейбаха ?. 3. Пусть ? = (N, T, S, P ) грамматика, для которой N = {S, A, B}, T = {a, b} , а P состоит из правил S ? AbaB, A ? bAa, A ? ?, B ? AAb, B ? aabA. a) Найти нормальную форму Хомского ?. b) Найти нормальную форму Грейбаха ?. 3.3 Автоматы с магазинной памятью Определение 34. Автомат с магазинной памятью (PDA-автомат) набор M = (?, Q, s, I, ?, F ), где ? конечный алфавит, Q конечное множество состояний, s начальное или стартовое состояние, I алфавит памяти (магазина), ? функция перехода ? ? ((? S{?} Ч Q Ч I S{?}) Ч (Q Ч I S{?})), F множество приемных состояний. То есть ? прочитывает букву ? S{?}, определяет состояние, прочи- тывает букву I S{?}. Затем меняет или нет состояние, и выводит букву из I S{?}. Аналогично случаю обычного автомата, буква слова при про- чтении удаляется из слова. Последняя буква стека также удаляется при прочтении. Говорят, что она выводится из стека. Буква I, полученная с помощью ? записывается в стек. Слово принимается АМП, если и толь- ко если после прочтения этого слово начиная со стартового состояния и пустого стека, автомат переходит в конечное состояние и стек снова пуст. Язык, принимаемый M, обозначим L(M). Определение 35. M детерминированный автомат с магазин- ной памятью если ? ? ((? S{?} Ч Q Ч I S{?}) Ч (Q Ч I S{?})) имеет следующее свойство: если ((s, a, c), (s 0 , c 0 )) и ((s, a, c), (s 00 , c 00 )) ? F , то s 0 = s 00 и c 0 = c 00 Пример: 3.3. Автоматы с магазинной памятью 41 Работа этого автомата при обработке строки abba Действие Стек Лента Start (начало) ? abba read (ввод) ? bba push (запись в стек) a a bba resd (ввод) a ba pop (вывод) ? ba read (ввод) ? a push (запись в стек) b b a read (ввод) b ? pop (вывод) ? ? accept (прием) ? ? Теорема 20. Язык контекстно-свободной грамматики ? язык неко- торого автомата с магазинной памятью. Доказательство. Доказательство конструктивно. Построим автомат по данной грамматике. 1. Начинаем с автомата записи в стек S. 2. Если нетерминал A выводится из стека, то для некоторого правила A ? w в ?, w записывается в стек, то есть строим автомат 42 Глава 3. Грамматики 3. Если терминал a выводится из стека, то этот же символ должен быть прочитан, то есть строим автомат Пример: Пусть ? = (N, T, S, P ) грамматика N = {S}, T = {a, b}, и P состоит из правил S ? aSa, S ? bSb, S ? ?. Соответствующий этой грамматике автомат: 3.4. Контекстно-свободные языки и лемма о накачке 43 Задачи 1. Построить автомат с магазинной памятью, принимающий язык: по- рожденный грамматикой ? = (N, T, S, P ), где N = {S, A, B}, T = {a, b, c}, и P состоит из правил a) S ? aA, A ? aAB, A ? a, B ? bB ? ?. b) S ? AB, A ? abaA, A ? ?, B ? Bcacc, B ? ?. c) S ? AcB, A ? abaA, A ? ?, B ? Bcacb, B ? ?. d) S ? AB, A ? acA, B ? bcB, B ? bB, A ? aAa, B ? ?, A ? ?. e) S ? AB, A ? aAc, B ? bBc, B ? bB, A ? AaA, B ? ?, A ? ?. 3.4 Контекстно-свободные языки и лемма о накачке Определение 36. Пусть ? контекстно-свободная грамматика, на- зовем язык L(?) контекстно-свободным. Предположим, что грамматика ? представлена в нормальной форме Хомского. |