dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 93
Текст из файла (страница 93)
413413когда данный экземпляр ПСП имеет решение. Таким образом, решение существует тогда итолько тогда, когда в грамматике для объединения присутствует неоднозначность.Уточним эту идею. Пусть экземпляр ПСП состоит из списков A = w1, w2, …, wk и B =x1, x2, …, xk. Для списка A построим КС-грамматику с одной переменной A. Терминаламибудут все символы алфавита Σ, используемые в данном экземпляре ПСП, плюс не пересекающееся с Σ множество индексных символов a1, a2, …, ak, которые представляют выборы пар цепочек в решении ПСП. Таким образом, индексный символ ai представляетвыбор wi из списка A или xi из списка B. Продукции КС-грамматики для списка A имеютследующий вид.A→ w1Aa1 ⏐ w2Aa2 ⏐ … ⏐ wkAak ⏐w1a1 ⏐ w2a2 ⏐ … ⏐ wkakОбозначим эту грамматику через GA, а ее язык — через LA. Язык типа LA будет называться в дальнейшем языком для списка A.Заметим, что все терминальные цепочки, порожденные переменной A в GA, имеютвид wi1wi2LwimaimLai2ai1 при некотором m ≥ 1, где i1, i2, …, im — последовательность целых чисел в пределах от 1 до k.
Все выводимые цепочки содержат одиночный символ A,отделяющий цепочки w от индексных символов a, до тех пор, пока не используется одноиз k правил последней группы, в которых A отсутствует. Поэтому деревья разбора имеютструктуру, представленную на рис. 9.16.Рис.
9.16. Общий вид деревьев разбора в грамматике GAЗаметим также, что любая терминальная цепочка порождается в GA одним-единственным способом. Индексные символы в конце цепочки однозначно определяют, какое именно правило должно использоваться на каждом шаге, поскольку тела лишь двух414Стр. 414ÃËÀÂÀ 9. ÍÅÐÀÇÐÅØÈÌÎÑÒÜпродукций оканчиваются данным индексным символом ai: A → wiAai и A → wiai. Первуюпродукцию нужно использовать, когда данный шаг порождения не последний, в противном же случае используется вторая продукция.Рассмотрим теперь вторую часть экземпляра ПСП — список B = x1, x2, …, xk.Этому списку мы поставим в соответствие еще одну грамматику GB с такими продукциями.B→ x1Ba1 ⏐ x2Ba2 ⏐ … ⏐ xkBak ⏐x1a1 ⏐ x2a2 ⏐ … ⏐ xkakЯзык этой грамматики обозначим через LB.
Все замечания, касающиеся GA, справедливыи для GB. В частности, терминальная цепочка из LB имеет одно-единственное порождение, определяемое индексными символами в конце этой цепочки.Наконец, мы объединяем языки и грамматики двух списков, формируя грамматикуGAB для всего данного экземпляра ПСП. GAB имеет следующие компоненты.1.Переменные A, B и S, последняя из которых — стартовый символ.2.Продукции S → A⏐B.3.Все продукции грамматики GA.4.Все продукции грамматики GB.Утверждаем, что грамматика GAB неоднозначна тогда и только тогда, когда экземпляр (A, B) ПСП имеет решение.
Это утверждение является основным в следующейтеореме.Теорема 9.20. Вопрос о неоднозначности КС-грамматики неразрешим.Основная часть сведения ПСП к вопросу о неразрешимости КС-грамматики проведена выше. В силу неразрешимости ПСП это сведение доказывает неразрешимость проблемы неоднозначности КС-грамматики. Остается лишь показать корректность приведенной конструкции, т.е. что• GAB неоднозначна тогда и только тогда, когда экземпляр (A, B) ПСП имеетрешение.(Достаточность) Предположим, что i1, i2, …, im — решение данного экземпляраПСП. Рассмотрим два порождения в GAB.S ⇒ A ⇒ wi1Aai1 ⇒ wi1wi2Aai2ai1 ⇒ L ⇒wi1wi2Lwim-1 Aaim-1Lai2ai1 ⇒ wi1wi2LwimaimLai2ai1S ⇒ B ⇒ xi1Bai1 ⇒ xi1xi2Bai2ai1 ⇒ L ⇒xi1xi2Lxim-1Baim-1Lai2ai1 ⇒ xi1xi2LximaimLai2ai1Поскольку i1, i2, …, im — решение, то wi1wi2Lwim = xi1xi2Lxim, т.е.
эти два порожденияпредставляют собой порождения одной и той же цепочки. А поскольку сами порожде-9.5. ÄÐÓÃÈÅ ÍÅÐÀÇÐÅØÈÌÛÅ ÏÐÎÁËÅÌÛСтр. 415415ния, очевидно, являются двумя различными левыми порождениями одной и той же терминальной цепочки, делаем вывод, что грамматика GAB неоднозначна.(Необходимость) Как было отмечено ранее, для данной терминальной цепочки существует не более одного порождения в GA и не более одного порождения в GB. Поэтомутерминальная цепочка может иметь в GAB два левых порождения лишь в том случае, если одно из них начинается с S ⇒ A и продолжается порождением в GA, а второе начинается с S ⇒ B и продолжается порождением в GB.Цепочка с двумя порождениями имеет окончание из индексов aimLai2ai1 при неко-тором m ≥ 1.
Это окончание и должно быть решением данного экземпляра ПСП, поскольку то, что ей предшествует в цепочке с двумя порождениями, есть одновременнои wi1wi2Lwim, и xi1xi2Lxim. 9.5.3. Äîïîëíåíèå ÿçûêà ñïèñêàНаличие контекстно-свободных языков, подобных LA для списка A, позволяет показать неразрешимость ряда проблем, связанных с КС-языками. Еще больше фактов о неразрешимости свойств КС-языков можно получить, рассмотрев дополнение этого языка______LA .
Отметим, что язык LA состоит из всех цепочек в алфавите Σ U {a1, a2, …, ak}, не со-держащихся в LA, где Σ — алфавит некоторого экземпляра ПСП, а ai — символы, которые не принадлежат Σ и представляют индексы пар в этом экземпляре ПСП.___Интересными элементами языка LA являются цепочки, префикс которых принадлежит Σ*, т.е. является конкатенацией цепочек из списка A, а суффикс состоит из индексных символов, не соответствующих цепочкам из префикса.
Однако помимо этих эле___ментов в LA содержатся цепочки неправильного вида, не принадлежащие языку регулярного выражения Σ*(a1 + a2 + … + ak)*.______Мы утверждаем, что LA является КС-языком. В отличие от LA, грамматику для LAпостроить нелегко, но можно построить МП-автомат, точнее — детерминированныйМП-автомат. Конструкция описывается в следующей теореме.___Теорема 9.21. Если LA — язык для списка A, то LA является контекстно-свободным языком.Доказательство. Пусть Σ — алфавит цепочек из списка A = {w1, w2, …, wk}, аI = {a 1, a 2, …, a k} — множество индексных символов. ДМПА P, который по по___строению должен допускать LA , работает следующим образом.1.Обозревая символ из Σ, P записывает его в магазин. Поскольку все цепочки из Σ*___принадлежат LA , P допускает их по мере чтения.2.416Стр.
416При виде индексного символа из I, скажем, ai, P просматривает магазин, чтобы проверить, образуют ли символы из его верхней части цепочку wiR, т.е. обращение соответствующей цепочки:ÃËÀÂÀ 9. ÍÅÐÀÇÐÅØÈÌÎÑÒÜа) если это не так, то входная цепочка, а также всякое ее продолжение принад___лежат LA . Поэтому P переходит в допускающее состояние, в котором он дочитывает вход, не изменяя содержимое магазина;б) если цепочка wiR была извлечена из верхней части магазина, но маркердна магазина не показался на вершине, то P допускает, но запоминает всвоем состоянии, что он ищет только символы из I и может еще встретить цепочку из LA (которую не допустит). P повторяет шаг 2 до техпор, пока вопрос о принадлежности входа языку LA будет оставаться неразрешенным;в) если wiR была извлечена и показался маркер дна магазина, то P прочиталвход, принадлежащий LA.
P не допускает этот вход. Однако, поскольку всякое продолжение этого входа уже не может содержаться в LA, P переходит втакое состояние, в котором он допускает все последующие входы, не изменяя магазин.3.Если после того, как P считал один или несколько символов из I, он встречает ещеодин символ из Σ, то входная цепочка не может принадлежать LA, поскольку имеетнеправильную форму.
Поэтому P переходит в состояние, в котором он допускаетэтот и все последующие входы, не изменяя магазин.Для получения результатов о неразрешимости КС-языков можно использоватьLA, LB и их дополнения различными способами. Часть этих фактов собрана в следующей теореме.Теорема 9.22. Пусть G1 и G2 — КС-грамматики, а R — регулярное выражение.
Тогданеразрешимы следующие проблемы:а) L(G1) I L(G2) = ∅ ?б) L(G1) = L(G2) ?в) L(G1) = L(R) ?г) верно ли, что L(G1) = T* для некоторого алфавита T ?д) L(G1) ⊆ L(G2) ?е) L(R) ⊆ L(G1) ?Доказательство. Каждое из доказательств представляет собой сведение ПСП. Покажем, как преобразовать экземпляр (A, B) ПСП в вопрос о КС-грамматиках и/или регулярных выражениях, который имеет ответ “да” тогда и только тогда, когда данный экземпляр ПСП имеет решение. В некоторых случаях ПСП сводится к самому вопросу,сформулированному в теореме, в других же случаях — к его дополнению.
Это не имеетзначения, поскольку, если показано, что дополнение проблемы неразрешимо, то сама9.5. ÄÐÓÃÈÅ ÍÅÐÀÇÐÅØÈÌÛÅ ÏÐÎÁËÅÌÛСтр. 417417проблема также не может быть разрешимой, так как рекурсивные языки замкнуты относительно дополнения (теорема 9.3).Алфавит цепочек данного экземпляра ПСП обозначим Σ, а алфавит индексныхсимволов — I. В наших сведениях будем опираться на то, что LA, LB, LA и LB имеютКС-грамматики.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
