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

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

Гладкий А.В. Формальные грамматики и языки — Москва, 1973. — 368 c.
Скачать (прямая ссылка): formalnieidialogi1973.djvu
Предыдущая << 1 .. 60 61 62 63 64 65 < 66 > 67 68 69 70 71 72 .. 136 >> Следующая

б) Пользуясь результатом предыдущего пункта, показать, что подстановка автоматных языков в линейный дает линейный язык.
5.22. а) Показать, что для всякого детерминированного ДК-автомата (упражнение 5.21) можно построить эквивалентную ему однозначную линейную ОБ-грамматику.
б) Показать, что язык {xc.ty | х s {а, 6}*, у = A V у е d {а, &}*}, порождаемый однозначной линейной ОБ-грамматикой, не допускается никаким детерминированным ДК-автоматом [Диковский 1970].
5.23. Показать, что если L Е а*6*, где а, b — элементарные символы, и K(L) полулинейно (см. § 4.3), то L — линейный язык.
Замечание. Отсюда следует, что всякий ОБ-язык, содержащийся в а*Ь*, является линейным.
5.24. Если правая часть хаждого правила НС-грамматики Г содержит не более одного вхождения вспомогательного символа, то для Г можно построить эквивалентную ей линейную Б-грамматику. Доказать.
5.25. Указать способ непосредственного построения по дайной ОА-грамматике эквивалентной ей симметричной линейной ОБ-грамматики.
УПРАЖНЕНИЯ
183
5.26. Показать, что языки
| ni = 0, 1, ...}
и {k = 2, 3, ...)
(?*1^1 • • • xk*k !?*!»•••> xk s ^ ^ ^ ^ допускаются чисто стирающими МП-машин ами с 2к—1 поворотами и не допускаются никакими МП-машинами с меньшим числом поворотов.
5.27. Показать, что итерационно-линейный язык {апЬп\п = = 0, 1, ...}* не является ОБ-ОАЕВ-языком. Указать другие аналогичные примеры.
5.28. Показать, что языки
{ak+lbkcmdmbl\k, I, т = 0, 1, {ak+lbkambl+m\ k, I, m = 0, 1, ...},
{xyyzH | х, у, z е V *, ц (F) 2}
допускаются МП-машинами с тремя поворотами, но не допускаются никакими чисто стирающими МП-машинами.
5.29. Показать, что для каждой чисто стирающей МП-машины М можно построить эквивалентную ей МП-машину Л4', в которой для каждого полного вычисления найдется равносильное ему полное вычисление такое, что рабочая головка на каждом заданном расстоянии от начала ленты бывает не более четырех раз.
5.30. Пусть 3?0 ~ класс всевозможных языков, каждый из которых состоит из одной однобуквенной цепочки, и при каждом г = 0, 1,... 3?i+i есть класс всевозможных языков вида S (L; Oi, ..., an\Li,..., Ln), где L — линейный язык и Lu...,
е S’o U ••• U &1- Пусть, кроме того, 5Шг и 91г (г = 0, 1, ...) означают замыкание S’; относительно объединения и умножения, соответственно объединения, умножения и итерации. Показать, что для любого i = 0, 1, ... имеет место 3?i Е Яяг- cz S
5.31. Непосредственно (не пользуясь грамматиками) доказать «эффективную эквивалентность» центрально-подстановочных выражений и МП-машин с ограниченным числом поворотов.
5.32. Показать, что всякий ОБ-язык, содержащийся в а>1 ... в>к, где и»(, ..., а>к — фиксированные цепочки, порождается при к = 1
ОА-грамматикой и при к > 1 — ОБ-ОАЕВ-грамматикой Г такой, что /о(П ^ к—1 (ср. замечания к теореме 4.6 и к упражнению 5.23).
(Языки указанного здесь вида называются ограниченными; об ограниченных ОБ-языках см. [Ginsburg 1966, гл. V].)
5.33. Показать, что:
а) Линейный язык
Pk=* ... а1кЬПк\т1, = 0, 1,...;
nij =ге, V ... V mk = nk} (к = 2, 3, ...) допускается детерминированной чисто стирающей МП-мащиной С
184 СПЕЦИАЛЬНЫЕ КЛАССЫ БЕСКОНТЕКСТНЫХ ЯЗЫКОВ [ГЛ. 5
2k — 1 поворотами и не допускается никакой детерминированной МП-машиной с меньшим числом поворотов. ,
б) Линейный язык Я2 U Яз U ... допускается детерминированной чисто стирающей МП-машиной и не допускается никакой детерминированной МП-машиной с ограниченным числом поворотов.
в) Линейный язык
Rk = {a>lbqica>2bq2c ... са>к~1ЬЧк~1саРкЬ<,к+ГксЬГк~1с ...
... cbr,lcbr1 \pv qv г,-0, 1 ...; pj = <7j + rx V ... V Рк = Як +
(ft = 2, 3, ...)
допускается детерминированной МП-машиной с 2ft — 1 поворотами и не допускается никакой детерминированной МП-машиной с меньшим числом поворотов и никакой детерминированной чисто стирающей МП-машиной.
г) Б-ОАЕВ-язык R-i U Rs U ... (порождаемый грамматикой Г, для которой /о (Г) = 2) не допускается никакой детерминированной МП-машиной с ограниченным числом поворотов и никакой детерминированной чисто стирающей МП-машиной.
5.34. Показать, что в упражнении 4.25, в) можно взять в качестве Г итерационно-линейную ОБ-грамматику и в качестве Mi чисто стирающую МП-машину с выходом.
Ч
ГЛАВА 6
ДОПОЛНИТЕЛЬНЫЕ СВЕДЕНИЯ О БЕСКОНТЕКСТНЫХ ГРАММАТИКАХ.
ДРУГИЕ СПОСОБЫ ЗАДАНИЯ БЕСКОНТЕКСТНЫХ ЯЗЫКОВ
Наряду с Б-грамматиками и МП-машинами существует ряд других способов задания Б-языков. Многие из них вызваны к жизни потребностями приложений: различным способам задания языка отвечают различные способы описания синтаксической структуры его предложений (цепочек), отражающие различные лингвистические аспекты этой структуры. Некоторые из таких способов будут рассмотрены в настоящей главе. Здесь же нам будет удобно изложить еще несколько фактов, относящихся к «основным» способам задания Б-языков — Б-грамматикам и МП-машинам.
§ 6.1. Категориальные грамматики
Рассмотрим конечное множество W, которое будем называть словарем категорий, а его элементы — элементарными категориями. Введем в рассмотрение символы \, /, [ , ], не принадлежащие W. Из этих символов и элементов W будем строить выражения специального вида—категории (над W). Именно:
Предыдущая << 1 .. 60 61 62 63 64 65 < 66 > 67 68 69 70 71 72 .. 136 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

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

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed