Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
72
СИГНАЛИЗИРУЮЩИЕ ФУНКЦИИ
[ГЛ. 2
12ф-5?\, то U сложнее L\, поскольку при некотором способе порождения Lx можно обойтись более простыми выводами, чем те, которые понадобятся при любом способе порождения L2.
Для сигнализирующих наиболее важных типов — Г и S — правомерность указанного подхода к определению сложности становится особенно наглядной, если обратить внимание на следующее: при F = Т, f{n) ^ 1 и при F = S, f(n) ^ п из L ф следует, что для любой грамматики Г, порождающей язык L, найдется бесконечно много чисел п, удовлетворяющих неравенству Fг (п) > >f(n)*). Действительно, если, например, существует лишь конечное число таких ri{, i — I, ..., р, для которых Tr(tli) и при этом f (п) 1, то можно, положив
k= max (Гг {tii) — f{ni)) и воспользовавшись след-
ствием из теоремы об ускорении выводов, построить грамматику Гь эквивалентную Г и такую, что Гг, (п) ^ ^ тах(1, Гг(я) — k) (я); аналогично при F = S, f(n)> п.
Возникает вопрос: сколь сложным может быть язык в этом смысле? Иначе говоря, можно ли при заданном F указать такую общерекурсивную функцию /, чтобы все рекурсивно перечислимые языки оказались в классе i?f?
В такой форме этот вопрос немедленно получает отрицательный ответ; действительно, по лемме 2.1 всякий язык, для которого какая-либо сигнализирующая мажорируется вычислимой функцией, рекурсивен, так что никакой нерекурсивный язык не может принадлежать классу S’f ни для какого сигнализирующего оператора F и ни для какой вычислимой функции /. Однако наиболее важны и в теоретическом, и в прикладном аспекте как раз рекурсивные языки, и естественно поставить вопрос для них. Оказывается, что и в этом случае он решается отрицательно: имеет место
Теорема 2.4. Для любого сигнализирующего оператора F{T,ti) и любой общерекурсивной функции f(n) можно построить грамматику Го, порождающую рекурсивный язык и такую, что L (Го) ф 9?Ff.
*) Аналогичный факт имеет место и для /Г = (УЛ, <УП, D, / (упражнение 2.9).
§ 2.4]
СЛОЖНЫЕ РЕКУРСИВНЫЕ ЯЗЫКИ
73
Доказательство. Напомним, что рассматриваются лишь такие грамматики, основные и вспомогательные словари которых содержатся в счетных множествах Е и Ех соответственно (что не уменьшает общности). Пусть ?' = {а1, а3) а5, Ех =
= {«2t а4, а6, ...}. Положим ах — а, а3 = Ь и введем некоторое эффективное кодирование грамматик цепочками в словаре {а, b}. [Можно, например, считать кодом цепочки dicti ... ai( цепочку bal'+l bba2+l b ... bait+xb,
кодом цепочки Л цепочку bab, кодом правила q> -> ip цепочку х (ф) b% (ip), где я (ф), х (гр) — коды ф и ф соответственно, и кодом грамматики (у, W, I, R) цепочку
ba>lb ... balsbabbb%{r{) ... х(ги), где aj, ..., as и г,, ...
• • •» ru — некоторые пересчеты множеств V U W и R соответственно, аг = / и х(о) — код гг.] Грамматику, имеющую код х, обозначим Г*. Пусть L0 — множество всех цепочек х в словаре {а, b}, не удовлетворяющих конъюнкции следующих условий: а) существует грамматика Г*; б) xslfrj; в) F{TX, *)<;/( |х |). Для всякой грамматики Г, порождающей язык L0, найдется число п такое, что F(r, n)>f{ti). В самом деле, если L0 = L(Г), то для некоторой цепочки z будет Г — Г2; при этом ге! (rz) = Ь0, так как из z ф L (Гг) следовало бы по определению языка L0, что z eL0 = i (Г*). Но тогда F(TZ, z) > f( |г I), откуда F{TZ, | 2 |) >/( \г |). В то. же время язык L0 рекурсивен; действительно, д:ei0 тогда и только тогда, когда не выполняется ни одно из равенств ^(Г^, х) = 0....F(Гх, х) = f (| х |), каждое из
которых эффективно проверяемо. Грамматику, порождающую L0, нетрудно построить, зная алгоритмы, вычисляющие функцию / (п), и график функции F (Г, х) (упражнения 2.11, 2.12).
Итак, теорема 2.4 доказана. Но справедливо и более сильное утверждение:
Теорема 2.5. Для любого сигнализирующего оператора F(T,n) и любой общерекурсивной функции f(n) можно построить грамматику, порождающую рекурсивный язык и такую, что для любой эквивалентной ей грамматики Г при всех достаточно больших п имеет место неравенство Fr(n)> f(n).
74
СИГНАЛИЗИРУЮЩИЕ ФУНКЦИИ
[ГЛ. 2
Доказательство. Закодируем грамматики, как в доказательстве теоремы 2.4. Если п — стандартный номер цепочки х в словаре {а, b} (стр. 22), будем писать хп вместо х и Гп вместо Гж.
Искомый язык L0 мы будем строить индуктивно, решая последовательно для каждого п = 0,1, ..., следует ли причислить к L0 цепочку хп? Одновременно будет определяться некоторая вспомогательная частичная числовая функция h(ti)-—«функция опровержения», не принимающая никакого значения более чем один раз.
«Нулевой шаг» построения состоит в следующем. Если существует грамматика Г0 и ^(Г0, хс) ^ /(|*о|) (что эффективно проверяемо), то полагаем Хоф L0 и h(0) = 0. В противном случае (т. е. если грамматики Го не существует или неравенство ^(Го, х0) ^/(|х0|) не имеет места) полагаем Хо е L0, a h(0) остается не определенным.
Пусть произведены шаги с номерами 0, п — 1, в результате которых для каждой из цепочек х0, ..., хп-1 решено, принадлежит ли она языку L0, и для каких-то чисел }\, ..., js из ряда 0, ..., ti— 1 найдены значения функции опровержения, причем все эти значения различны; мы будем говорить в этом случае, что «грамматики Гй^, Г ^ опровергнуты». Тогда п-й шаг состоит в следующем. Проверяем выполнение неравенств: (0) F(T0, хп)^ f(\xn\); (1) Я(Г1, *„) <.
