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

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

Гладкий А.В. Формальные грамматики и языки — Москва, 1973. — 368 c.
Скачать (прямая ссылка): formalnieidialogi1973.djvu
Предыдущая << 1 .. 50 51 52 53 54 55 < 56 > 57 58 59 60 61 62 .. 136 >> Следующая

4.35. Показать, что если U и V — непересекающиеся алфавиты, isti* и je К*, то:
а) по детерминированной МП-машине, допускающей язык Ly, можно построить детерминированную МП-машину, допускающую L;
б) по однозначной Б-грамматике, порождающей Ly, можно построить однозначную Бграмматику, порождающую L.
4.36. Показать, что для всякой грамматики, левые части правил которой не содержат основных символов, а правая часть каждого правила содержит хотя бы одно вхождение основного символа, можно построить эквивалентную ей Б-грамматику [Ginsburg — Greibach 1966(a)].
*) Обращением называется операция, сопоставляющая языку L язык L = {? | х е L] (а также ее результат).
\
ГЛАВА 5
НЕКОТОРЫЕ СПЕЦИАЛЬНЫЕ КЛАССЫ БЕСКОНТЕКСТНЫХ ЯЗЫКОВ § 5.1. Автоматные и обобщенные автоматные языки. Конечные автоматы
В предыдущей главе мы видели, что присоединение к Б-грамматикам правил вида А —? А делает класс порождаемых этими грамматиками языков в ряде отношений более естественным (достаточно вспомнить об удобстве описания с помощью МП-машин). В еще большей степени это справедливо, как мы скоро убедимся, для А-грамматик. Поэтому их изучение мы начнем со следующего определения.
(ОБ-) грамматика называется обобщенной автоматной грамматикой (ОА-г р а м м а т и к о й), если каждое ее правило имеет вид А-*аВ, А —*• а или Л->-А, где А, В — вспомогательные символы и а — основной символ. Язык, порождаемый ОА-грамматикой, называется ОА-я зыком.
Полезно заметить, что в ОА-грамматике всякая промежуточная цепочка полного вывода имеет вид хВ, где х — цепочка в основном словаре и В — вспомогательный символ.
Теорема 5.1. Для любой Ok-грамматики Г можно построить А-грамматику Г' такую, что ?(Г') = L(T) — -{А}.
Доказательство. С помощью процедуры, прит мененной в доказательстве леммы 4.2, можно перестроить Г так, чтобы начальный символ не встречался в правых частях правил. После этого достаточно для каждой пары правил вида А—*аВ, 5-* Д добавить к схеме
158 СПЕЦИАЛЬНЫЕ КЛАССЫ БЕСКОНТЕКСТНЫХ ЯЗЫКОВ [ГЛ. 5
грамматики правило Л-»-а (если оно не содержалось там ранее) и затем изъять все правила вида А -* А.
Будем называть ОА-'грамматику стандартной, если она не имеет правил вида А —*? а. Для каждой ОА-грамматики легко построить эквивалентную ей стандартную ОА-грамматику: достаточно добавить к вспомогательному словарю новый символ К, к схеме — правило К —*? Л и заменить каждое правило А —? а правилом А —* аК.
Стандартные ОА-грамматики допускают следующее очень простое и. наглядное изображение. Рассмотрим мультиграф, узлами которого служат вспомогательные символы данной грамматики и для каждой пары узлов А, В из А в В идет столько дуг, сколько грамматика имеет правил вида А аВ\ каждую из этих дуг пометим соответствующим основным символом а. Начальный символ будем называть начальным узлом, а каждый узел А, для которого имеется правило А —»? Л, — заключительным. Построенный таким образом мультиграф с помеченными дугами и выделенными в множестве узлов начальным и заключительными узлами мы будем называть диаграммой данной грамматики.
Нестандартной ОА-грамматике мы также будем сопоставлять диаграмму, совпадающую, по определению,
о О 'с~ъук у.а.\у к V17 1 в к
Рис. 8.
\
с диаграммой стандартной грамматики, полученной из данной указанным выше способом.
На рис. 8,а) показана диаграмма Стандартной ОА-грамматики со схемой {/ —*? аА, I —>? ЬА, А —*? dA, А -* ЬС, С сВ\ В т* ЬА, С —» i?D, С —*? fD, В —? el, 1 —? А, В-*- А,
§5.1] АВТОМАТНЫЕ И ОБОБЩЁННЫЕ АВТОМАТНЫЕ ЯЗЫКИ Jgg
D->-A}. На рис. 8,6), в) показаны диаграммы А-грамма-тик примеров 2 и 4 из § 1.3. Здесь и далее начальный узел обозначается символом /, заключительные узлы выделяются подчеркиванием.
Если Л0, Ли ..., Ап — путь в диаграмме грамматики Г и для каждого i = 1........п имеется дуга, иду-
щая из Лг-1 в Ai й помеченная символом а, мы будем говорить, что данный путь производит цепочку ai ... ап. Всякий путь длины 0 производит, по определению, цепочку Л. Цепочка х будет, очевидно, производиться путем, начинающимся в А и оканчивающимся в В, тогда и только тогда, когда А^.хВ (Н озна-
г
чает здесь то же, что на стр. 124).
Будем называть путь Ло, ..., Л„ циклом, если Л0 = Ап, и полным путем, если Л0— начальный узел и Ап — заключительный узел. Между полными выводами в Г и полными путями диаграммы имеется очевидное взаимно однозначное соответствие, и цепочка принадлежит L(r) тогда и только тогда, когда она производится некоторым полным путем.
Диаграммы позволяют, в частности, особенно просто интерпретировать для ОА-грамматик понятия и утверждения из § 4.2. Так, зависимость В от Л означает наличие пути из Л и В, бесплодность Л — отсутствие пути из Л в заключительный узел, неустранимость Л — наличие проходящего через Л полного пути, цикличность Л — наличие проходящего через Л цикла. Выбрасывание всех устранимых узлов сразу дает теперь приведенную грамматику; приведенная грамматика порождает конечный язык тогда и только тогда, когда ее диаграмма не содержит циклов.
Заметим еще, что AeL(T) тогда и только тогда, когда начальная вершина диаграммы является заключительной.
Предыдущая << 1 .. 50 51 52 53 54 55 < 56 > 57 58 59 60 61 62 .. 136 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

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

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed