Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 95
Текст из файла (страница 95)
Мы утверждаем, что Е, является КС-языком. В отличие от Тл, грамматику для Е, построить нелегко, но можно построить МП-автомат, точнее — детерминированный МП-автомат. Конструкция описывается в следующей теореме. Теорема 9.21. Если „— язык для списка А, то А„является контекстно-свобод- ным языком. Доказательство. Пусть Х вЂ” алфавит цепочек из списка А = (вп ж,, ..., вь), а У= (а,, а, ..., а,) — множество индексных символов. ДМПА Р, который по построению должен допускать 1А, работает следующим образом. Обозревая символ из Х, Р записывает его в магазин.
Поскольку все цепочки из Х* принадлежат 1,, Р допускает их по мере чтения. При виде индексного символа из 1, скажем, аь Р просматривает магазин, чтобы проверить, образуют ли символы из его верхней части цепочку н,, т.е. обращение соответствуюшей цепочки: 416 ГЛАВА 9. НЕРАЗРЕШИМОСТЬ а) если это не так, то входная цепочка, а также всякое ее продолжение принадлежат Е . Поэтому Р переходит в допускающее состояние, в котором он до- читывает вход, не изменяя содержимое магазина; б) если цепочка и,к была извлечена из верхней части магазина, но маркер дна магазина не показался на вершине, то Р допускает, но запоминает в своем состоянии, что он ищет только символы из 1 и может еше встретить цепочку из Ед (которую не донуслгинг). Р повторяет шаг 2 до тех пор, пока вопрос о принадлежности входа языку А„будет оставаться не- разрешенным; в) если и,к была извлечена и показался маркер дна магазина, то Р прочитал вход, принадлежащий (,„.
Р не допускает этот вход. Однако, поскольку всякое продолжение этого входа уже не может содержаться в С„, Р переходит в такое состояние, в котором он допускает все последующие входы, не изменяя магазин. 3. Если после того, как Р считал один или несколько символов из!, он встречает еше один символ из Х, то входная цепочка не может принадлежать Ам поскольку имеет неправильную форму. Поэтому Р переходит в состояние, в котором он допускает этот и все последующие входы, не изменяя магазин. (:2 Для получения результатов о неразрешимости КС-языков можно использовать ),„, г,в и их дополнения различными способами.
Часть этих фактов собрана в следующей теореме. Теорема 9.22. Пусть бг и Сг — КС-грамматики, а гг — регулярное выражение. Тогда неразрешимы следующие проблемы: а) ь(ггг) П ь(ггг) = ~? б) ЦСг)=ЦОг)? в) ЦОг) = А(гг)? г) верно ли, что Цс г) = 7~ для некоторого алфавита Т? д) цаг) айаг)? е) ЦН) с Е(бг)? Доказательство. Каждое из доказательств представляет собой сведение ПСП. Покажем, как преобразовать экземпляр (А, В) ПСП в вопрос о КС-грамматиках и/или регулярных выражениях, который имеет ответ "да" тогда и только тогда, когда данный экземпляр ПСП имеет решение. В некоторых случаях ПСП сводится к самому вопросу, сформулированному в теореме, в других же случаях — к его дополненао.
Это не имеет значения, поскольку, если показано, что дополнение проблемы неразрешимо, то сама 9.5. ДРУГИЕ НЕРАЗРЕШИМЫЕ ПРОБЛЕМЫ 417 проблема также не может быть разрешимой, так как рекурсивные языки замкнуты отно- сительно дополнения (теорема 9.3). Алфавит цепочек данного экземпляра ПСП обозначим Х, а алфавит индексных символов — Х В наших сведениях будем опираться на то, что Еь, ьв, Г н Га имеют КС-грамматики.
КС-грамматики либо строятся непосредственно, как в разделе 9.5.2, либо вначале строятся МП-автоматы для языков-дополнений (см, теорему 9.21), а затем с помощью теоремы б.!4 они преобразуются в КС-грамматики. Пусть Е(б~) = Ах и ЦО.) = Се. Тогда ЦОг)1) ЦОг) — множество решений данного экземпляра ПСП.
Пересечение пусто тогда и только тогда, когда решений нет. Отметим, что технически мы свели ПСП к языку, который состоит нз пар КС-грамматик с непустым пересечением нх языков, т,е. показали, что проблема "является ли пересечение языков двух КС-грамматик непустым?" неразрешима. Однако, как указано во введении к доказательству, доказать неразрешимость дополнения проблемы — это то же самое, что доказать неразрешимость самой проблемы. 3.
Рассуждения точно такие же, как и в п. 2, но полагаем В регулярным выражением (Х О))'. Достаточно рассуждений п. 3, поскольку Х () 1 — единственный алфавит, замыкани- ем которого может быть 1.„() 1.„. Пусть б, — КС-грамматика для (Х0/) н Ор — КС-грамматика лля Л~ 0 Г„. Сле- довательно, ЦО>) с Цбз) тогда и только тогда, когда Г 0 ь'„= (Х 0 1), т.е. тогда и только тогда, когда данный экземпляр ПСП не имеет решения.
Рассуждения точно такие же, как и в п. 5, но полагаем Н регулярным выражением (ХО1), аЦО!) — Г, 0 ~.а. 9.5.4. Упражнения к разделу 9.5 (в) Пусть Š— множество (кодов) КС-грамматик О, у которых Цб) содержит хотя бы один палиндром. Покажите неразрешимость Е. Указание. Сведите ПСП к ь путем построения по каждому экземпляру ПСП грамматики, содержащей палиндром тогда н только тогда, когда этот экземпляр ПСП имеет решение. 9.5.1. 418 ГЛАВА 9.
НЕРАЗРЕШИМОСТЬ 2. Поскольку КС-языки замкнуты относительно объединения, то можно построить КС- грамматику б~ для Е, 0 Х . Поскольку (Х 0 1) — ре~улярное множество, то для него, конечно же, можно построить КС-грамматику Оь Далее, 1,, 0 ьв = 1.„П 1.» . Таким образом, в ЦО,) отсутствуют лишь цепочки, которые представляют решения данного экземпляра ПСП. Цбг) содержит все цепочки из (Х О 1), так что эти языки совпадают тогда и только тогда, когда данный экземпляр ПСП не имеет решения. (!) Покажите, что язык Ех 0 Е является регулярным тогда и только тогда, когда он представляет собой множество всех цепочек над своим алфавитом, т.е.
экземпляр (А, В) ПСП не имеет решения. Таким образом, докажите неразрешимость вопроса, порождает ли КС-грамматика регулярный язык. Указание. Допустим, решение ПСП существует; например, в Ех () 1.„нет цепочки их, где зг — цепочка из алфавита экземпляра ПСП, а х — соответствующая цепочка индексных символов, записанная в обратном порядке. Определим гомоморфизм Ь(0) = и и Ь(1) =х. Тогда, что представляет собой Ь ~(Е, 0 Ев )? В доказательстве того, что язык Е, () Е, нерегулярен, используйте замкнутость регулярных множеств относительно обратного гомоморфизма и дополнения„а также лемму 9.52.
1. зг и х — цепочки над алфавитом Х данного экземпляра ПСП. 2. у и х — цепочки над алфавитом индексов Е данного экземпляра. 3. я' — символ, не принадлежащий ни Х, ни Е 4. них~. х не совпадает с тем, что порождает цепочка индексов у в соответствии со списком В. и не совпадает с тем, что порождает цепочка индексов х в соответствии со списком А. Отметим, что Е„в состоит из всех цепочек, принадлежащих Х ФХ П П, если только экземпляр (А, В) ПСП не имеет решения, но независимо от этого Ехв является КС-языком.
Докажите, что Е„является КС-языком тогда и только тогда, когда решения нет. Указание. Как и в упражнении 9.5.2, используйте прием с обратным гомоморфизмом, а для того, чтобы добиться равенства длин тех или иных подцепочек, воспользуйтесь леммой Огдена, как в указа- нии к упражнению 7.2.5, б. 9.5. ДРУГИЕ НЕРАЗРЕШИМЫЕ ПРОБЛЕМЫ 419 о накачке для регулярных множеств. 9.5.3. (11) Вопрос о том, является ли дополнение КС-языка также КС-языком, неразрешим. С помощью упражнения 9.5.2 можно показать, что неразрешим вопрос о том, является ли дополнение КС-языка регулярным языком, но это не одно и то же.
Чтобы доказать первое утверждение, нужно определить другой язык, который представляет цепочки, не являющиеся решениями экземпляра (А, В) ПСП. Пусть Ехв есть множество цепочек вида иФхяуяк со следующими свойствами. 9.6. Резюме Рекурсивные и релурсивно-пвречисзииые языки. Языки, допускаемые машинами Тьюринга, называются рекурсивно-перечислимыми (РП), а РП-языки, допускаемые МТ, которые всегда останавливаются, — рекурсивными. Дополнения релурсивных и РГГ-языков. Множество рекурсивных языков замкнуто относительно дополнения, и если язык и его дополнение являются РП, то оба они рекурсивны. Поэтому дополнение языка, являющегося РП, но не рекурсивным, не может быть РП.
Разрешимость и нвразрешииость. "Разрешимость" есть синоним 'рекурсивности", однако языки чаще называются "рекурсивными", а проблемы (которые представляют собой языки, интерпретируемые как вопросы) — "разрешимыми". Если язык не является рекурсивным, то проблема, которую выражает этот язык, называется "неразрешимой". Язык Гь В этот язык входит каждая цепочка в алфавите ~0, )), которая, будучи проинтерпретированной как код МТ, не принадлежит языку этой МТ. Язык Г является хорошим примером не РП-языка, т.е. его не допускает нн одна машина Тьюринга. Универсальный язык. Язык Г,„состоит нз цепочек, интерпретируемых как код МТ, к которому дописан ее вход.
Цепочка принадлежит Г,„, если эта МТ допускает данный вход. Язык Г.„— это пример РП-языка, который не является рекурсивным. Теорема Ройса. Всякое нетривиальное свойство языков, допускаемых МТ, является неразрешимым. Например, множество кодов машин Тьюринга, допускающих пустой язык, согласно теореме Райса является неразрешимым.
В действительности этот язык не является РП, хотя его дополнение — множество кодов МТ, допускающих хотя бы одну цепочку, — является РП, но не рекурсивным. Г!роблема соответствий ГГоста. Заданы два списка, содержащие одинаковое количество цепочек. Спрашивается, можно ли, выбирая последовательности соот- ветствующнх цепочек из этих двух списков, построить путем их конкатенации одну и ту же цепочку. ПСП является важным примером неразрешимой проблемы. Сводимость ПСП к ряду других проблем обеспечивает доказательство их нераз- решимости. Неразрешииыв проблемы, связанные с контекстно-свобадныли языками. Посредством сведения ПСП можно доказать неразрешимость многих вопросов о КС- языках или их грамматиках. Так, например, неразрешимы вопросы о неоднозначности КС-грамматики, о включении одного КС-языка в другой или о пустоте пересечения двух КС-языков.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
