Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
Для НС-грамматик можно определить некоторые специфические характеристики сложности выводов, весьма сходные с рассмотренными в гл. 2 сигнализирующими операторами. Именно, пусть /(Г, С, А) —вычислимая функция, принимающая в качестве значений натуральные числа и определенная на всевозможных тройках (Г,С,Л), где Г = (V,W,I,R)—НС-грамматика (причем мы считаем, что основные и вспомогательные словари всех рассматриваемых грамматик содержатся в некоторых множествах F и Fi соответственно), С — система составляющих, отвечающая некоторому выводу в Г, и АеС. Для произвольной цепочки хеЦГ) и произвольной системы составляющих С, соответствующей какому-нибудь выводу х из / в Г, положим /(Г, С, х) = = шах/(Г, С, А); далее определим F(T,х) и F{T,n)
ЛеС
84
ГРАММАТИКИ СОСТАВЛЯЮЩИХ
[ГЛ. 3
точно так же, как в § 2.1. Функцию F(r, л) мы будем называть НС-си г н а л и з и р у ю щ и м оператором для НС-грамматик, а функцию Fr(rc), получаемую из F(T, п) фиксированием Г, — НС-с и г н а л и з и р у ю ще й (функцией) типа F грамматики Г.
Термин «НС-сигнализирующий оператор» (а не «НС-квазисигнализирующий») оправдывается тем, что график соответствующей функции Р(Г, х) всегда рекурсивен; более того, она сама рекурсивна, так что рекурсивна и функция F(T,n). Это следует из результата упражнения 3.3 и того очевидного факта, что длина бесповторного вывода цепочки х в НС-грамматике не может превосхо-/г,х|+1-1
дить —Y^~\—’ Где —мощность полного словаря грамматики.
Отметим три важных для лингвистических приложений типа НС-сигнализирующих, которые получаются если брать в качестве /(Г, С, А) функции ул{А), уп{А) и ф(А) (§ П1.1). Эти НС-сигнализирующие мы будем обозначать соответственно через У?(я), Y^(n) и Фг(п). Очевидно, Фг (ti) ^ min (Y? (n), Yp(n)). Полезно также обратить внимание на простые соотношения между Ул и °У-Л и между Yn и (упражнение 3.5, а)). ?
Можно определить также Фг (п) и Фг («) (ср. стр. 289).
§ 3.2. Неукорачивающие грамматики и машины Тьюринга без растяжения
Пусть Г = (V, W, I,R)— произвольная грамматика. Назовем правило ф—неукорачивающим, если |<р|^|ф|. Если все правила грамматики Г неукорачивающие, то сама она тоже будет называться неукорачивающей.
В частности, всякая НС-грамматика неукорачивающая.
Полезно заметить, что в силу леммы 2.2 для всякой неукорачивающей грамматики Г может быть построена грамматика Г', не имеющая правил с пустой левой частью (причем простой просмотр доказательства леммы показывает, что Г' может быть также сделана неукорачивающей), эквивалентная Г и даже такая, что каждый
НЕУКОРАЧИВАЮЩИЕ ГРДММАТИКИ
85
полный вывод в Г является одновременно полным выводом в Г' и обратно.
Значение неукорачивающих грамматик определяется прежде всего следующим фактом.
Теорема 3.1. Для всякой неукорачивающей грамматики может быть построена эквивалентная ей НС-грамматика.
Чтобы установить справедливость этой теоремы, мы докажем более сильное утверждение, представляющее интерес и само по себе.
Будем называть грамматику Г, соответственно Э-ма-шину М, грамматикой (машиной) без растяжения, если Sv(n) ^ п, соответственно SM(n) ^ п. Очевидно, всякая неукорачивающая грамматика есть грамматика без растяжения (обратное неверно — см. упражнение 3.8).
Теорема 3.2. а) Для всякой грамматики без растяжения можно построить эквивалентную ей Э-машину без растяжения.
б) Для всякой Э-машины без растяжения можно построить эквивалентную ей НС-грамматику.
Из этой теоремы непосредственно следует теорема 3.1.
Доказательство теоремы 3.2. а) Простой просмотр доказательства пункта б) теоремы 1.4 показывает, что длина рабочей ленты фигурирующей там машины М при имитации вывода в грамматике Г никогда не превышает максимальной длины встречающейся в выводе цепочки. Но если грамматика Г без растяжения, то в выводе цепочки длины п ни одна промежуточная цепочка не может быть длиннее п.
б) Пусть М — Э-машина без растяжения с входным алфавитом V. Построим для нее машину М2, как в доказательстве пункта а) теоремы 1.4. В нашем случае М2 может быть простроена так, чтобы в любом ее вычислении, начинающемся с ситуации (qЛ, # ф, Л, ф *)> ни на одном шаге длина рабочей ленты не была больше |*|. Для этого можно воспользоваться «двухэтажной» рабочей лентой, — иначе говоря, рабочим алфавитом, состоящим из кодов пар вида (а, А), где а — входной символ машины М («символ верхнего этажа») и А — рабочий символ М («символ нижнего этажа»), В «верхнем этаже» машина М2 будет работать, как М на входной
86
ГРАММАТИКИ СОСТАВЛЯЮЩИХ
[ГЛ. 3
ленте, а в «нижнем», как М на рабочей; по окончании имитации работы М (рабочая) лента уничтожается.
Далее построим машину М3, обладающую следующими свойствами: (а) рабочий алфавит М3 получается из рабочего алфавита М2 добавлением одного символа О («пустого символа»); (Р) как и в М2, в М3 при хе Р из ситуации (q', Л, #ф, Л, ф х) тогда и только тогда достижима ситуация (q", Л, Л, ф), когда х^Ь(М);
(у) в любом вычислении машины М3 каждому шагу, на котором выполняется инструкция вида (iii), предшествует шаг, реализующий инструкцию вида (и).
