Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
же время при 1 ^ i < m имеем |со;| |<0m|- Следова-
тельно, max | щ |<: (g + 1) \х |, откуда 5 г (л) ^ (g+ 1)п.
о < i < п
Остается применить теорему З.Г.
Заметим, что грамматики примеров 10 и 11 из § 1.3 неукорачивающие, а грамматика примера 13 почти неукорачивающая. Поэтому соответствующие языки явля-
СЛОЖНОСТЬ ВЫВОДА
89
ются НС-языками. Дальнейшие примеры см. в упражнениях 3.6 и 3.19.
В заключение параграфа рассмотрим вопрос о свойствах замкнутости класса & (НС).
Теорема 3.4. Класс 3? (НС) эффективно замкнут относительно операций объединения, пересечения, умножения, усеченной итерации и подстановки.
Доказательство. Просмотр доказательства теоремы 1.1 показывает, что если Г', Г", Г — НС-грамма-тики, то соответствующие грамматики, порождающие языки L(T') U Ь(Г' ) и Ь(Г')Ь(Г"), будут также НС-грамматиками, грамматика, порождающая язык /-(Г') П П L(T"), будет почти неукорачивающей, а грамматика Г+, порождающая (L(T))+, удовлетворяет условию Sr*(n) < п -f 2 ^ Зя. Доказательство для подстановки предоставляется читателю (оно также не отличается от доказательства для произвольных грамматик).
Замечания. 1) По поводу операций левого и правого деления см. упражнение 3.9.
2) Вопрос о замкнутости класса 9? (НС) относительно вычитания и взятия дополнения остается открытым.
§ 3.3. Сложность вывода в неукорачивающих грамматиках и НС-грамматиках
Начнем со следующего очевидного, но весьма важного замечания. Поскольку для любой неукорачивающей грамматики Г имеет место Sr(n)^ п, из леммы 2.1 следует, что каждый НС-язык рекурсивен. Сверх того, в силу замечания на стр. 60 существует единый (и достаточно простой) алгоритм, позволяющий по любой неукорачивающей грамматике Г и любой цепочке х в основном словаре этой грамматики распознать, выводима ли х в Г из начального символа *).
Более того, все НС-языки не только рекурсивны, но и примитивно рекурсивны (упражнение 2.16); при этом во всех имеющихся классификациях примитивно рекурсивных языков — или, что то же самое, предикатов — по сложности вычисления (см., например, [Ritchie 1963])
*) Это верно на самом деле и для любой цепочки в полном словаре Г.
90
ГРАММАТИКИ СОСТАВЛЯЮЩИХ
[ГЛ. 3
НС-языки занимают самые нижние ступени иерархии.
Переходя к временной сложности, отметим прежде всего, что для любой грамматики без растяжения Г неравенства (2) и (3) из § 2.1 дают
ьп+1
сп^Т г(п)<|—р,
где с и k — постоянные, зависящие от Г (и эффективно определяемые по Г). О возможности уточнения оценок временной сложности хотя бы для отдельных НС-языков известно немного, а то, что известно, получается довольно громоздкими рассуждениями; этот вопрос будет рассмотрен в следующем параграфе, а сейчас мы займемся сравнением временных сложностей НС-грамматик, неукорачивающих грамматик и грамматик без растяжения.
Теорема 3.5. Для любой грамматики без растяжения Г можно построить неукорачивающую грамматику Г', эквивалентную Г и такую, что
7Y(«)<r-[7Y(n)]2,
где г — постоянная, эффективно определяемая по Г.
Доказательство. Пусть Г = (V, W, I, R) — грамматика без растяжения. Положим Г'= (V, W U {/о, ?}, /о, R'), где /о, Е — новые символы и R' получается из R следующим образом: а) каждое правило ф—*\p^R, где заменяется правилом ф?'|'*>| |<р|->^, если |фj < |гр|, и правилом ф-> ?ф?|ф|_|ф|, если |ф|>|\|}|; б) добавляются новые правила /о -* IqE, /0 —*? /, ?а —? ас, аЕ -> Еа, где а е V U W. Пусть (/ = со0, . • •, со( = х) — полный вывод в Г и | х | = и. Непосредственной индукцией по i легко показать, что для любого i = 0, ..., п в грамматике Г' из цепочки 1Еп~1 выводима цепочка I; При этом имитация применения одного правила ф —* е R состоит в применении соответствующего правила из R' с предварительной «подгонкой» нужного числа символов Е к месту применения правила, если |ф|<|ф|, или последующим сдвигом вновь полученных Е в конец цепочки, если |ф|>|^|; таким образом, на имитацию одного шага в Г тратится не более 1 -f- ng
§ 3.31
СЛОЖНОСТЬ ВЫВОДА
91
шагов в Г', где g = max 11 ф | — | гр 11. В частности, из
Ф-»Ф s= #
IEn~l выводима не более чем за /(1 + ng) шагов цепочка х, а поскольку 1Еп~1 выводима из /о за п шагов и n pt (р — постоянная), цепочка х выводима в Г' из Л> не более чем за п + t{l + ng) t(p + I + ptg) < t*(p + I + pg) шагов. В то же время очевидно, что всякая цепочка в словаре V, выводимая в Г' из /0, выводима в Г из /. Итак, Г' эквивалентна Г, и 7V («) ^ (р + 1 + pg) • [Гг (я)]2.
Замечание. Неизвестно, можно ли в теореме 3.5 заменить квадратичную функцию какой-либо медленнее растущей.
Теорема 3.6. Для любой неукорачивающей грамматики Г и любого положительного действительного числа с можно построить НС-грамматику Г', эквивалентную Г и такую, что
Гг'(п)^тах(1, сГг(п)).
Доказательство. Обратившись к конструкциям, примененным для доказательства леммы 2.4 (о сцеплении) и теорем 2.1 (о сжатии выводов) и 2.2 (об ускорении выводов), мы без труда убедимся, что каждая из этих конструкций, будучи применена к неукорачивающей грамматике, приводит снова к неукорачивающей грамматике. Это дает нам возможность поступить следующим образом. Пусть Г — данная неукорачивающая грамматика и с > 0 — данное действительное число. Фиксируем еще два положительных действительных числа С\ и с2, пока произвольные. Применив конструкцию теоремы об ускорении выводов, построим неукорачивающую грамматику Гь эквивалентную Г и такую, что Гг,(я)^ <|тах(1, С[Гг(п)).Кэтой грамматике применим конструкцию теоремы о сжатии выводов, причем в качестве постоянной с, фигурирующей в формулировке этой теоремы, возьмем число с2. Полученная при этом грамматика Г2 эквивалентна Ti и обладает следующими двумя свойствами: а) Гг,(«XГг,(tt)-f max(c2n, I); б) длины
