Гладкий - Формальные грамматики и языки - 1973 (947381), страница 56
Текст из файла (страница 56)
Положим 84 (М) = 74(174 (М)(Я (М))') Г('(М) (1= 1, 2) и Е (М)=[!((!Г4(М)()Г(М)) р,,(М)) — Н(М)]ЬЬ()О'(М). Ясно, что 5'(М) — ОА-язык, а Яе(М) — линейный язык; соответствующие грамматики строчтся без труда. Поэтому 278 неРАЗРеп!имые АлГОРитмические провлемы (гл.
з УПРАЖНЕНИЯ 2?9 Лемма 8.8 дает возможность по машине М построить линейные ОБ-грамматики, порождающие 1.!(М) и 1Р(М) Непосредственно ясно, что в языке 1.!(М) любая цепочка вида Л(4Е)[Х(аа))АЬЬ, й = О, 1, ..., замещаема на символ с, в то время как этот последний замещаем на А(чф) [А(ао)]АЬЬ тогда и тольно тогда, когда никакая цепочка из Н(М) не оканчивается вхождением Х(®[) (ао))АЬЬ вЂ” иначе говоря, когдааоз не является зна чением (.
Что же касается языка (.э(М), то для нег пРинадлежность поз множествУ значений 1 Равносильна замещаемости Ьь+' на )ь(до). Заметим еще, что а) коди-. рование )ь можно произвести так, чтобы было Х(!)о) = = Ьаай; б) в 1.!(М) символ с можно с тем же резуль-' татом заменить цепочкой ЬЬЬЬ. Подобрав машину М так, чтобы множество значений ! было нерекурсивным, т.е. чтобы не существовало алгоритма, позволяюш(рго по числу я узнать, принадлежит ли оно этому мно)кеству *), мы получаем конкрет ные линейные ОБ-грамматики Г! с основным словарем » (а, Ь, с), Г, и Гз — обе с основным словарем (а, Ь) — такие, что не существует алгоритмов, позволяющих для. произвольной цепочки х еи (а, Ь)' распознать: а) является ли х конфигурацией языка ь(Г!) с результирующим с б) является ли х конфигурацией первого ранга языка ') Таким свойством будет обладать, например, следующая ДЭ-мэшинз (ниже описывается, кзк обычно, только принцип ее рв боты).
Входной алфавит машины есть (а, й). В начале работы мв шина переписывает входную цепочку х ив рабочую ленту; затем он проверяет, является ли этз цепочка кодом в алфавите (а,э) некото'рой Э-мзшины М' (см. стр. 258 — 259), и если дз, то переписывает ее 'еще рзз в другой зоне рабочей ленты (если нет, мзшиив ломается) и далее работает в этой зоне, кзк М', используя «первый экземпляр» х нз рабочей ленте для «получения инструнций» (зто значит, что перед каждым очередным преобразованием «второго экэемплярз» головка должна найти в «первом экземпляре» код той инструкции, которую следует применить нв данном шаге). Если этот процесс окончится вычислением значения соответствующей функции от х, то все содер.
жимое рабочей лепты заменяется одн о букв ен и ы и кодом М' в алфавите (а«), после чего машина останавливается, перейдя предварительно в ззключительное состояние; в противном случае машина работает вечно. Таким образом, цепочка ао тогда и только тогда при. з нзллежит множеству значений функции, которую вычисляет по. строенная машина, когда зтз цепочка есть код некоторой сзмоприменимой машины М'. Остается воспользоваться леммой 8.!. 7.(Г!) с результирующим с; в) замещаема ли цепочка ЬЬЬЬ на х относительно Г.(Г!); г) замещаема ли х на ЬааЬ относительно 7.(Гз); д) являются ли х и ЬЬЬЬ взанмозамещаемыми относительно Т.
(Г',). По поводу возможности уменьшить здесь мощности словарей см. упражнения 8.19 н 8.20, по поводу распознавания конфигураций высших рангов †упражнение 8.21. Упражнения 8.(, Закодировав всевозможные грамматики, кзк в донзззтельстве теоремы 2.4, назовем грамматику Г с ам опор ождв ю щей, если наименьший (в лексикографическом порядке) из ее кодов принадлежит ь(Г). показать, что сзмопорождземость нерзспоэнзввемз в классе Г«), (Указание. Показать, что множество наименьших кодов несзмопорождвющих грамматик не порождзется никакой грзммзтикой.1 8.2.
Покивать, что следующие свойства грамматик нерзспознв-. вземы в классе Г: в) иметь ограниченное растяжение (т. е. емкость, мзжорнруемую линейной функцией); б) быть грамматикой без рзстяжепия. 8.3. Можно ли перенести результат упражнения 8.! нв класс НС» 8.4. в) Пусть ь« — произвольный НС-язык, Ь вЂ” произвольный не.
пустой НС.язык и Ы' — класс языков, содержащий ьа 0 ь и не содержзщий ни одного языка вида ь«с! (ь — (х)), где хш ь. Показать, что свойство принадлежать 2' нерзспознзвземо в классе НС. б) То же с изменой языков ь — (х) нз языки вида ь — Е', где ь' — непустое конечное подмножество !..
8эй Покзззть, что в классе НС нерзспознзвземо свойство при. нздлежзть Я~ ~(НС), 8 8. Язык !. в словаре У и и е е т н е т р и в и в л ь н у ю з з м е. щз ем ость, если нзйдется хотя бы одна пара цепочек х, у ш У', х чь у, такая, что х является подцепочкой некоторой цепочки из !. н при этом х =!ь у. Показать, что свойство иметь нетривизльиую замеу,ь щземость нерзспознввземо в классе НС. 8.7. Усилить лемму 8.! и теорему 8.2, показав, что следующие множества не могут быть рекурсивно перечислимыми: з) множество кодов несзмопркменимых Э-мзшии; б) множество кодов таких ДЭ-мишин, что вычисляемые ими функции облздзют некоторым свойством, справедливым для нигде че определенной функции, но не для всех чзстичио рекурсивных функций. 8.8.
Используя упражнение 8.7, б), показать, что следующие мнозсествз не могут быть рекурсивно перечислимыми: *) à — класс всех грамматик (стр. 30), 289 неРАВРешимые АлГОРитмические пРОелемы [Гл, з 281 УПРАЖНЕНИЯ а) множество кодов грамматик, обладающих некоторым инвари антным и нетривиальным в классе Г свойством, справедливым для грамматик, порождающих пустой язык; б) множество кодов НС-грамматик, для которых порождаемые ' ими языки принадлежат некоторому классу, удовлетворяющему условию леммы 8.4 или теоремы 8.3 (но не дополнение к такому множеству!).
8.9. Назовем свойство языков в словаре У «булевски перечисли-, мым», если оно представимо в виде В, з)... з/Вгьз/ ..., где В;— булевы свойства, занумерованные с помощью некоторого эффективно-: го кодирования булевых выражений (от переменных Хь ..,, Х" ..., где Х, означает «юл ш Е»; ыл — цепочка с номером и, см. стр. 267), и (!ь ..,, но ...) — рекурсивно перечислимое множество натуральных ' чисел. Показать, что если Ег — класс грамматик такой, что соответствующий класс Ы'(Ь" ) содержит вместе с наждым конечным языком все ' его НС-надъязыки и множество кодов НС-грамматик из Ьг рекурсивно перечислныо, то свойство быть НС-языком, принадлежащим 2'(К'), булевски перечислимо.
[Указание. Использовать упражнение 8.8, 6).) 8.16. Опираясь непосрелственно на лемму 8.8, доказать, что в, классе линейных языков нераспозуаваемы свойства быть ОЛ-языком' и иметь бесконтекстное дополнениц 8.11. Показать, что все результаты следствия нз теоремы 8.5 справедливы для любого словаря мощности, большей или равной 2, [Указание. Установить сводимость проблем распознавания свойств" (я) — (6) для словаря мощности 4 к соответствующим проблемам для словаря мощности 2.] 8Л2. Доказать нераспозиаваемость в классе Бг, где У вЂ” словарь мощности, большей или равной 2, следующих свойств языков: а) порождаться Б-грамматикой, активная емкость которой не превышает заланного числа Ь; б) быть ОЛЕ-языком; в) удовлетворять условию к =аз у, где х и у — произвольные ' У,Р.
фиксированные различные цепочки в У; г) иметь заданную конфигурацию заданного ранга с заданным результирующим; д) содержать бесконечный ОЛ-язык [СбпзЬпгд !966, лемма 4,3.4]. 8.13. Доказать нераспознаваемость в классе Бз, где У вЂ” словарь мощности, большей или равной 2, следующих отношений между языками Е1 и Ез. а) пустоты пересечения Еа П Ет; б) бесконтекстности пересечения Е,() Ем в) существования конечного автомата с выходом (упражне-. ние 5.8), переводящего Е~ в бесконечное подмножество Ез [О!пзЬнгй 1966, теорема 4.3.2].
8.14. Доказать, что для словаря У мощности, большей нли рав. ной 2, невозможен алгоритм, позволяющий для любых лвух систем л цепочек хь ..., х и уь ..., у в У узнать, существует ли такая„ (непустая) последовательность чисел й, ..., Д (!ь = 1, ..., и), что х; ... хгь —— уз ., у,з (теорема Поста о проблеме соответствий; см.[роз( !946, Марков 1954]). [указание. Доказать нераспознаваемость в классе линейных ОБ-грамматик с основным словарем (а, Ь, с, 8, е) свойства языка иметь непустое пересечение с Еа(с(, е)', где !а = (хсх[х ея (а, Ь)*).
При этом можно рассуждать по аналогии с доказательством теоремы 8.5.] 8.15. Используя упражнение 8.14, доказать нераспозпаваемость однозначности г р а м мат и к и в классе Бг, где Р(У) з 2. 8.16. Указать алгоритмы, распознающие для любых ОЛ-грамматик (а тем самым и для любых ОБ-грамматик с одноэлементным основным словарем — см, замечание к теореме 4,6) свойства и отношения, перечисленные в следствиях из теоремы 8.4. 8.17. Показать, что если Š— рекурсивный язык, то для любой цепочки х дополнения к множествам Ф,(Е) и Ч'„(Е) (см. стр.
3!8) рекурсивно перечислимы. 8.18. Пусть !т — рекурсивное множество точек целочисленной плоскости (т, и) (лт, п = О, 1. ..,'), проекция которого на ось гл не рекурсивна. Положим Е, = [ЬЬа+' [ и = О, 1, ...) 0 [п~+'Ьо~' [ (т, л) ф)з); Ез=[(уо»з~ Ь) (Ь а"+'Ь ) ] (ю, л) зьц; р, 9=1, 2, ...) [) () (!(Ьплз+'Ь) (Ь пн+'Ь ) [(ю. л) ~В! р, о=1, 2, ...). Показать, что: а) множества Фьэ(Ез) и Чгаз(Е~) не рекурсзвны; б) для любой цепочки хш(п,Ь)" множества Ф (Еэ) и Ч',(Ез) рекурсивны, однако Ф(Е») и Ч'(Ез) не рекурсивны. [Гладкий !963 (б)].
8.10. Показать, что для любого рекурсивного языка Е в одно- элементном словаре Ф(Е) и Ч'(Е) рекурсивны [Гладкий 1963 (бЦ. 8.26. Построить линейный язык в лвухэлементном словаре с неразрешимой проблемой распознавания конфигураций. 8.21. Указать примеры линейных языков, для которых не существует алгоритмов, позволяющих по заданной цепочке х распознать: а) является ли х конфигурацией заданного ранга г (для кажлого г — свой язык); б) является ли х конфигурацией. [Лучкин 1966]. [Указание.
Использовать конструкцию упражнения ПП.7.) 8.22. Показать, что не существует алгоритма, позволшощего для любой Б-грамматики Г найти наименьшее число вспомогательных сныволов Б-грамматики, эквивалентной Г, [Укпзпние. Использовать упражнение 42!.] системы состквляюших 283 4 Пл.н ПРИЛОЖЕНИЕ 1 СИСТЕМЪ| СОСТАВЛЯЮЩИХ И ДЕРЕВЪЯ СИНТАКСИЧЕСКОГО ПОДЧИНЕНИЯ В современной лингвистике используются различные ' способы описания синтаксической структуры предложения, из которых наиболее употребительны два — описание с помощью систем5«СоставляЮШих и опиСание с по- ' мощью деревьев синтаксического подчинения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
