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

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

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

L {М) = S{Lq, &\\> ' • * 9 &рр 1L (Mjj), L (Af12), (Al^p)).
Но по диаграмме можно построить регулярное выражение, представляющее L0 (теорема 5.6). Остается заменить в этом выражении каждый символ на L(Гар).
В частности, если М — машина с ограниченным числом поворотов, то в диаграмме D длины путей ограничены, так что D не имеет циклов, и поэтому соответствующее регулярное выражение является, — точнее, может быть сделано — многочленом (замечание к теореме 5.6). Следовательно, в этом случае L(M) получается из L(rap) с помощью объединения и умножения; но класс металинейных языков, как уже отмечалось, эффективно замкнут относительно этих операций. Тем самым доказана теорема 5.9,6).
Назовем языки, допускаемые чисто стирающими МП-машинами, итерационно-линейными языками. Теорема 5.10 позволяет указать следующий «канонический вид» ОБ-грамматики, порождающей итерационно-линейный язык: Г = (V, W, I, R), где W=WX\J U W2, R = R1 U Rz, причем W{ П W2 — 0; Ri состоит из правил вида А—*ВС, где A, C^Wi, B^W2\ R2 состоит из правил вида Л—»со, где А е W2 и со содержит
*) Ради этого нам и пришлось заменить «двойником». Впрочем, на самом деле «двойник» необходим тол^о при а = |3.
174 СПЕЦИАЛЬНЫЕ КЛАССЫ БЕСКОНТЕКСТНЫХ ЯЗЫКОВ [ГЛ. 5
не более одного вхождения символа из Wi и не содержит вхождений символов из WТакие грамматики можно назвать итерационно-линейными.
Из теоремы 5.10 следует также, что класс итерационно-линейных языков представляет собой замыкание класса линейных языков относительно объединения, пересечения и итерации.
Существуют итерационно-линейные языки, не являющиеся металинейными (упражнение 5.27).
О «допускающих возможностях» детерминированных машин рассмотренных классов см. упражнение 5.33.
§ 5.4. Грамматики с ограниченной активной емкостью выводов. ОАЕВ-языки
Займемся теперь изучением языков, допускаемых МП-мащинами с ограниченным числом поворотов. Мы получим для этих языков, подобно металинейным и итерационно-линейным, две характеристики: в терминах грамматик и в алгебраических терминах.
Пусть Г — грамматика с основным словарем V и вспомогательным словарем W, и (oe(VU®')*. Назовем активной емкостью цепочки число вхождений в нее вспомогательных символов. Активной емкостью вывода в Г будем называть наибольшую активную емкость входящей в этот вывод цепочки*). Если существует число k, мажорирующее активные емкости всех полных выводов в Г, мы будем называть Г грамматикой с ограниченной активной емкостью выводов (ОАЕВ-г р а м м а т и к о й); наименьшее из таких чисел k будет обозначаться /0(Г). Языки, порождаемые ОАЕВ-грамматиками, мы будем называть ОАЕВ-я з ыка м и. Очевидно, для приведенной ОБ-грамматики Г тогда и только тогда /о (Г) = 1, когда Г линейна.
Введем еще одно вспомогательное понятие. Пусть Г — произвольная ОБ-грамматика, Т — дерево вывода в
*) Обе эти величины фактически уже рассматривались нами. Именно, фигурирующая в определении активной емкости грамматики (стр. 57) функция f(F,D,i)—это активная емкость цепочки tot, а ?(Г,D,x)—активная емкость вывода D. (Активная емкость Б-грам-матик изучается ниже, § 7.2.)
§ 5.4] ГРАММАТИКИ С ОГРАНИЧЕННОЙ ЕМКОСТЬЮ ВЫВОДОВ 175
ней и Т — Р\-дерево, полученное из Т выбрасыванием всех узлов, помеченных основными символами. Число висячих узлов дерева Т' будем называть приведенным индексом ветвления дерева Т (не Г'!). Нетрудно видеть, что это число равно наибольшему значению активной емкости вывода, отвечающего дереву Т. (В самом деле, это наибольшее значение достигается на выводе, в котором правила, не содержащие в правых частях вспомогательных символов, применяются в последнюю очередь; а цепочка этого вывода, имеющая наибольшую активную емкость, — точнее, последняя из таких цепочек— должна «проходить» через все висячие узлы Т'.)
Таким образом, ОБ-грамматика Г тогда и только тогда является ОАЕВ-грамматикой, когда множество приведенных индексов ветвления полных выводов в Г имеет конечную наименьшую верхнюю грань; последняя, если она существует, равна /о(Г).
Теперь мы можем доказать следующее утверждение.
Лемма 5.2. Существует алгоритм, позволяющий по любой ОЪ-грамматике Г распознать, является ли она ОАЕВ-грамматикой, и в случае положительного ответа найти /о(Г).
Доказательство. Назовем рангом вспомогательного символа Л ОБ-грамматики Г = (V, W, /, R) наименьшую верхнюю грань множества приведенных ин* дексов ветвления деревьев выводов в Г, начинающихся символом А и заканчивающихся цепочками в V. Кроме того, каждому основному символу припишем ранг 0. Все символы конечного ранга можно найти — и определить их ранги — следующим способом. Определим последовательность W0, W1, ... подмножеств словаря V U W так: W0 = V; если определены Wo, ..., Wn, то Wn+i состоит из тех А ^ W — (Го U... U Wn), которые обладают следующим свойством: какова бы ни была последовательность Aq—Л] >• ?,2-^2^12> *••> As—i ^Е^Л^т^ правил Г такая, что Л0 = Л и А0, AS^W — (W0U ... ... U Wn), все цепочки |4, т], принадлежат V*. (Это свойство, очевидно, эффективно проверяемо.) Непосредственная индукция по п показывает, что для каждого Wn все принадлежащие ему символы имеют конечные ранги; сцособ их нахождения ясен из конструкции. В tq же
Предыдущая << 1 .. 56 57 58 59 60 61 < 62 > 63 64 65 66 67 68 .. 136 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

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

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed