Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
</(|*n|); (п) F (Гп, х„) f(\xn\) (точнее, тех
из них, которые имеют смысл, т. е. для тех i ^ п, для которых Tj существуют). Если k, ..., in — все те числа из ряда 0.......п, для которых соответствующие
неравенства справедливы, ищем среди них наименьшее — пусть это iP, — для которого грамматика Г1р еще
не опровергнута. Если такое число нашлось, полагаем h(n) = ip, х„ ф Lo. Если такого числа нет, а также если ни одно из неравенств (0), ..., (п), имеющих смысл, не выполняется (в частности, если ни одно не имеет смысла), то полагаем xn е L0, a h(x) оставляем не определенным.
Рекурсивность построенного языка L0 очевидна, и порождающую его грамматику легко построить по алгоритмам, вычисляющим f(n) и график F(T, х). Ясно
УПРАЖНЕНИЯ
75
также, что L0 не может порождаться ни одной из опровергнутых грамматик (поскольку из Р(Т, х) ^/(|*|) следует, во всяком случае, что х е L (Г)). Поэтому для завершения доказательства достаточно установить, что всякая грамматика Г*, для которой найдутся сколь угодно большие числа п, удовлетворяющие неравенству F(Th, рано или поздно опровергается. Но
имеет место даже более сильное утверждение: грамматика Г/j будет опровергнута, если существует k + 1 чисел ти ..., ти+1, не меньших k и таких, что для каждого t' = l, ...,*+1 имеет место F(Tk, |*mi|)<f(|*mt|)
Действительно, пусть Г& обладает указанным свойством и никогда не опровергается. Тогда на каждом из шагов с номерами ть ..., тк+\ должна быть опровергнута некоторая грамматика с номером, меньшим k\ иначе говоря, функция опровержения для каждого из чисел ть ..., m,k+i будет определена и примет значение, меньшее k, а это невозможно из-за разнозначности данной функции.
Упражнения
2.1. а) Найти временную сложность, левую и правую глубину для каждой из грамматик примеров 6—13 из § 1.3.
б) Найти емкость грамматики примера 13 из § 1.3.
в) Найти разброс и активную емкость для каждой из грамматик примеров 7, 8, 10, 11, 13 из § 1.3.
2.2. Показать, что для любой грамматики Г и любой общерекурсивной функции f(m), удовлетворяющей условию Vm[m ^ f(m)], можно построить грамматику Г', эквивалентную Г и такую, что Sr, (я) = f (Sr (га)).
2.3. Пусть х — класс всех грамматик, у которых левые части правил не содержат основных символов. Пусть далее Ш (!Г, О, F, f (п, Fv^ (я), ...,Fr (я)^, где Т — класс грамматик,
О — s-местная операция над языками, F — квазисигнализирующий оператор для грамматик и f(n, ти ..., та)—общерекурсивная функция, означает: «Для любых грамматик Гь . •., Г8 е <Г можно построить грамматику Ге?", порождающую язык 0(L(Ti), L(r,))
и такую, что FT (я) «С f (я, ^г, (я).FT^ (п)у.
Показать, что
а) При F = Т, S, ЩЛ, оцп, / имеет место
Я (Тv U, F, max [Fr> (я), FГа (я))):
76
СИГНАЛИЗИРУЮЩИЕ ФУНКЦИИ
[ГЛ. 2
б) имеет место
$1 {9~], X. Т, max (ГГ[ (fe) + ГГз (п — k))),
О ^ k ^ ti
Ш(ЗГ., X, S, max (Sr (k), Sr (n-k), n),
' 0v 1 12 '
й(^1, X, °УЪ, тах(^т? (rt), <yjb («))) (Ъ = JI, П),
X. A max (?>ri (n), Dv^(n), n)),
X. Л max(/r (я), /Гг(я)) + 1) (X — знак умножения);
в) имеет место
Л> Т, TTi(n) + TT2(n) + n2),
Л. и max(/Г[ (я), ITi(n)) + n), и _при F = S, Ул, <Ци, D-
,, П. Р, max(Fri(«), FVi(я)));
г) при О = +, * имеет место
%(TV О, Т, max (Т г (га,) + ... + Тг (пк))) (п{ > 1),
Гс|4- *• • +м^=м
Щ (rv О, S, max (Sr (n-k) + k)), Ш (Г,, О, Щъ, (я))
О ^ ^ ^ ть
(Ъ = Л, П),
Я(^[, О, А тах(Дг(я), п)+1), О, /, /г (п) + 1).
2.4. Вывести соотношения, аналогичные приведенным в упражнении 2.3:
а) для подстановки;
б) для левого и правого деления на фиксированную цепочку.
2.5. Показать, что для Р = Т, S все соотношения упражнения 2.3 сохраняют силу при замене класса \ классом Г.
2.6. Пусть Т\ означает то же, что в упражнении 2.3, и пусть
1 — функция f(n) = 1 и С —класс всех функций-констант. Показать, что:
а) При F = Vn, °У-п, D
Si (Г,) = [Г, Л НС) = (Б) =
- 2* {Г{) = ZFC («Tj Л НС) = 2*с (Б) *);
б) 2\ (Тх) = 2\ (JT, Л НС) = 2[ (Б) = S’? (iT,);
в) 2'с (1Г,) = Z'c {Г, Л НС) = 2'с (Б).
*) При Р = аЦл, 1Уи это класс Л-языков, при Р = ?> — класс линейных языков (см. ниже, § 5.3 и следствия из теорем 7.2 и 7.3).
УПРАЖНЕНИЯ
77
Заметим, что для любого класса функций имеет место
<?? (гг,) = <?? (г) 2^ (9~| п НС) = 2% (НС), а если $ замкнут относительно умножения на константу, то
аг\ (т,) = 2\ (Г), 2\ {тх л не) = 2\ (не)
(ем. замечание на стр. 61).
2.7. Пусть !7~2 — класс всех грамматик, у которых левая часть каждого правила содержит хоть одно вхождение вспомогательного символа, и 1, С те же, что в упражнении 2.6. Показать, что:
а) при /Г = ^Л,
2* (iT2) = 2f (НС) = 2* (Б) = 2*с (Г2) =
-21 (НС) = 2*с (Б) = (Т,);
б) S’? = 2° (Г2) = (f2)= <?' (!Г2)=2°=*2'; (Г2) = 2(Т).
Заметим, что для любого класса функций % имеет место 21 (Т2) = i?| (Г), а если $ замкнут относительно умножения на константу, то 2l (&~2) ~ (Г) (ср. замечание к упражнению 2.6).
2.8. Показать, что при F — ^/П. D для любой грамматики
Г и любого положительного действительного числа с можно построить грамматику Г', эквивалентную Г и такую, что FГ/ (п) <
