Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
54
ОСНОВНЫЕ ПОНЯТИЯ
[ГЛ. I
Показать, что:
а) понятия н. р. п. м. и н. ч. р. ф. не зависят от выбора стандартной нумерации;
б) понятие н. р. п. м. не изменяется при расширении алфавита (точнее: если L s V* и V s V', то свойство языка L быть н. р. п. м. не зависит от того, относительно которого из алфавитов V и V' определяются н. р. п. м.);
в) язык (функция) тогда и только тогда является н. р. п. м. (н. ч. р. ф.), когда он(а) допускается (вычисляется) некоторой Э-ма-шиной.
1.22. Показать, что:
а) для всякой ДЭ-машины, распознающей язык L, можно построить ДЭ-машину, допускающую язык CL;
б) если имеются ДЭ-машины, допускающие языки L и CL, то по ним можно построить ДЭ-машину, распознающую L.
Замечание. Отсюда и из теоремы Поста следует, — поскольку, как уже было отмечено, ДЭ-машины допускают в точности рекурсивно перечислимые множества, — что существование распознающей язык ДЭ-машины равносильно рекурсивности этого языка.
ГЛАВА 2
СИГНАЛИЗИРУЮЩИЕ ФУНКЦИИ
§ 2.1. Сигнализирующие функции грамматик
Одним из наиболее существенных вопросов, возникающих при изучении порождающих грамматик (как в теоретическом, так и в прикладном аспекте), является вопрос об оценке сложности их работы, т. е. сложности выводов. Для оценки сложности выводов в грамматиках используются так называемые сигнализирующие функции, введением которых мы сейчас и займемся.
Пусть /(Г, D, i) —вычислимая функция, принимающая в качестве значений натуральные числа и определенная на всевозможных тройках (Г, D, i), где Г = = (V, W, I, R) — грамматика (причем мы считаем, что основные и вспомогательные словари всех рассматриваемых грамматик содержатся в некоторых счетных множествах Е и Ei соответственно), D = (мо, coi, ..., соп) — вывод в Г и i = 0, 1, ..., п. Для произвольной цепочки
jteL(r) и произвольного вывода D = (мо, coi......соп)
цепочки х из / в Г положим
f (Г, D, х)= шах /(Г, D, г).
0< i <п
Далее, для любой цепочки ^еЦГ) положим Р(Г, х) = minf (Г, D, х), где минимум берется по всем выводам цепочки х из / в Г. Наконец, положим
F(T, п)= шах ^(Г, х);
(Г), | х |<п
для тех п, для которых не существует таких ^е!(Г), что |*|< п, полагаем Р(Т, п) = 0.
56 СИГНАЛИЗИРУЮЩИЕ ФУНКЦИИ [ГЛ.
Так определенную функцию F(T,n) мы будем на,: зывать квазисигнализирующим операторо ' для грамматик, а функцию Fr(ti), получаемую и F(T, ti) фиксированием переменной Г, — квазисигна лизирующей функцией (или просто к в а з и сигнализирующей) типа F грамматики Г
Таким образом, квазисигнализирующий оператор: F(r, п) сопоставляет каждой грамматике Г числовую функцию Ft {п). Если участвующая в определении оператора функция /(Г, D, г) выбрана так, чтобы она в каком-то смысле характеризовала «сложность» цепочки со,- по отношению к ее «месту» в выводе D, то функцию J (Г, D, х) — наибольшую «/-сложность» входящей в вывод цепочки — естественно считать мерой /-сложности вывода; тогда /‘(Г, х) есть /-сложность самого простого вывода цепочки х, a F{Г, п) —наименьшее число N такое, что все принадлежащие /-(Г) цепочки длины, не превосходящей ti, можно вывести с /-сложностью, не превосходящей N. Таким образом, значение оператора F для конкретной грамматики, т. е. ее квазисигнализирующую типа F, можно считать определенной характеристикой сложности выводов в данной грамматике.
Однако действительно пригодные для произвольных грамматик характеристики сложности выводов доставляются лишь теми квазисигнализирующими операторами, которые удовлетворяют некоторому специальному условию (его значение станет нам ясно из дальнейшего) . Это условие — рекурсивность графика соответствующей функции f (Г, х), т. е. существование алгоритма, позволяющего по любой тройке (Г, х, р), где Г — грамматика, х — цепочка в ее основном словаре и р — натуральное число, узнать, выполняется ли равенство Р(Г, х) = р. Квазисигнализирующий оператор F(I\ /г), удовлетворяющий этому условию, мы будем называть сигнализирующим оператором для грамматик, а соответствующие квазисигнализирующие — с и г-нали-зирующими (функциями) типа F.
Может оказаться, что некоторый квазисигнализирующий оператор, не являющийся сигнализирующим в классе всех грамматик, становится таковым в некотором более частном классе. Точнее: пусть F(T, п) —квазисиг-налнзирующий оператор, ?Г„ -— некоторый класс грамма-
СИГНАЛИЗИРУЮЩИЕ ФУНКЦИИ ГРАММАТИК
67
тик и F3" (Г, п) — функция, индуцируемая оператором F на ЗГ. Если соответствующая функция Рт имеет рекурсивный график, то мы будем называть /^(Г, п) относительным сигнализирующим оператором в классе 0~, а функцию Ft (п), получаемую из FT(Г, и)фиксированием переменной Г, — сигнализирующей (функцией) типа F грамматики Г относительно ЗГ.
Мы будем рассматривать следующие основные типы квазисигнализирующих.
1. Временная сложность (обозначение Гг (п))\ соответствует случаю /( Г, D, i) = i.
2. Емкость Sr(ti): получается при /(Г, D, i) =
= I ю< I •
3. Левая глубина /(Г, D, ^ — увеличен-
ное на единицу расстояние от самого левого вхождения в (Oj вспомогательного символа до правого конца ю*; точнее, если сог = ХгЛг'Пь где х(ёГ и At^Vlt то f(Г, D, г) = | Лг |+ 1; если сог еГ, то /(Г, D, /) = 0.
