dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 94
Текст из файла (страница 94)
КС-грамматики либо строятся непосредственно, как в разделе 9.5.2,либо вначале строятся МП-автоматы для языков-дополнений (см. теорему 9.21), а затем с помощью теоремы 6.14 они преобразуются в КС-грамматики.Пусть L(G1) = LA и L(G2) = LB. Тогда L(G1) I L(G2) — множество решений данного1.экземпляра ПСП. Пересечение пусто тогда и только тогда, когда решений нет. Отметим, что технически мы свели ПСП к языку, который состоит из пар КС-грамматик снепустым пересечением их языков, т.е. показали, что проблема “является ли пересечение языков двух КС-грамматик непустым?” неразрешима. Однако, как указано вовведении к доказательству, доказать неразрешимость дополнения проблемы — этото же самое, что доказать неразрешимость самой проблемы.Поскольку КС-языки замкнуты относительно объединения, то можно построить КС-2.___грамматику G1 для LA U LB .
Поскольку (Σ U I)* — регулярное множество, то для___него, конечно же, можно построить КС-грамматику G2. Далее, LA U LB = LA I LB .Таким образом, в L(G1) отсутствуют лишь цепочки, которые представляют решенияданного экземпляра ПСП. L(G2) содержит все цепочки из (Σ U I)*, так что эти языкисовпадают тогда и только тогда, когда данный экземпляр ПСП не имеет решения.Рассуждения точно такие же, как и в п.
2, но полагаем R регулярным выражением3.(Σ U I)*.Достаточно рассуждений п. 3, поскольку Σ U I — единственный алфавит, замыкани-4.___ем которого может быть LA U LB .___Пусть G1 — КС-грамматика для (Σ U I)* и G2 — КС-грамматика для LA U LB . Сле-5.___довательно, L(G1) ⊆ L(G2) тогда и только тогда, когда LA U LB = (Σ U I)*, т.е. тогдаи только тогда, когда данный экземпляр ПСП не имеет решения.Рассуждения точно такие же, как и в п. 5, но полагаем R регулярным выражением6.___(Σ U I)*, а L(G1) — LA U LB .9.5.4.
Óïðàæíåíèÿ ê ðàçäåëó 9.59.5.1.418Стр. 418(∗) Пусть L — множество (кодов) КС-грамматик G, у которых L(G) содержитхотя бы один палиндром. Покажите неразрешимость L. Указание. Сведите ПСПк L путем построения по каждому экземпляру ПСП грамматики, содержащейпалиндром тогда и только тогда, когда этот экземпляр ПСП имеет решение.ÃËÀÂÀ 9.
ÍÅÐÀÇÐÅØÈÌÎÑÒÜ___9.5.2.(!) Покажите, что язык LA U LB является регулярным тогда и только тогда, когда он представляет собой множество всех цепочек над своим алфавитом, т.е.экземпляр (A, B) ПСП не имеет решения. Таким образом, докажите неразрешимость вопроса, порождает ли КС-грамматика регулярный язык. Указание. До___пустим, решение ПСП существует; например, в LA U LB нет цепочки wx, гдеw — цепочка из алфавита экземпляра ПСП, а x — соответствующая цепочка индексных символов, записанная в обратном порядке. Определим гомоморфизм___h(0) = w и h(1) = x.
Тогда, что представляет собой h–1( LA U LB )? В доказатель___стве того, что язык LA U LB нерегулярен, используйте замкнутость регулярныхмножеств относительно обратного гомоморфизма и дополнения, а также леммуо накачке для регулярных множеств.9.5.3.(!!) Вопрос о том, является ли дополнение КС-языка также КС-языком, неразрешим. С помощью упражнения 9.5.2 можно показать, что неразрешимвопрос о том, является ли дополнение КС-языка регулярным языком, но этоне одно и то же.
Чтобы доказать первое утверждение, нужно определитьдругой язык, который представляет цепочки, не являющиеся решениями экземпляра (A, B) ПСП. Пусть LAB есть множество цепочек вида w#x#y#z соследующими свойствами.1.w и x — цепочки над алфавитом Σ данного экземпляра ПСП.2.y и z — цепочки над алфавитом индексов I данного экземпляра.3.# — символ, не принадлежащий ни Σ, ни I.4.w ≠ xR.5.y ≠ zR.6.xR не совпадает с тем, что порождает цепочка индексов y в соответствии сосписком B.7.w не совпадает с тем, что порождает цепочка индексов zR в соответствии сосписком A.Отметим, что LAB состоит из всех цепочек, принадлежащих Σ*#Σ*#I*#I*, еслитолько экземпляр (A, B) ПСП не имеет решения, но независимо от этого LABявляется КС-языком. Докажите, что LAB является КС-языком тогда и толькотогда, когда решения нет.
Указание. Как и в упражнении 9.5.2, используйтеприем с обратным гомоморфизмом, а для того, чтобы добиться равенствадлин тех или иных подцепочек, воспользуйтесь леммой Огдена, как в указании к упражнению 7.2.5, б.9.5. ÄÐÓÃÈÅ ÍÅÐÀÇÐÅØÈÌÛÅ ÏÐÎÁËÅÌÛСтр. 4194199.6. Ðåçþìå♦ Рекурсивные и рекурсивно-перечислимые языки. Языки, допускаемые машинамиТьюринга, называются рекурсивно-перечислимыми (РП), а РП-языки, допускаемые МТ, которые всегда останавливаются, — рекурсивными.♦ Дополнения рекурсивных и РП-языков.
Множество рекурсивных языков замкнутоотносительно дополнения, и если язык и его дополнение являются РП, то оба онирекурсивны. Поэтому дополнение языка, являющегося РП, но не рекурсивным, неможет быть РП.♦ Разрешимость и неразрешимость. “Разрешимость” есть синоним “рекурсивности”, однако языки чаще называются “рекурсивными”, а проблемы (которыепредставляют собой языки, интерпретируемые как вопросы) — “разрешимыми”.Если язык не является рекурсивным, то проблема, которую выражает этот язык,называется “неразрешимой”.♦ Язык Ld. В этот язык входит каждая цепочка в алфавите {0, 1}, которая, будучипроинтерпретированной как код МТ, не принадлежит языку этой МТ.
Язык Ld является хорошим примером не РП-языка, т.е. его не допускает ни одна машинаТьюринга.♦ Универсальный язык. Язык Lu состоит из цепочек, интерпретируемых как кодМТ, к которому дописан ее вход. Цепочка принадлежит Lu, если эта МТ допускает данный вход. Язык Lu — это пример РП-языка, который не являетсярекурсивным.♦ Теорема Райса. Всякое нетривиальное свойство языков, допускаемых МТ, является неразрешимым. Например, множество кодов машин Тьюринга, допускающихпустой язык, согласно теореме Райса является неразрешимым. В действительности этот язык не является РП, хотя его дополнение — множество кодов МТ, допускающих хотя бы одну цепочку, — является РП, но не рекурсивным.♦ Проблема соответствий Поста. Заданы два списка, содержащие одинаковое количество цепочек. Спрашивается, можно ли, выбирая последовательности соответствующих цепочек из этих двух списков, построить путем их конкатенации одну и ту же цепочку.
ПСП является важным примером неразрешимой проблемы.Сводимость ПСП к ряду других проблем обеспечивает доказательство их неразрешимости.♦ Неразрешимые проблемы, связанные с контекстно-свободными языками. Посредством сведения ПСП можно доказать неразрешимость многих вопросов о КСязыках или их грамматиках. Так, например, неразрешимы вопросы о неоднозначности КС-грамматики, о включении одного КС-языка в другой или о пустоте пересечения двух КС-языков.420Стр.
420ÃËÀÂÀ 9. ÍÅÐÀÇÐÅØÈÌÎÑÒÜ9.7. ËèòåðàòóðàРезультат о неразрешимости универсального языка фактически взят из работы Тьюринга [9], хотя там он выражен в терминах вычислений арифметических функций и останова, а не в терминах языков и допустимости по заключительному состоянию. ТеоремаРайса взята из [8].Неразрешимость проблемы соответствий Поста была доказана в [7], но приведенноездесь доказательство, не вошедшее в печатные работы, принадлежит Р. В. Флойду(R.
W. Floyd). Неразрешимость ТАГ-систем Поста (определенных в упражнении 9.4.4)доказывается в [6].Основополагающими работами о неразрешимости вопросов, связанных с контекстносвободными языками, являются [1] и [5]. Однако неразрешимость неоднозначных КСграмматик была установлена независимо друг от друга Кантором [2], Флойдом [4], Хомским и Шютценберже [3].1.Y.
Bar-Hillel, M. Perles, and E. Shamir, “On formal properties of simple phrase-structuregrammars”, Z. Phonetik. Sprachwiss. Kommunikations-forsch. 14 (1961), pp. 143–172.2.D. C. Cantor, “On the ambiguity problem in Backus systems”, J. ACM 9:4 (1962),pp. 477–479.3.N. Chomsky and M. P. Schutzenberger, “The algebraic theory of context-free languages”,Computer Programming and Formal Systems (1963), North Holland, Amsterdam,pp. 118–161. (Хомский Н., Шютценберже М.
Алгебраическая теория контекстносвободных языков. — Кибернетический сборник, новая серия, вып. 3. — М.: Мир,1966, С. 195–242.)4.R. W. Floyd, “On ambiguity in phrase structure languages”, Communications of the ACM5:10 (1962), pp. 526–534.5.S. Ginsburg and G. F. Rose, “Some recursively unsolvable problems in ALGOL-like languages”, J. ACM 10:1 (1963), pp. 29–47.6.M.
L. Minsky, “Recursive unsolvability of Post’s problem of ‘tag’ and other topics in thetheory of Turing machines”, Annals of Mathematics 74:3 (1961), pp. 437–455.7.E. Post, “A variant of a recursively unsolvable problem”, Bulletin of the AMS 52 (1946),pp. 264–268.8.H. G.
Rice, “Classes of recursively enumerable sets and their decision problems”, Transactions of the AMS 89 (1953), pp. 25–59.9.A. M. Turing, “On computable numbers with an application to the Entscheidungsproblem”, Proc. London Math. Society 2:42 (1936), pp. 230–265.9.7. ËÈÒÅÐÀÒÓÐÀСтр. 421421422Стр. 422ÃËÀÂÀ 9. ÍÅÐÀÇÐÅØÈÌÎÑÒÜÃËÀÂÀ 10ÒðóäíîðåøàåìûåïðîáëåìûОбсуждение вычислимости переносится на уровень ее эффективности или неэффективности.
Предметом изучения становятся разрешимые проблемы, и нас интересует, какиеиз них можно решить на машинах Тьюринга за время, полиномиально зависящее от размера входных данных. Напомним два важных факта из раздела 8.6.3.• Проблемы, разрешимые за полиномиальное время на обычном компьютере, —это именно те проблемы, которые разрешимы за такое же время с помощью машины Тьюринга.• Практика показывает, что разделение проблем на разрешимые за полиномиальноевремя и требующие экспоненциального или большего времени, является фундаментальным. Полиномиальное время решения реальных задач, как правило, являетсяприемлемым, тогда как задачи, требующие экспоненциального времени, практически (за приемлемое время) неразрешимы, за исключением небольших экземпляров.В этой главе изучается теория “труднорешаемости”, т.е. методы доказательства неразрешимости проблем за полиномиальное время.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
