Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 70
Текст из файла (страница 70)
С такой модификацией общего построения НФХ единственным нелинейным шагом будет удаление цепных продукций. Поскольку этот шаг требует О(и ) времени, можно з заключить следующее. Теорема 7.32. По грамматике С длиной и можно найти грамматику в нормальной форме Хомского, эквивалентную С, за время О(и ); полученная грамматика будет 2, иметь длину О(и~). П 7.4.3. Проверка пустоты КС-языков Алгоритм проверки пустоты КС-языка В нам уже знаком, Чтобы определить, является ли стартовый символ В данной грамматики С для языка Т.
порождающим, можно использовать алгоритм из раздела 7.1.2. А пуст тогда и только тогда, когда 5 не является порождающим. Поскольку эта проверка весьма важна, рассмотрим детальнее, сколько времени требуется для поиска всех порождающих символов грамматики С. Пусть С имеет длину и. Тогда у нее может быть порядка и переменных, и каждый проход индуктивного обнару- кения порождающих переменных может занимать О(и) времени для проверки всех продукций С. Если на каждом проходе обнаруживается только одна новая порождающая переменная, то может понадобиться О(и) проходов. Таким образом, простая реализация проверки на порождающие символы требует О(п ) времени, т.е.
является квадратичной. Однако существует более аккуратный алгоритм, который заранее устанавливает структуру данных для того, чтобы обнаружить порождающие символы всего за 0(н) времени. Структура данных (рис. 7.!1) начинает с массива, индексированного переменными, как показано слева, который говорит, установлено ли, что переменная является порождающей. Массив на рис. 7,1! показывает, что переменная В уже обнаружена как варожлаюшая, но о переменной А это еще неизвестно. В конце алгоритма каждая отметка "?" превращается в "нет", поскольку каждая переменная, не обнаруженная алгоритмом как порождающая, на самом деле является непорождающей.
7.4. СВОЙСТВА РАЗРЕШИМОСТИ КС-ЯЗЫКОВ 399 Порождающая? Й Рис. 7. ё. Структуры донньтсия линейной проверки пустоты Для продукций предварительно устанавливается несколько видов полезных ссылок. Во-первых, для каждой переменной заводится список всех возможных позиций, в которых эта переменная встречается. Например, список для переменной В представлен сплошными линиями. Во-вторых, для каждой продукции ведется счетчик числа позиций, содержащих переменные, способность которых породить терминальную цепочку еше не учтена. Пунктирные линии представляют связи, ведушие от продукций к их счетчикам.
Счетчики, показанные на рис. 7.11, предполагают, что ни одна из переменных в телах продукций еше не учитывалась, хотя уже и установлено, что  — порождающая. Предположим, мы уже обнаружили, что  — порождающая. Мы спускаемся по списку позиций в телах, содержащих В. Для каждой такой позиции счетчик ее продукции уменьшаем на 1; позиций, которые нужны для заключения, что переменная в голове продукции тоже порождающая, остается на одну меньше. Если счетчик достигает О, то понятно, что переменная в голове продукции является порождаюшей. Связь, представленная точечными линиями, приводит к переменной, и эту переменную можно поместить в очередь переменных, о которых еше неизвестно, порождают ли они (переменная В уже исследована).
Эта очередь не показана. Обоснуем, что этот алгоритм требует О(п) времени. Важными являются следующие утверждения. ° Поскольку грамматика размера п имеет не более и переменных, создание и ини- циализация массива требует времени О(п). ° Есть не более и продукций, и их обшая длина не превосходит и, поэтому инициализация связей и счетчиков, представленных на рис. 7.11, может быть выполнена за время О(п), ° Когда обнаруживается, что счетчик продукции получил значение О, т.е. все позиции в ее теле являются порождающими, вся проделанная работа может быть раз- делена на следующие два вида.
ГЛАВА 7. СВОЙСТВА КОНТЕКСТНО-СВОБОДНЫХ ЯЗЫКОВ 310 1. Работа, выполненная для продукции: обнаружение, что счетчик обиулен, поиск переменной, скажем, А, в голове продукции, проверка, установлено ли, что эта переменная является порождающей, и помещение ее в очередь, если это не так, Все эти шаги требуют О(1) времени для каждой продукции, поэтому вся такая работа в целом требует О(п) времени. Работа, выполненная при посещении позиций в телах продукций, имеющих переменную А в голове. Эта работа пропорциональна числу позиций с переменной А. Следовательно, совокупная работа, выполненная со всеми порождающими переменными, пропорциональна сумме длин тел продукций, а это О(и). Отсюда делаем вывод, что общая работа, выполненная этим азгоритмом, есть О(о). Другие способы использования линейной проверки пустоты Структура данных и счетчики, примененные в разделе 7А.3 для проверки, является ли переменная порождающей, могут использоваться для обеспечения линейности времени некоторых других проверок из раздела 7.1.
Назовем два важных примера. 1. Какие символы достижимы? 2. Какие символы являются г-порождающими? 7.4.4. Проверка принадлежности КС-языку Проблема принадлежности цепочки и КС-языку Т. также разрешима. Есть несколько неэффективных способов такой проверки; они требуют времени. экспоненциального отнесительно ~и1, в предположении, что язык Т. представлен заданной грамматикой или МП-автоматом, и размер представления считается константой, не зависящей от и.
Например, начнем с преобразования какого-либо данного нам представления в НФХ-грамматику. Поскольку дерево разбора в такой грамматике является бинарным, при длине и слова и в дереве будет ровно 2и — 1 узлов, отмеченных переменными. Несложное индуктивное доказательство мого факи оставляется в качестве упражнения.
Количество возможных деревьев и разметок пх узлов, таким образом, "всего лишь" экспоненциально относительно и, поэтому в принципе пх кожно перечислить, и проверить, имеет ли какое-нибудь из деревьев крону и. Существует гораздо более эффективный метод, основанный на идее "динамического программирования" и известный также, как алгоритм заполнения таблицы" или "табуляция". Данный алгоритм известен как СУКыигорити (азгориоси Кока-Янгераз Косача). Он начинает с НФХ-грамматики С = (1; Т, Р, 5) для языка 2„На вход алгоритма подается цепочка и = а,ал..а„из Т. За время О(и ) алгоритм строит таблицу, которая говорит, принадлежит ли ж языку А.
Отметим, что при вычислении этого времени сама по себе грамматика рассматривается фиксированной, и ее размер вносит лишь констант- ' Ои назван по фамилиям трех авторов (1. Сасйе, 11. Уоипяег и Т. Казали), независимо пришедших к одной и той же, по сути. идее. ? А. СВОЙСТВА РАЗРЕШИМОСТИ КС-ЯЗЫКОВ ный сомножитель в оценку времени, измеряемого в терминах длины цепочки, проверяемой на принадлежность б.
В СУК-алгоритме строится треугольная таблица (рис. 7.12). Горизонтальная ось соответствует позициям цепочки ж = айаг...а„, имеющей в нашем примере длину 5. Содержимое клетки, или вход таблицы Хн, есть множество таких переменных А, для которых А ~ а,и,,...а,, Заметим, в частности, что нас интересует, принадлежит ли 5 множеству Хт, поскольку это то же самое, чтоб =» н,т.е.
лен Б. Таблица заполняется построчно снизу вверх. Отметим, что каждая строка соответствует определенной длине подцепочек; нижняя — подцепочкам длины 1, вторая снизу— подцепочкам длины 2 и так далее до верхней строки, соответствующей одной подцепочке длиной п, т.е. зн. Ниже обсуждается метод, с помощью которого вычисление одного входа требует времени О(н). Поскольку всего входов н(н+ 1)/2, весь процесс построения таблицы занимает О(и ) времени. Алгоритм вычисления Л;, таков.
Рис. 7. !2 7облича, построенная слегорнтнол~ Кока-Янгеро-Косил~и Базис. Вычисляем первую строку следующим образом. Поскольку цепочка, которая начинается и заканчивается в позиции б представляет собой просто терминал нн а грамматика находится в НФХ, единственный способ породить а, заключается в использовании продукции вида А — » и, грамматики О. Итак, Л;, является множеством переменных А, для которых А — » а, — продукция О.
Индукции, Пусть нужно вычислить Хн в (г' — !+ !)-й строке, и все множества Х в нижних строках уже вычислены, т.е. известны для всех подцепочек, более коротких, чем о,а, Р..а„и в частности, для всех собственных префиксов и суффиксов этой цепочки. Можно предполагать, что у — ! > О, поскольку случай) = ! рассмотрен в базисе. Поэтому любое порождение А =» а,а, Р,.а, должно начинаться шагом А =г ВС Тогда В порож- дает некотоРый пРефикс стРоки на,ч...ап скажем, В ~ на, Р..ал длЯ некотоРого lе < У. Кроме того, С порождает остаток аа, ь..он те.
С =» ал, ~ал.г...ан ГЛАВА 7. СВОЙСТВА КОНТЕКСТНО-СВОБОДНЫХ ЯЗЫКОВ 312 Приходим к выводу, что для того, чтобы А попало в Хв, нужно найти переменные В и С н целое )е, при которых справедливы следующие условия. 1, ! <л</. 2. В принадлежитХ». 3. СпринадлежитЛ» ьг 4. А -+ ВС вЂ” продукция в О. Поиск таких переменных А требует обработки не более и пар вычисленных ранее множеств: (Хл Х,. ю), (Л;, ь Х...) и т.д. до (Х,, ь Х„). Таким образом, мы поднимаемся по колонке, расположенной под Л;„и одновременно спускаемся по диагонали (рис. 7.13). и е 1 Рис. 7.13. Вычисление Хи требует совыестиой обработки столбна под Хч и диагонали справа от лего Теорема 7.33.
Вышеописанный алгоритм корректно вычисляет Хи для всех 1 и 7'. Такни образом, ж и ЦО) то~да и только тогда, когда 5 и Хгт Кроме того, время выполнення алгоритма есть О(и ). Доказательство. Представив базис и индуктивную часть алгоритма, мы объяснили, почему алгоритм находит корректные множества переменных. Рассмотрим время выполнения.
Заметим, что нужно вычислить О(п ) элементов таблицы, и каждое вычисле- г нне вовлекает сравнение и вычисление не более, чем и пар элементов. Важно помнить, что, хотя в каждом множестве Хв может быть много переменных, грамматика О зафиксирована и число ее переменных не зависит от н — длины проверяемой цепочки и. Такни образом, время сравнения элементов Х» и Х»,, и поиска переменных, входящих в Хв есть 0(1). Поскольку для каждого Х, возможно не более л таких пар, общее время составляет 0(н~). П Пример 7.34. Рассмотрим следующие продукции грамматики О в НФХ. 5-»АВ!ВС А — >ВА)а В-э СС)Ь С-+АВ!а 7,4.
СВОЙСТВА РАЗРЕШИМОСТИ КС-ЯЗЫКОВ 313 Проверим, принадлежит ли цепочка ЬааЬа языку Ь(6). На рис. 7.14 показана таблица, заполненная для этой строки. Для построения первой (нижней) строки используется базисное правило. Нужно рассмотреть лишь переменные с телом продукции а (это А и С) и телом Ь (это В). Таким образом,Х»» =Х,»= (В),Хм — — Хзз =Хез = (А, С).
Во второй строке показаны значения Хп, Хсь Х,» и Х»и Рассмотрим, например, как вычисляется Хы, Цепочку Ьа, занимающую позиции 1 и 2, можно разбить на непустые подцепочки единственным способом. Первая должна занимать позицию 1, вторая — позицию 2. Для того чтобы переменная порождала Ьа, она должна иметь продукцию с телом, первая переменная которого принадлежит Х„= (В) (т.е. порождает Ь), а вторая— Хм = (А, С) (т.е. порождает а).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
