Научная литература
booksshare.net -> Добавить материал -> Лингвистика -> Гладкий А.В. -> "Формальные грамматики и языки" -> 101

Формальные грамматики и языки - Гладкий А.В.

Гладкий А.В. Формальные грамматики и языки — Москва, 1973. — 368 c.
Скачать (прямая ссылка): formalnieidialogi1973.djvu
Предыдущая << 1 .. 95 96 97 98 99 100 < 101 > 102 103 104 105 106 107 .. 136 >> Следующая

(а) и (Р)), простой модификацией примера 2 из § 4.3*) (для у), примером к следствию из теоремы 5.7 (для (б)), примерами из упражнений 5.26, 5.28 (для' (е) — (0)). Свойства (а) и (р) при проектировании могут не сохраняться, но удовлетворяют указанному в конце формулировки теоремы 8.5 более слабому требованию (упражнение 4.35). То же верно, как нетрудно убедиться, для (у). Сохранение свойства (а) при пересечении с A-языком вытекает из упражнения 5.17, а), свойства (р)—из теорем 5.5 и 5.3, свойства (у)—из теорем 4.8 и 5.4.
Замечание. Утверждения следствия из теоремы 8.5 справедливы для любого словаря мощности, большей или равной 2 (упражнение 8.11). В случае одноэлементного словаря свойства (а)—(0) тривиальны. ?>
*) Именно, нужно убрать разделительный символ Ь..
§ 8.4] ПРОБЛЕМЫ, СВЯЗАННЫЕ С Б-ГРАММАТИК.АМИ 277
Другие примеры нераспознаваемых в классе Б-грамматик свойств и отношений см. в упражнениях 8.12, 8.13, 8.15, 8.22.
В заключение мы рассмотрим некоторые проблемы иного характера (второго из двух типов, указанных в § 8.1), а именно проблемы распознавания замещаемо-сти, взаимозамещаемости и конфигураций. Мы покажем, что они неразрешимы уже для линейных языков; более того, для подходящих линейных языков неразрешимы и соответствующие частные проблемы.
Укажем сцособ построения этих языков. Пусть М — произвольная ДЭ-машина, в рабочем алфавите которой выделен символ а0 такой, что все значения вычисляемой машиной М функции f являются цепочками в {ао}. Множество всех тех п, для которых а" суть значения f, будем обозначать Ем. При надлежащем выборе М мы можем, очевидно, получить в качестве Ем произвольное рекурсивно перечислимое множество. Будем, кроме того, считать, что машина М имеет единственное заключительное состояние qо, причем оно отлично от начального и не встречается в левых частях инструкций; понятно, что класс множеств lzM при таком ограничении не сужается. Положим далее V = {а, b} и построим по лемме 8.8 линейную ОБ-грамматику Гм, порождающую язык CVH(M). Рассмотрим произвольную цепочку со е %(RZ(M)) (см. стр. 272, 273). Эта цепочка единственным образом представляется в следующем виде: ?.(?o)M#*VФ)М#)М{/), где х и у — цепочки во входном и рабочем алфавитах М соответственно; обратно, всякая цепочка такого вида принадлежит h(R2(M)). Обозначим через Q^vM) и Q2(M) соответственно множества всевозможных цепочек вида
M?o)M#*V + V)c И bk+\(#xV$S/)X(#)X(y)bb,
где х, у — цепочки во входном и рабочем алфавитах М соответственно; k = \y\ \ с — символ, отличный от а и Ь. Положим Si(M) — X{R1(M){R{M))*)Qi(M) (г = 1,2) и и (М)=[Х (/?! (М) (R (M))* R2 (М))-Н (М)] ЬЬ и Sl (.М). Ясно, что S'(M) — ОА-язык, a S2(M) — линейный язык; соответствующие грамматики строятся без труда. Поэтому
278 неразрешимые Алгоритмические проблемы [Гл. ъ
лемма 8.8 дает возможность по машине М построить линейные ОБ-грамматики, порождающие Ll(M) и L2(M)
Непосредственно ясно, что в языке Ll(M) любая цепочка вида Х(Ф)[‘к{а0)]кЬЬ, k — О, 1, ..., замещаема на символ с, в то время как этот последний замещаем на ~К(ф)[К(а0)]кЬЬ тогда и только тогда, когда никакая •цепочка из Н(М) не оканчивается вхождением ЧтЦао))ьЬЬ — иначе говоря, когда не является зна чением /. Что же касается языка L2(M), то для нег принадлежность а* множеству значений f равносильна замещаем ости 6ft+4 на K(qo)- Заметим еще, что а) кодирование К можно произвести так, чтобы было i(4o)
= baab; б) в Ll(M) символ с можно с тем же резуль-' татом заменить цепочкой bbbb.
Подобрав машину М так, чтобы множество значений f было нерекурсивным, т. е. чтобы не существовал^ алгоритма, позволяющего по числу k узнать, принадле^-жит ли оно этому множеству*), мы получаем конкрет ные линейные ОБ-грамматики Ti с основным словарем {a,b,c}, Ti и Гг — обе с основным словарем {а, Ь) — такие, что не существует алгоритмов, позволяющих для: произвольной цепочки х е {а, Ь}* распознать: а) является ли х конфигурацией языка L(Ti) с результирующим с; .6) является ли х конфигурацией первого ранга языка
*) Таким свойством будет обладать, например, следующая ДЭ-машина (ниже описывается, как обычно, только принцип ее ра боты). Входной алфавит машины есть {а, &}. В начале работы ма шина переписывает входную цепочку х на рабочую ленту; затем он проверяет, является ли эта цепочка кодом в алфавите {а, Ь] некоторой Э-машины М' (см. стр. 258—259), и если да, то переписывает ее еще раз в другой зоне рабочей ленты (если нет, машина ломается) и далее работает в этой зоне, как М', используя «первый экземпляр» х на рабочей ленте для «получения инструкций» (это значит, что перед каждым очередным преобразованием «второго экземпляра» головка должна найти в «первом экземпляре» код той инструкции, которую следует применить на данном шаге). Если этот процесс окончится вычислением значения соответствующей функции от х, то все содержимое рабочей ленты заменяется однобуквенным кодом М' в алфавите {<Зо}, после чего машина останавливается, перейдя предварительно в 'заключительное состояние; в противном случае машина работает вечно. Таким образом, цепочка а* тогда и только тогда при-, надлежит множеству значений функции, которую вычисляет по-, строенная машина, когда эта цепочка есть код некоторой самоприменимой машины М'. Остается воспользоваться леммой 8.1.
Предыдущая << 1 .. 95 96 97 98 99 100 < 101 > 102 103 104 105 106 107 .. 136 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed