dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 70
Текст из файла (страница 70)
Тогда B порож**дает некоторый префикс строки aiai+1…aj, скажем, B ⇒ aiai+1…ak для некоторого k < j.*Кроме того, C порождает остаток aiai+1…aj, т.е. C ⇒ ak+1ak+2…aj.312Стр. 312ÃËÀÂÀ 7. ÑÂÎÉÑÒÂÀ ÊÎÍÒÅÊÑÒÍÎ-ÑÂÎÁÎÄÍÛÕ ßÇÛÊÎÂПриходим к выводу, что для того, чтобы A попало в Xij, нужно найти переменные B иC и целое k, при которых справедливы следующие условия.1.i ≤ k < j.2.B принадлежит Xik.3.C принадлежит Xk+1, j.4.A → BC — продукция в G.Поиск таких переменных A требует обработки не более n пар вычисленных ранеемножеств: (Xii, Xi+1, j), (Xi, i+1, Xi+2, j) и т.д.
до (Xi, j–1, Xjj). Таким образом, мы поднимаемсяпо колонке, расположенной под Xij, и одновременно спускаемся по диагонали (рис. 7.13).Рис. 7.13. Вычисление Xij требует совместной обработки столбца под Xijи диагонали справа от негоТеорема 7.33. Вышеописанный алгоритм корректно вычисляет Xij для всех i и j. Таким образом, w ∈ L(G) тогда и только тогда, когда S ∈ X1n.
Кроме того, время выполнения алгоритма есть O(n3).Доказательство. Представив базис и индуктивную часть алгоритма, мы объяснили,почему алгоритм находит корректные множества переменных. Рассмотрим время выполнения. Заметим, что нужно вычислить O(n2) элементов таблицы, и каждое вычисление вовлекает сравнение и вычисление не более, чем n пар элементов. Важно помнить,что, хотя в каждом множестве Xij может быть много переменных, грамматика G зафиксирована и число ее переменных не зависит от n — длины проверяемой цепочки w. Таким образом, время сравнения элементов Xik и Xk+1, j и поиска переменных, входящих вXij, есть O(1).
Поскольку для каждого Xij возможно не более n таких пар, общее время составляет O(n3). Пример 7.34. Рассмотрим следующие продукции грамматики G в НФХ.S → AB | BCA → BA | aB → CC | bC → AB | a7.4. ÑÂÎÉÑÒÂÀ ÐÀÇÐÅØÈÌÎÑÒÈ ÊÑ-ßÇÛÊÎÂСтр. 313313Проверим, принадлежит ли цепочка baaba языку L(G). На рис.
7.14 показана таблица, заполненная для этой строки.Для построения первой (нижней) строки используется базисное правило. Нужно рассмотреть лишь переменные с телом продукции a (это A и C) и телом b (это B). Таким образом, X11 = X44 = {B}, X22 = X33 = X55 = {A, C}.Во второй строке показаны значения X12, X23, X34 и X45. Рассмотрим, например, каквычисляется X12. Цепочку ba, занимающую позиции 1 и 2, можно разбить на непустыеподцепочки единственным способом. Первая должна занимать позицию 1, вторая — позицию 2. Для того чтобы переменная порождала ba, она должна иметь продукцию с телом, первая переменная которого принадлежит X11 = {B} (т.е. порождает b), а вторая —X22 = {A, C} (т.е.
порождает a). Таким телом может быть только BA или BC. Просмотревграмматику, находим, что с такими телами там есть только продукции A → BA и S → BC.Таким образом, две головы, A и S, образуют X12.{S, A, C}-{S, A, C}-{B}{S, A}{B}{B}{A, C}{A, C}{B}{A, C}baaba{B}{S, C} {S, A}Рис. 7.14. Таблица для цепочки baaba, построенная алгоритмом Кока-Янгера-КасамиВ качестве более сложного примера рассмотрим вычисление X24. Цепочку aab в позициях с 2 по 4 можно разбить, заканчивая первую подцепочку в 2 или в 3, т.е. в определении X24 можно выбрать k = 2 или k = 3. Таким образом, нужно рассмотреть все тела вX22X34 U X23X44. Этим множеством цепочек является {A, C}{S, C} U {B}{B} = {AS, AC, CS,CC, BB}.
Из пяти цепочек этого множества только CC является телом; его голова — B.Таким образом, X24 = {B}. 7.4.5. Îáçîð íåðàçðåøèìûõ ïðîáëåì ÊÑ-ÿçûêîâВ следующих главах излагается замечательная теория, позволяющая доказать формально, что существуют проблемы, которые нельзя разрешить никаким алгоритмом,выполняемым на компьютере.
Используем ее для того, чтобы показать, что многиеэлементарные вопросы о грамматиках и КС-языках не имеют алгоритма решения; ониназываются “неразрешимыми проблемами”. Сейчас же ограничимся следующим списком наиболее значительных неразрешимых вопросов о контекстно-свободных грамматиках и языках.314Стр. 314ÃËÀÂÀ 7. ÑÂÎÉÑÒÂÀ ÊÎÍÒÅÊÑÒÍÎ-ÑÂÎÁÎÄÍÛÕ ßÇÛÊÎÂ1.Неоднозначна ли данная КС-грамматика G?2.Является ли данный КС-язык существенно неоднозначным?3.Пусто ли пересечение двух КС-языков?4.Равны ли два данных КС-языка?5.Равен ли Σ* данный КС-язык, где Σ — алфавит этого языка?Отметим, что вопрос 1 о неоднозначности отличается от остальных тем, что это вопрос о грамматике, а не о языке.
Все остальные вопросы предполагают, что язык представлен грамматикой или МП-автоматом, но это все равно вопросы о языке (или языках).Например, в противоположность вопросу 1 вопрос 2 требует по данной грамматике G(или МП-автомату) определить, существует ли некоторая эквивалентная ей однозначнаяграмматика G′. Если G сама по себе однозначна, то ответом, безусловно, будет “да”, ноесли G неоднозначна, то для языка грамматики G может существовать другая грамматика G′, которая однозначна, как было с грамматиками выражений в примере 5.27.7.4.6.
Óïðàæíåíèÿ ê ðàçäåëó 7.47.4.1.Постройте алгоритмы разрешения следующих проблем:а) (∗) конечен ли язык L(G) данной грамматики G? Указание. Используйтелемму о накачке;б) (!) определить, содержит ли язык L(G) данной грамматики G не менее 100цепочек;в) (!!) по данной грамматике G и ее переменной A определить, существует ливыводимая цепочка, которая начинается символом A. Указание. Напомним,что переменная A может впервые появиться в середине некоторой выводимой цепочки, а затем все символы слева от нее могут породить ε.7.4.2.7.4.3.Используйте технику, описанную в разделе 7.4.3, для построения линейных повремени алгоритмов разрешения следующих вопросов о КС-грамматиках.1.Какие символы встречаются в выводимых цепочках?2.Какие символы являются ε-порождающими?Примените CYK-алгоритм к грамматике G из примера 7.34, чтобы определить,принадлежат ли L(G) следующие цепочки:а) (∗) ababa;б) baaab;в) aabab.7.4.4.(∗) Покажите, что для любой НФХ-грамматики все деревья разбора цепочекдлиной n имеют 2n – 1 внутренних узлов (отмеченных переменными).7.4.
ÑÂÎÉÑÒÂÀ ÐÀÇÐÅØÈÌÎÑÒÈ ÊÑ-ßÇÛÊÎÂСтр. 3153157.4.5.(!) Измените CYK-алгоритм так, чтобы он сообщал, сколько различных деревьеввывода у данной цепочки, а не просто, принадлежит ли она языку грамматики.Ðåçþìå♦ Удаление бесполезных символов. Переменную можно удалить из КС-грамматики,если она не порождает ни одной терминальной цепочки или не встречается в цепочках, выводимых из стартового символа.
Для корректного удаления таких бесполезных символов нужно сначала проверить, порождает ли каждая переменнаятерминальную цепочку, и удалить те, которые не порождают. Только после этогоудаляются переменные, которые не выводятся из стартового символа.♦ Удаление цепных и ε-продукций. По данной КС-грамматике G можно найти ещеодну КС-грамматику, которая порождает тот же язык, за исключением цепочки ε,но не содержит цепных продукций (с единственной переменной в качестве тела) иε-продукций (с телом ε).♦ Нормальная форма Хомского. По данной КС-грамматике G можно найти еще одну КС-грамматику, которая порождает тот же язык, за исключением цепочки ε, инаходится в нормальной форме Хомского: нет бесполезных символов, и тело каждой продукции состоит либо из двух переменных, либо из одного терминала.♦ Лемма о накачке.
В любой достаточно длинной цепочке КС-языка можно найтикороткую подцепочку, два конца которой можно синхронно “накачивать”, т.е повторять произвольное число раз. Хотя бы одна из накачиваемых цепочек не равнаε. Эта лемма, а также ее более мощная версия, которая называется леммой Огденаи приводится в упражнении 7.2.3, дают возможность доказывать, что многие языки не являются контекстно-свободными.♦ Операции, сохраняющие контекстно-свободные языки.
КС-языки замкнутыотносительно подстановки, объединения, конкатенации, замыкания (*), обращения и обратного гомоморфизма. КС-языки не замкнуты относительно пересечения и дополнения, но пересечение КС-языка с регулярным всегда является КС-языком.♦ Проверка пустоты КС-языка.
Существует алгоритм, который по данной грамматике G определяет, порождает ли она какие-нибудь цепочки. Аккуратная реализация этой проверки выполняется за время, прямо пропорциональное размерусамой грамматики.♦ Проверка принадлежности КС-языку. Алгоритм Кока-Янгера-Касами определяет,принадлежит ли данная цепочка данному КС-языку. Если язык зафиксирован, этапроверка требует времени O(n3), где n — длина проверяемой цепочки.316Стр. 316ÃËÀÂÀ 7. ÑÂÎÉÑÒÂÀ ÊÎÍÒÅÊÑÒÍÎ-ÑÂÎÁÎÄÍÛÕ ßÇÛÊÎÂËèòåðàòóðàНормальная форма Хомского впервые описана в [2], нормальная форма Грейбах — в [4],хотя конструкция, описанная в упражнении 7.1.11, принадлежит Полу (M. C. Paull).Многие фундаментальные свойства контекстно-свободных языков установлены в [1].Среди них лемма о накачке, основные свойства замкнутости, а также проверки для простых вопросов, таких как пустота и конечность КС-языка.
Результаты о незамкнутостиотносительно пересечения и дополнения происходят из работы [6], а дополнительные результаты о замкнутости, включая замкнутость КС-языков относительно обратного гомоморфизма, — из [3]. Лемма Огдена предложена в [5].Алгоритм Кока-Янгера-Касами имеет три независимых источника. Работа Кока распространялась частным образом и не была опубликована. Версия по сути того же алгоритма, записанная Касами, появилась только в закрытом докладе Воздушных Сил США.И лишь работа Янгера была опубликована в [7].1.Y. Bar-Hillel, M. Perles, and E.
Shamir, “On formal properties of simple phrase-structuregrammars”, Z. Phonetic. Sprachwiss. Kommunikationsforsch. 14 (1961), pp. 143–172.2.N. Chomsky, “On certain formal properties of grammars”, Information and Control 2:2(1959), pp. 137–167. (Хомский Н. О некоторых формальных свойствах грамматик. —Кибернетический сборник, вып. 5.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
