Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
Заметим, что если для некоторого сигнализирующего оператора F(Y,x), некоторой вычислимой функции h(n) и некоторого класса грамматик имеет место
F(T,n)^ h(\x\), какова бы ни была грамматика то указанный только что метод доказательства импликации (5) гэ (1) дает единый алгоритм, позволяющий для любой грамматики ref и для любой цепочки х в основном словаре этой грамматики распознать, принадлежит ли х языку Ь(Г).
В дальнейшем нам будут полезны следующие обозначения. Пусть 0~ — некоторый класс грамматик, F — квазисигнализирующий оператор и S — класс числовых
функций. Тогда через 2?g(^-) мы будем обозначать класс языков, порождаемых такими грамматиками класса 3~, у которых квазисигнализирующие типа F мажорируются какими-либо функциями класса Ъ. Если § состоит из одной функции f, будем вместо писать
2?t (&~). Кроме того, вместо S’s (Г) (Г — класс всех грамматик, см стр. 30) мы будем писать
5 2.1]
СИГНАЛИЗИРУЮЩИЕ ФУНКЦИИ .ГРАММАТИК
61
Наконец, /.?(Г), где Г — грамматика, F— квазисигнализирующий оператор и k — натуральное число, будет означать множество цепочек xeL(T), удовлетворяющих условию Р(Г, х) ^ k.
Замечание. Обратившись к конструкции, примененной в доказательстве леммы 1.4, легко увидеть, что для фигурирующих там грамматик Г и Г' имеют место соотношения
Sr(n) = Sr(n), 2V(n)<ftrr(n),
где k — постоянная, зависящая от Г (и допускающая эффективное вычисление). Действительно, если D — полный вывод цепочки х в Г и D' — соответствующий полный вывод х в Г', то максимальные длины цепочек в D и в D' совпадают, а длина самого вывода D' равна сумме длины D и длины х; но длина х не превосходит длины D, умноженной на максимум длин правых частей правил Г.
Нам понадобится также
Лемма 2.2. Для произвольной грамматики Г можно построить эквивалентную ей грамматику Г', удовлетворяющую следующим условиям,-.
а) Г' не имеет правил с пустой левой частью.
б) Для любого полного вывода D в Г, оканчивающегося цепочкой х, можно построить равносильный ему полный вывод D' в Г', отличающийся от D только тем, что на тех местах (кроме последнего, если х = А), на которых в D стоит А, в D' стоит цепочка из одного символа Е, не встречающегося в остальных цепочках D. При этом D' можно разметить так, чтобы при х Ф А правые части всех применяемых правил были непусты, а при х — А правило с пустой правой частью применялось только на последнем шаге. Если D — упорядочиваемый вывод, то D' — также упорядочиваемый вывод. Обратно, любой вывод в Г' можно получить из некоторого вывода в Г указанным способом.
в) Sr(n) — Sr(n); Tr'{n) = Тг(п).
Если АфЬ(Т), то можно сверх сказанного потребовать, чтобы
а') Г' не имела правил с пустой правой частью.
Доказательство. Пусть Г = ( V, W, /, R). Каждому правилу из R вида А -* ?ф, соответственно <р =*? А,
62
СИГНАЛИЗИРУЮЩИЕ ФУНКЦИИ
[ГЛ. 2
сопоставим всевозможные правила а -+ аф и а —? фа, соответственно аф—* а, фа —» а, где а е V и W, а также правило Е-*\[), соответственно ф —*? Е, где Е — символ; не входящий в V U W. Присоединим к W символ Е и к R — все новые правила; одновременно удалим из R все правила вида А—Полученная грамматика Г' удовлетворяет условию а). Выполнение условия б) легко проверяется непосредственно; условие в), равно как и эквивалентность Г и Г', следует из б). Наконец, в силу
а) и б) при А<^1(Г) из схемы Г' можно удалить правила вида ф —? А, что дает а').
§ 2.2. Сигнализирующие функции машин Тьюринга
Пусть f(M,C,i)—вычислимая функция, принимающая в качестве значений натуральные числа и определенная на всевозможных тройках (M,C,i), где М — Э-машина, С — (s0, Si, ..., s„) —вычисление машины
М и i = 0, 1.....п. (Алфавиты и множества состояний
всех рассматриваемых машин считаем содержащимися в некотором множестве Е.) Для произвольной цепочки xeL(M) и произвольного полного х-вычисления С = = (s0, si, s„) машины М положим f(М, С, х) = == шах f(M,C,i). Для любой цепочки x^L(M) по-
О <t<n.
ложим Р(М,х) = min f(M, С, х), где минимум берется по всем полным х-вычислениям машины М. Наконец, положим F(M,n)= max F(M, х); для тех п,
х е L (М); I х I < я
для которых не существует таких xeL(T), что |х|^ п, полагаем F(M, п) = 0.
Так определенную функцию F(M,n) мы будем называть квазисигнализирующим оператором для Э-машин, а функцию FM(n), получаемую из F(M,n) фиксированием М,—квазисигнализирующей (функцией) типа F машины М.
Если М — ДЭ-машина, то можно определить FM(n) непосредственно как max f(M, С, х), поскольку
xeL (М); | X |< п
в этом случае цепочка x^L(M) имеет единственное полное вычисление.
В случае, когда график функции Р(М, х) рекурсивен, мы будем называть соответствующий оператор F(M,n)
§ 2.2] СИГНАЛИЗИРУЮЩИЕ ФУНКЦИИ МАШИН ТЬЮРИНГА 63
сигнализирующим оператором для Э-м а-шин и функцию FM(ti)—сигнализирующей (функцией) типа F машины М.
Нас будут интересовать два типа сигнализирующих функций Э-машин: время работы — обозначение
Тм{п) — и емкость — обозначение SM(n). При определении этих функций в качестве f(M,C,i) берется соответственно число i и длина рабочей ленты в ситуации Si (т. е. число ее ячеек, не считая ячейки, занятой граничным маркером). Тот факт, что соответствующие операторы действительно являются сигнализирующими, устанавливается точно так же, как для грамматик (§ 2.1).
