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

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

Гладкий А.В. Формальные грамматики и языки — Москва, 1973. — 368 c.
Скачать (прямая ссылка): formalnieidialogi1973.djvu
Предыдущая << 1 .. 35 36 37 38 39 40 < 41 > 42 43 44 45 46 47 .. 136 >> Следующая

3.18. Назовем грамматику Г= (V, №, I, R) обобщенной НС-г рамматикой (ОНС-г рамматикой), если каждое ее правило имеет вид ?i/}g2—*? ?i0?2, где А е W и ?i, |2, 0 s (VUW)*. Показать, что для произвольной грамматики можно построить эквивалентную ей обобщенную НС-грамматику и притом без увеличения временной сложности. [Указание. Рассуждать по аналогии с доказательством теоремы 3.6.]
3.19. Для каждой из следующих функций i|)i построить неукорачивающую грамматику, порождающую язык Lи такую, что ее временная сложность мажорируется квадратичной функцией: $,(.*) = = bxb; 1|з2 (-*) = bxb\ i|)3(x) = bJcxJcb.
3.20. а) Построить неукорачивающую грамматику Г, порождающую язык [xbx^x^ Ьх \ х е {aia2}+} и такую, что Тр (я) ^ я Уя.
б) Показать, что для любой монотонной числовой функции fi(m), по порядку не меньшей m и такой, что множество {h(m)\m= 1, 2, ..является НС-языком, можно подобрать функцию i|), отображающую V в Ь[а\, а%}* Ь(а\, 02 s V, Ь ф V) и удовлетворяющую условию |i|)(x) I ^ М 1*1) • 1*1, так, чтобы существовала НС-грамматика, порождающая язык и имеющая временную сложность, по порядку не превосходящую и-/г1 (л).
114
ГРАММАТИКИ СОСТАВЛЯЮЩИХ
[ГЛ. 3
3.21. а) Пусть ф (л-) == 66. Построить Б-грамматику, порождающую язык C'L^. [Указание. Использовать конструкцию примера 12 из § 1.З.]
б) Очевидно, при ty(x) = bxb имеем = L, Л L2, где Ц = = {хЬЛЪу \х,у<= (а,, а2}+}, L2 — {xbCjby \х,у*= {аи а2}+}. Построить Б-грамматики, порождающие Ц и Ц.
3.22. а) Построить грамматику Г с правилами вида а Л -* а|3 и А -*? р, где А — вспомогательный символ и а, р — элементарные символы, такую, что Г-образ языка Р* (Р — некоторый символ) есть [an*hbn | п = 1, 2, ...; k = 0, 1, ...}.
б) Показать, что для любой НС-грамматики Г можно построить' грамматику Tt с правилами такого же вида, как в пункте а), и грамматику Гг с правилами вида Аа -> ра и А -*? р (смысл обозначений тот же) такие, что L(T) будет Гг-образом ГкОбраза языка Р+ [Haines 1969].
3.23. Построить левоконтекстные НС-грамматики, порождающие следующие языки:
а) {aW | п = 1, 2, ...};
б) [xJtx\x^{al.......ajJ+};
в) {апЬа2>1Ьап\п = \, 2, ...}.
3.24. Проанализировав доказательство теоремы 3.8, показать, что для всякой НС-грамматики Г можно построить левоконтекстнуго НС-грамматику Г', эквивалентную Г и такую, что Тг, (п) < [71 г (и)]2
ГЛАВА 4
БЕСКОНТЕКСТНЫЕ ГРАММАТИКИ И МАШИНЫ С МАГАЗИННОЙ ПАМЯТЬЮ
§ 4.1. Некоторые вспомогательные утверждения
В этом параграфе мы докажем несколько простых лемм о Б-грамматиках, которые пригодятся нам в дальнейшем.
Лемма 4.1. Для любой Ъ-грамматики можно построить эквивалентную ей Ъ-грамматику, схема которой не содержит правил вида А-+В, где А, В — вспомогательные символы.
Доказательство. Пусть Г = (V, W, I,R) — Б-грамматика. Введем на W бинарное отношение рг; АргВ тогда и только тогда, когда схема Г содержит правило А —> В. Граф (W, рг) обозначим Gr. Если А, В е W и в С?г имеются пути из АвВи из ВвА (допускаются и пути нулевой длины), то будем писать ЛагВ. Ясно, что аг есть отношение эквивалентности. Со* поставим каждому классу 5 е W/о г новый символ as и положим rt = (V, Wu aSi, Ri), где Wi ={as|S e Wlor}, Si — класс, содержащий I, и Ri получается из R заменой в левых и правых частях всех правил каждого вхождения каждого символа А е W вхождением символа as(a>, где 5(Л) —класс, содержащий Л. Легко видеть, что Ti эквивалентна Г и граф Gr, не содержит замкнутых путей ненулевой длины.
Пусть теперь В — висячий неизолированный узел графа Gп и Аи ..., Ак — все узлы, из которых идут дуги в В. Устраним из схемы П правила Ах -> В, ...
116 Б-ГРАММАТИК.И И МАШИНЫ С МАГАЗИННОЙ ПАМЯТЬЮ [ГЛ. 4
..., Au—уВ и одновременно добавим к ней всевозможные правила вида Ai -»г|э...—*- чр, где гр — правая
часть какого-либо правила Ti с левой частью В. Полученную так грамматику обозначим Гг. Поскольку В — висячий узел Gr,> среди новых правил нет ни одного правила вида А\ —* С, где С е W'i, так что граф Gга имеет меньше дуг, чем Gг,. В то же время Гг эквивалентна Гь Продолжая этот процесс, получим в конце концов грамматику Г3, эквивалентную Г4 и такую, что все узлы графа Gr, изолированные; это и требовалось сделать.
Лемма 4.2. Для всякой Ъ-грамматики можно построить эквивалентную ей Ъ-грамматику, правые части правил которой не содержат начального символа. Если при этом исходная грамматика удовлетворяет требованию леммы 4.1, то новую грамматику можно построить так, чтобы и она ему удовлетворяла. Если исходная грамматика автоматная, то и новую можно сделать автоматной.
Доказательство. Достаточно добавить к вспомогательному словарю данной грамматики новый символ /', в правых частях правил заменить все вхождения начального символа вхождениями /' и добавить к схеме всевозможные правила вида где гр — правая
часть правила, левой частью которого служит начальный символ.
Будем называть Б-грамматику Г стандартной бинарной Б-грамматикой, если каждое правило Г имеет вид А—*ВС или А—*а, где А, В, С — вспомогательные символы и а — основной символ.
Стандартная бинарная Б-грамматика обладает тем свойством, что для всякого ее дерева вывода соответствующая система составляющих (см. § 3.1) бинарна.
Предыдущая << 1 .. 35 36 37 38 39 40 < 41 > 42 43 44 45 46 47 .. 136 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

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

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed