dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 69
Текст из файла (страница 69)
Большинство шагов сохраняют, сточностью до константного сомножителя, длину описания грамматики, т.е. по грамматике длиной n они строят другую длиной O(n). “Хорошие” (с точки зрения затрат времени)преобразования перечислены в следующем списке.1.С использованием подходящего алгоритма (см. раздел 7.4.3) определение достижимых и порождающих символов грамматики может быть выполнено за линейноевремя, O(n). Удаление получившихся бесполезных символов требует O(n) времени ине увеличивает размер грамматики.2.Построение цепных пар и удаление цепных продукций, как в разделе 7.1.4, требуетвремени O(n2), и получаемая грамматика имеет размер O(n2).3.Замена терминалов переменными в телах продукций, как в разделе 7.1.5(нормальная форма Хомского), требует времени O(n) и приводит к грамматике длиной O(n).4.Разделение тел продукций длины 3 и более на тела длины 2 (раздел 7.1.5) также требует времени O(n) и приводит к грамматике длиной O(n).“Плохой” является конструкция из раздела 7.1.3, где удаляются ε-продукции.
По телупродукции длиной k можно построить 2k – 1 продукций новой грамматики. Поскольку k308Стр. 308ÃËÀÂÀ 7. ÑÂÎÉÑÒÂÀ ÊÎÍÒÅÊÑÒÍÎ-ÑÂÎÁÎÄÍÛÕ ßÇÛÊÎÂможет быть пропорционально n, эта часть построения может занимать O(2n) времени иприводить к грамматике длиной O(2n).Во избежание этого экспоненциального взрыва достаточно ограничить длины телпродукций. К каждому телу продукции можно применить прием из раздела 7.1.5, нотолько если в теле нет терминалов. Таким образом, в качестве предварительного шагаперед удалением ε-продукций рекомендуется разделить все продукции с длинными телами на последовательность продукций с телами длины 2. Этот шаг требует времениO(n) и увеличивает грамматику только линейно.
Конструкция из раздела 7.1.3 для удаления ε-продукций будет работать с телами длиной не более 2 так, что время выполнениябудет O(n) и полученная грамматика будет длиной O(n).С такой модификацией общего построения НФХ единственным нелинейным шагомбудет удаление цепных продукций. Поскольку этот шаг требует O(n2) времени, можнозаключить следующее.Теорема 7.32.
По грамматике G длиной n можно найти грамматику в нормальнойформе Хомского, эквивалентную G, за время O(n2); полученная грамматика будетиметь длину O(n2). 7.4.3. Ïðîâåðêà ïóñòîòû ÊÑ-ÿçûêîâАлгоритм проверки пустоты КС-языка L нам уже знаком. Чтобы определить, является ли стартовый символ S данной грамматики G для языка L порождающим, можноиспользовать алгоритм из раздела 7.1.2. L пуст тогда и только тогда, когда S не является порождающим.Поскольку эта проверка весьма важна, рассмотрим детальнее, сколько времени требуется для поиска всех порождающих символов грамматики G. Пусть G имеет длину n.Тогда у нее может быть порядка n переменных, и каждый проход индуктивного обнаружения порождающих переменных может занимать O(n) времени для проверки всех продукций G.
Если на каждом проходе обнаруживается только одна новая порождающая переменная, то может понадобиться O(n) проходов. Таким образом, простая реализацияпроверки на порождающие символы требует O(n2) времени, т.е. является квадратичной.Однако существует более аккуратный алгоритм, который заранее устанавливаетструктуру данных для того, чтобы обнаружить порождающие символы всего за O(n)времени. Структура данных (рис. 7.11) начинает с массива, индексированного переменными, как показано слева, который говорит, установлено ли, что переменная являетсяпорождающей. Массив на рис. 7.11 показывает, что переменная B уже обнаружена какпорождающая, но о переменной A это еще неизвестно. В конце алгоритма каждая отметка “?” превращается в “нет”, поскольку каждая переменная, не обнаруженная алгоритмом как порождающая, на самом деле является непорождающей.7.4.
ÑÂÎÉÑÒÂÀ ÐÀÇÐÅØÈÌÎÑÒÈ ÊÑ-ßÇÛÊÎÂСтр. 309309Порождающая?СчетчикA?ByesACBcBADB32Рис. 7.11. Структуры данных для линейной проверки пустотыДля продукций предварительно устанавливается несколько видов полезных ссылок. Во-первых, для каждой переменной заводится список всех возможных позиций,в которых эта переменная встречается. Например, список для переменной B представлен сплошными линиями.
Во-вторых, для каждой продукции ведется счетчикчисла позиций, содержащих переменные, способность которых породить терминальную цепочку еще не учтена. Пунктирные линии представляют связи, ведущие отпродукций к их счетчикам. Счетчики, показанные на рис. 7.11, предполагают, что ниодна из переменных в телах продукций еще не учитывалась, хотя уже и установлено,что B — порождающая.Предположим, мы уже обнаружили, что B — порождающая. Мы спускаемся по списку позиций в телах, содержащих B.
Для каждой такой позиции счетчик ее продукцииуменьшаем на 1; позиций, которые нужны для заключения, что переменная в голове продукции тоже порождающая, остается на одну меньше.Если счетчик достигает 0, то понятно, что переменная в голове продукции являетсяпорождающей. Связь, представленная точечными линиями, приводит к переменной, иэту переменную можно поместить в очередь переменных, о которых еще неизвестно, порождают ли они (переменная B уже исследована).
Эта очередь не показана.Обоснуем, что этот алгоритм требует O(n) времени. Важными являются следующиеутверждения.• Поскольку грамматика размера n имеет не более n переменных, создание и инициализация массива требует времени O(n).• Есть не более n продукций, и их общая длина не превосходит n, поэтому инициализация связей и счетчиков, представленных на рис. 7.11, может быть выполненаза время O(n).• Когда обнаруживается, что счетчик продукции получил значение 0, т.е.
все позиции в ее теле являются порождающими, вся проделанная работа может быть разделена на следующие два вида.310Стр. 310ÃËÀÂÀ 7. ÑÂÎÉÑÒÂÀ ÊÎÍÒÅÊÑÒÍÎ-ÑÂÎÁÎÄÍÛÕ ßÇÛÊÎÂ1.Работа, выполненная для продукции: обнаружение, что счетчик обнулен, поиск переменной, скажем, A, в голове продукции, проверка, установлено ли, что эта переменная является порождающей, и помещение ее в очередь, если это не так.
Все этишаги требуют O(1) времени для каждой продукции, поэтому вся такая работа в целом требует O(n) времени.2.Работа, выполненная при посещении позиций в телах продукций, имеющих переменную A в голове. Эта работа пропорциональна числу позиций с переменной A.Следовательно, совокупная работа, выполненная со всеми порождающими переменными, пропорциональна сумме длин тел продукций, а это O(n).Отсюда делаем вывод, что общая работа, выполненная этим алгоритмом, есть O(n).Äðóãèå ñïîñîáû èñïîëüçîâàíèÿ ëèíåéíîé ïðîâåðêè ïóñòîòûСтруктура данных и счетчики, примененные в разделе 7.4.3 для проверки, является липеременная порождающей, могут использоваться для обеспечения линейности времени некоторых других проверок из раздела 7.1.
Назовем два важных примера.1. Какие символы достижимы?2. Какие символы являются ε-порождающими?7.4.4. Ïðîâåðêà ïðèíàäëåæíîñòè ÊÑ-ÿçûêóПроблема принадлежности цепочки w КС-языку L также разрешима. Есть нескольконеэффективных способов такой проверки; они требуют времени, экспоненциального относительно |w|, в предположении, что язык L представлен заданной грамматикой илиМП-автоматом, и размер представления считается константой, не зависящей от w. Например,начнем с преобразования какого-либо данного нам представления в НФХ-грамматику. Поскольку дерево разбора в такой грамматике является бинарным, при длине n слова w в деревебудет ровно 2n – 1 узлов, отмеченных переменными.
Несложное индуктивное доказательствоэтого факта оставляется в качестве упражнения. Количество возможных деревьев и разметоких узлов, таким образом, “всего лишь” экспоненциально относительно n, поэтому в принципеих можно перечислить, и проверить, имеет ли какое-нибудь из деревьев крону w.Существует гораздо более эффективный метод, основанный на идее “динамическогопрограммирования” и известный также, как “алгоритм заполнения таблицы” или“табуляция”. Данный алгоритм известен как CYK-алгоритм3 (алгоритм Кока-ЯнгераКасами). Он начинает с НФХ-грамматики G = (V, T, P, S) для языка L.
На вход алгоритмаподается цепочка w = a1a2…an из T*. За время O(n3) алгоритм строит таблицу, котораяговорит, принадлежит ли w языку L. Отметим, что при вычислении этого времени сама3Он назван по фамилиям трех авторов (J. Cocke, D. Younger и T. Kasami), независимо пришедших к одной и той же, по сути, идее.7.4. ÑÂÎÉÑÒÂÀ ÐÀÇÐÅØÈÌÎÑÒÈ ÊÑ-ßÇÛÊÎÂСтр. 311311по себе грамматика рассматривается фиксированной, и ее размер вносит лишь константный сомножитель в оценку времени, измеряемого в терминах длины цепочки, проверяемой на принадлежность L.В CYK-алгоритме строится треугольная таблица (рис. 7.12).
Горизонтальная ось соответствует позициям цепочки w = a1a2…an, имеющей в нашем примере длину 5. Содержимое клетки, или вход таблицы Xij, есть множество таких переменных A, для которых*A ⇒ aiai+1…aj. Заметим, в частности, что нас интересует, принадлежит ли S множеству*X1n, поскольку это то же самое, что S ⇒ w, т.е. w ∈ L.Таблица заполняется построчно снизу вверх.
Отметим, что каждая строка соответствует определенной длине подцепочек; нижняя — подцепочкам длины 1, вторая снизу —подцепочкам длины 2 и так далее до верхней строки, соответствующей одной подцепочке длиной n, т.е. w. Ниже обсуждается метод, с помощью которого вычисление одноговхода требует времени O(n). Поскольку всего входов n(n + 1)/2, весь процесс построениятаблицы занимает O(n3) времени.
Алгоритм вычисления Xij таков.X15X14X25X13X24X35X12X23X34X45X11X22X33X44X55a1a2a3a4a5Рис. 7.12. Таблица, построенная алгоритмом Кока-Янгера-КасамиБазис. Вычисляем первую строку следующим образом. Поскольку цепочка, котораяначинается и заканчивается в позиции i, представляет собой просто терминал ai, а грамматика находится в НФХ, единственный способ породить ai заключается в использовании продукции вида A → ai грамматики G. Итак, Xii является множеством переменных A,для которых A → ai — продукция G.Индукция. Пусть нужно вычислить Xij в (j – i + 1)-й строке, и все множества X внижних строках уже вычислены, т.е. известны для всех подцепочек, более коротких, чемaiai+1…aj, и в частности, для всех собственных префиксов и суффиксов этой цепочки.Можно предполагать, что j – i > 0, поскольку случай j = i рассмотрен в базисе. Поэтомулюбое порождение A ⇒ aiai+1…aj должно начинаться шагом A ⇒ BC.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
