Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
176 СПЕЦИАЛЬНЫЕ КЛАССЫ БЕСКОНТЕКСТНЫХ ЯЗЫКОВ [ГЛ. 5
время символы, не вошедшие ни в одно если такие есть, имеют бесконечный ранг. Действительно, если п0 — наибольшее из чисел п, для которых Wn не пусты, то из всякого В е W — (№0U ?. • U №„„) будет выводима некоторая цепочка вида |Ст), где С е W — (W'oU ... U Wnt) и gt) содержит вхождение вспомогательного символа; а поскольку то же самое имеет место для Сит. д., для любого р найдется выводимая из В цепочка, содержащая не менее р вхождений вспомогательных символов, что и обеспечивает бесконечность ранга В. Итак, Г тогда и только тогда будет ОАЕВ-грамматикой, когда ее начальный символ содержится в одном из Wn, и /о (Г) будет равно в этом случае рангу начального символа.
Легко заметить, что понятие приведенного индекса ветвления. позволяет охарактеризовать и МП-машины с ограниченным числом поворотов. Именно, если определить этот индекс для дерева вычисления так же, как для дерева вывода, то он будет равен числу переходов от создания ячеек к их уничтожению, иначе — половине увеличенного на единицу общего числа поворотов. Теперь без труда получается
Теорема 5.11. а) Для любой MYl-машины М с ограниченным числом поворотов можно построить эквивалентную ей ОЪ-ОАЕВ-грамматику Г такую, что /о (Г) = 1/2(П(М) + 1). б) Для любой ОБ-ОАЕВ-грамматики Г можно построить эквивалентную ей МП-машину М с ограниченным числом поворотов такую, что П(М) =2/0(Г) — 1.
Доказательство немедленно следует из лемм 4.12 и 4.13 и того факта, что конструкция, использованная при установлении леммы 4.14, сохраняет приведенные индексы ветвления деревьев.
Замечание. Это же обстоятельство вместе с леммой 5.2 дает алгоритм, позволяющий по любой МП-ма-шине М распознать, имеет ли она ограниченное число поворотов, и в случае положительного ответа найти П(М). ..Перейдем теперь к. алгебраической характеристике ОБ-ОАЕВ-языков. Пусть V* = {ai, ..., а^, b} (k ^ 0) д V7 — произвольные словари, L = V*, L's V , и пусть каждая цепочка языка L содержит не более одного вхождения Ь. Положим Sb(L, //) = 5 (L; а4, ..ak, b\{aj, {аА}, U). ОперациюS,будем называть цент*
§ 5.4] ГРАММАТИКИ С ОГРАНИЧЕННОЙ ЕМКОСТЬЮ ВЫВОДОВ [77
ральной подстановкой L' в L (с центром 6). Выражение, составленное из абстрактных символов |ь . . ., |п с помощью знаков центральной подстановки (с произвольными центрами), будем называть центрально-подстановочным выражением от (переменных) |ь ..., Например, Sc(?i, Sa(l2, Sc(|з, |i))) есть центрально-подстановочное выражение. Можно определить представление языка с помощью центрально-подстановочного выражения так же, как представление с помощью многочлена или регулярного выражения (стр. 24).
Мы покажем, что класс языков, представимых с помощью центрально-подстановочных выражений от линейных языков (иначе говоря, замыкание класса линейных языков относительно центральной подстановки), «эффективно совпадает» с классом ОБ-ОАЕВ-языков. Точнее, имеет место
Теорема 5.12. а) Для любого центрально-подстановочного выражения 21 (|j, ..., ?„) и любых п линейных ОЪ-грамматик Г,........Г„ таких, что выражение
L{rn)) определено*), можно построить ОБ-ОАЕВ-грамматику Г, порождающую язык 2l(L (Г,),... ...,L(rj). б) Для любой ОВ-ОАЕВ-грамматики Г можно построить центрально-подстановочное выражение
21(1;....?„) и линейные грамматики Гь Г„ такие,
что L (Г) = 21 (L (Г,).L (Г„)).
Доказательство, а) Достаточно показать, что если Tj и Г2 — ОБ-ОАЕВ-грамматики и каждая цепочка языка ?(1^) содержит не более одного вхождения символа Ь, то можно построить ОБ-ОАЕВ-грамматику Г*,, порождающую Sb(L (Г[), L (Г2)). Но при Гг = (V, Wt, Ih Rt) (i — 1, 2) и Wx П W2= 0 мы можем, очевидно, положить Tb=(V, W{ U W2,11, Ri lb, I2] U R2), где Rt [b, I2] получается из Rx заменой всех вхождений b вхождениями /2.
б) При /0 (Г) = 1 утверждение тривиально. Пусть оно доказано для случая /0(Г)<й (& > 1), и для данной грамматики Г = <V, W, I, R) имеет место I0(T) = k. Рассмотрим произвольный полный вывод D = (со0, со^)
*) Это значит, что если в данном выражении для каких-либо i, j в L(Ti) подставляется ЦГ^) вместо символа Ь, то каждая цепочке языка ?(Гi) содержит не более одного вхождения Ь,
178 СПЕЦИАЛЬНЫЕ КЛАССЫ БЕСКОНТЕКСТНЫХ ЯЗЫКОВ [ГЛ. 5
в Г и обозначим через iD наибольшее число i, для которого каждая из цепочек со0, ю,, ..со, содержит точно одно вхождение вспомогательного символа. Пусть L' — множество цепочек юг для всех полных выводов в Г, Аи At — все вспомогательные символы, ветре- ’ чающиеся в цепочках языка I/, и Aj-x.оп.......
(/—1, — всевозможные правила Г с левой частью Ah
содержащие в правых частях либо более одного вхо- , ждения вспомогательного символа, либо ни одного. Для произвольных j, I, 1 1^/^Sy, обозначим через ;
ащ, а;-/г все вхождения вспомогательных символов в со л (очевидно, г/г<&) и через Вт, ..., В11г — те
вспомогательные символы, вхождениями которых являются ащ, ajtrjl соответственно.
Положим
Tjlm = (V,W,Bjtm,R> (m = 1, ..., гц). ;
Ясно, что всеГцт являются ОАЕВ-грамматиками и при этом /0(Г цт) < k. Введем новые символы Ьпи ..., bjtr}l и заменим каждое вхождение ацт вхождением символа Ьцт, полученную цепочку обозначим <р/г. (Если не содержит вспомогательных символов, то <р// совпадает С С0/(.) Положим
