Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
4. Правая глубина (п): определяется симметрично ^р(п).
5. Разброс DT(n): /(Г, Z), г) есть длина наименьшей подцепочки сог, содержащей все вхождения вспомогательных символов, если таковые имеются; в противном случае / (Г, D, i) — 0.
6. Активная емкость It (п): f(F, D, i) есть
число вхождений вспомогательных символов в со,.
Соответствующие квазисигнализирующие операторы будут обозначаться 7, S, бУ-л, <Vn, D, /*).
Содержательный смысл функций 7г и Sr ясен: первая характеризует сложность вывода числом его шагов, вторая — объемом затрачиваемой «памяти» (носителями «памяти» в выводе естественно считать его промежуточные цепочки). Легко видеть, что операторы 7 и S сигнализирующие. Действительно, пусть заданы грамматика Г, цепочка х и натуральное число р. Чтобы узнать, имеет ли место равенство ? (Г, х) = р, можно поступить следующим образом. Выпишем все полные выводы в Г,
*) Т, S, D, I — от time, space, dispersion, index (индекс — другое название активной емкости, см., например, [Стоцкий 1969]).
58
СИГНАЛИЗИРУЮЩИЕ ФУНКЦИИ
[ГЛ. 1
имеющие длину р. Если ни один из них не оканчивается цепочкой х, то заведомо Т(Г, х) ф р. В противном случае выпишем все полные выводы в Г, длины которых меньше р. Если среди этих выводов найдется хотя бы один, оканчивающийся цепочкой х, то Т (Г, х) Ф р, а если таких выводов нет, то Т (Г, х) = р. Совершенно аналогично проверяется выполнение равенства 5 (Г, х) = = р\ при этом вместо длины вывода (соо, ..., соп) рассматривается число шах | (ot- I и берутся не произволь-
О^ i^.n
ные выводы, а только бесповторные (иначе выводов с данным значением max | a>t | могло бы оказаться бес-
О < г < п
конечно много). Ограничиться бесповторными выводами можно в силу леммы 1.3 и того, что при выбрасывании из вывода каких-либо цепочек число max 1(0,1 не
о< г<л
увеличивается.
Что касается операторов <Я/П, D, /, то ни один из них сигнализирующим не является. Чтобы показать это, рассмотрим произвольно грамматику Г0 = = (V, W, /0, Ro) такую, что V = {|> и 1(Г0) = М0 — нерекурсивное множество целых положительных чисел. Положим
Г, = ({«} U V U Г, {/, Ъ}, /, Ro U {/ -* /0,1 -> Ь, Ь-^аа}),
где /, а, b ф V, U W. Добавим теперь к схеме грамматики Ti правила /—*?/', 1'-*1'АА, Г—+ВВ, ВВ-+аа, аА-*аа, где /', А, В — новые символы, которые будут считаться вспомогательными. Полученная грамматика Гг порождает язык 1(Г0 \]{а2п\п> 1, 2, ...}, но при п е СМ0 имеем (Г2> а2п) = <^п (Г2> а2п) = 0(Г2, а2»)=/(Г2> а2«)= => 2п, а при п е М0 ни одна из этих величин не превосходит п. Поэтому предположение о рекурсивности, например, графика функции 7(Г,х) немедленно приводит к противоречию, так как из него вытекает существование алгоритма, позволяющего для любого п = 1, 2, ... узнать, выполняется ли равенство
7 (Гг, а2п) — 2п, т. е. принадлежит ли число п множеству СМ0.
Впрочем, для некоторых важных классов грамматик индуцируемые операторами <Я/Л, D, I относительные операторы будут сигнализирующими. В частности, это
§ 2.1) СИГНАЛИЗИРУЮЩИЕ ФУНКЦИИ, ГРАММАТИК 59
имеет место для НС-грамматик (см. § 3.3); именно ради применения к НС-грамматикам (в основном даже к Б-грамматикам, см. гл. 7) мы и рассматриваем указанные операторы.
Для произвольной грамматики Г — (V, W, I, R), порождающей бесконечный язык, имеют место неравенства
(О
(2)
(3)
Здесь d = max N't!—-|ф11 и k — мощность множе-ства V[)W.
Неравенства (1) и (2) непосредственно следуют из определений (для получения последнего из неравенств
(2) надо еще воспользоваться тем очевидным фактом, что ни на каком шаге вывода цепочка не может удлиниться более чем на d). (3) вытекает из леммы 1.3, поскольку для бесповторного вывода (м0, • •.. toп) такого, что max \®i\ — l, число п во всяком случае меньше о<г<«
числа различных цепочек в словаре V I) W длины, не
kl+l — 1
большей I, а это число равно —.
Отметим следующее свойство сигнализирующих. Лемма 2.1. Для произвольной грамматики Г следующие утверждения равносильны: (1) язык L (Г) рекурсивен-, (2) любая сигнализирующая грамматики Г вычислима *); (3) любая сигнализирующая грамматики Г мажорируется **) подходящей вычислимой функцией;
(4) хотя бы одна сигнализирующая грамматики Г вычислима', (5) хотя бы одна сигнализирующая граммати-
*) Поскольку сигнализирующая любой грамматики есть всюду определенная функция, вычислимость здесь и далее можно заменить общей рекурсивностью.
**) Мы говорим, что функция g(n) мажорируется функцией h(n), если для каждого п, для которого g(п) определена, h(n) также определена и g(n) ^ А (я).
Sv{n) ^rnax(n, 1); TrW^l;
/г (п) < Dr (п) < (n) < Sr (п) < dTv (п) + 1,
/г {п) < ?>г (п) < Щх (n) < Sr (n) < dTF (л) + I;
Sp (п)+1 (
Гг („)<*-—-L.
60
СИГНАЛИЗИРУЮЩИЕ ФУНКЦИИ
[ГЛ. 2"-
ки Г мажорируется вычислимой функцией. При этом по алгоритму, требуемому каким-либо одним из перечисленных утверждений, можно построить алгоритмы, требуемые остальными.
- Доказательство. Достаточно доказать импликации (1) гэ (2) и (5) гз (1). Пусть язык 1(Г) рекурсивен и Fг (п) —какая-либо сигнализирующая Г. Для произвольной цепочки х в основном словаре Г мы можем узнать, принадлежит ли она L(T), и в случае положительного ответа найти значение г(Г, х), последовательно проверяя равенства Р(Г, х) — 0, Р(Г,х) = 1 и т. д. Таким образом, функция F (Г, х) (с фиксированной Г), а следовательно и F(Y,n), оказывается вычислимой. Пусть теперь некоторая сигнализирующая Ft (п) грамматики Г мажорируется (всюду определенной) вычислимой функцией h(n). Тогда для каждой цепочки д:еЬ(Г) имеет место /?(Г, х) ^A(|x|); в то же время при x^L(T) функция Р(Т, х) не определена. Поэтому х е L (Г) тогда и только тогда, когда выполняется хотя бы одно из равенств Р(Г,х) = 0, ..., F(T,х) — h(\x\), а они поддаются проверке в силу рекурсивности графика F (Г, х).
