Гладкий - Формальные грамматики и языки - 1973 (947381), страница 44
Текст из файла (страница 44)
ленностн для некоторого й, зависящего от Т (см. упражнение 5.7), :то словарь л к язык 0(л) можно выбрать одни и те же для всех . Б-грамматик с данным основным словарем. ГЛАВА 7 СЛОЖНОСТЬ ВЫВОДА В БЕСКОНТЕКСТНЪ|Х ГРАММАТИКАХ Для классификации Б-грамматик по сложности вывода «разрешающая способность» «главных» сигнализирующих операторов — временной сложности и емкости — оказывается недостаточной.
Действительно, для всякой Б-грамматики Г функция Тг(п) мажорнруется линейной функцией (упражнение 4.1,б)) и сверх того для любой Б-грамматики Г можно построить эквивалентную Б-грамматику Г' такую, что Тг (и) < сп, где с в произвольное наперед заданное положительное число (зто тривиальным образом вытекает из теоремы 6.З); но временная сложность грамматики, порождающей бесконечный язык, не может быть по порядку меньше линейной функции (неравенства (1) и (2) на стр. 59).
Что же касается емкости, то она, как мы знаем, не позволяет классифицировать даже неукорачивающие грамматики. Зато квазисигнализирующие операторы «низших» типов — левая и правая глубина, разброс, активная емкость, для которых соответствующие относительные операторы в классе Б-грамматик являются сигнализирующими, — дают в рассматриваемом случае весьма интересную картину.
К ее описанию мы и перейдем. В 7.1. Глубина и разброс Левая глубина. Следующая теорема устанавливает связь между левой глубиной Б-грамматики и степенями левого ветвления отвечающих ей систем составляющих. ГЛУБИНА И РАЗБРОС » 7.п 2»» сложность ВыВОдА В Б-ГРАммАтикАХ !Гл. т Т е о р е м а 7.1 (ср. упражнение 3.5). Для всякой Б- грамматики Г = ()л, !(л,!, Й) флг(п) ~=Унт(п)+1(~9~~(п)+й, где й — максимум длин цепочек х~ )'*, для которых существуют правила вида А- хОВ=Я, причем ОВАЛ. В частности, для стандартной бинарной Б-грамматики су'~(п) =У~(п)+ 1 Имеет место даже более сильное утверждение: аул(Г, х) (Ул(Г, х)+ 1(."ул (Г, х) + й (смысл символов «Гл и т'л ясен из систем обозначений, использовавшихся на стр.
55 и 83). Назовем левой глубиной цепочки хв, где х еп Р» и ГВ ея (у (И) )Г)" ЩЛ), число !ГВ). Левой глубиной вывода будем называть наибольшую нз левых глубин входящих в него цепочек. Легко видеть, что среди всех выводов в Б-грамматике, отвечающих одному и тому же дереву вывода, наименьшую левую глубину имеет упорядочиваемый вывод (всегда существующий и единственный — см. стр.
1!9). Поэтому нужное утверждение непосредственно получается из следующей леммы. Л ем м а 7.1. Пусть (в обозначениях теоремы 7.1) А ~ (Г, х е= Г" и Т есть (А,х)-дерево. Тогда ул,--,л(Т) ! 1 -.ул ! й где у (Т) — степень левого ветвления индуцируемой деревом Т системы составляющих для х и у — левая глул бина соответствующего Т упорядочиваемого вывода. Дока з а тельство.
Если высота Т равна единице, . неравенства очевидны. Пусть они доказаны для всех (В, г)-деревьев высоты, меньшей и (В ~ йГ, г~)л+), высота Т равна и и а«) ... ) а», — все узлы Т, подчиненные корню. Для каждого узла ао помеченного вспомогательным символом, обозначим через ул степень левого ветвления системы составляющих, индуцируемой на соответствующей подцепочке х полным а;-поддеревом Т (само это поддерево обозначим Т,), и через ул — левую глубину отвечающего этому поддереву упорядочиваемого вывода. По индуктивному предположению ул((ул+! ~ ул+ й.
Положим, кроме того, ул=О, если а; помечен основным символом. Имеем, очевидно, ул = гпах(1 + ул), у (Т) = шах(! + ул), причем в первом случае максимум берется по тем 1, для которых и, помечены вспомогательными символами, а во втором — по всем 1=0, ..., й — 1. Обозначим через ул' максимум чисел 1+ул по тем 1, для которых а~ помечены вспомогательными символами, и' через угм — максимум тех же чисел по остальным 1 (если они есть).
Тогда ул ( ул'+ + 1(ул+ 1. С другой стороны, ул'-=. ул(Т)+ й — 1; что же касается числа ул", то оно, очевидно, меньше ул', если узел а», помечен вспомогательным символом, и равно й — 1 в противном случае. Но если ! — наибольшее 1, для которого а, помечен вспомогательным символом, то й — 1 — 1В ( й и 1г ~ (ул — 1, так что (й — 1)+ 1 = й < ул+ й. Этим доказательство заканчивается. Связь между левой глубиной и степенью левого ветвления была впервые замечена В. Ингве [Уппуе !960); именно эта связь была выдвинута им в качестве основного аргумента для обоснования гипотезы об ограниченности степеней левого ветвления в естественных языках (стр.
290). Дело в том, что если моделировать процесс произнесения («порождения») предложения человеком с помощью вывода в Б-грамматике, то для каждой промежуточной цепочки вывода ее отрезок вправо от самого левого вхождения вспомогательного символа (включая это вхождение) естественно интерпретировать как ту информацию, которую говорящий должен на соответствующем шаге процесса держать в памяти. (Такая цнтерпретация будет особенно наглядной, если взять грамматику с правилами вида А - хХ, где х еп Р« и Х ен %" (например, стандартную бинарную 'или в нормальной форме), и построить для нее эквивалентную МП-машину способом, использованным в доказательстве теоремы 6А.
Тогда каждая промежуточная цепочка упорядочиваемого вывода будет иметь вид гЯ, где ген ~ )л" и Х еп 11«', а при переходе к МП-машине цепочка (точнее, Я) станет содержимым рабочей ленты, т, е, «ленты памяти», на соответствующем шаге вычисления.) Но объем «оперативной памяти» человека ограничен сверху, причем граница, по данным экспериментальной психологии, сравнительно невысока. То ГЛУБИНА И РАЗБРОС з 7.Ц 8 А. и. саадака 224 сложность выводА в в гркммдтикдх 1гл. 7, обстоятельство, что гипотеза в целом не подтверждается:: (стр. 290), заставляет сделать вывод, что с помощью Б-грамматик — во всяком случае, без дополнительных ', механизмов — нельзя достаточно удовлетворительно мо-, делировать процесс порождения предложения носителем языка *).
Тем не менее Б-грамматики, левые глубины которых ограничены константами, представляют значительный лингвистический интерес, хотя бы потому, что ограниченность степеней левого ветвления является существен- . ной типологической характеристикой языка. Возникает ' вопрос о природе языков, порождаемых такими грамма- ' тиками, а также множеств цепочек, выводимых в про- ' извольных Б-грамматиках с помощью выводов ограниченной левой глубины. Ответ на эти вопросы дает сле-а дующая Теорема 7.2. Для любой Б-грамматики Г и лю- З7Л бого натурального числа й множество Е» является А-языком.
Более того, для всякой Б-грамматики Г и всякого натурального й можно построить А-грамматику,, „л порождающую Еь (Г). Доказательство. Пусть Г = ()7, Ф',1,)ч). Сопоставим каждой цепочке ьз ен(И) йу)+, 1аз) ( й, новый символ сс(ьз) и каждой тройке (ф,фх), где фен(И))Р)а, ф я()7()%')',хан 17', 1ф), 1ф) < й и ф~хф, новое пра-; г вило а(ф)- ха(ф), если ф чь Л, и сс(ф)- х, если ф = Л. Положим Г' = (17, Ю',а(1),В'), где 1Р" состоит из всех . новых символов и )с" — из всех новых правил. Грамматика Г' правосторонняя линейная, и для нее без труда; строится эквивалентная ей автоматная (ср.
стр. 169).: В то же время легко видеть, что Е (Г') = Е(Г). Следствие. Для любой Б-грамматики Г, для которой йулг(п) ограничена числом й, можно, если известно й, построить эквивалентную ей А-грамматику. ") Это утверждение ни н коей мере не означает отрицании лингинсгической значимости Б-грамматик. Грамматики, неадекватные для моделирования прпцесса порождения предложения челонеком, могут ' быть а то же время пригодны для описания структуры законченнога предложения, подобно тому, нак с помощью языка математической логики можно представить готовое доказательство теоремы, нп не, процссс его нахождения математиком. Заметим, что если à — приведенная грамматика, то чз7лг(п)=1 тогда и только тогда, когда à — А-грамматика.
Таким образом, если С вЂ” класс всех функций- констант, то .У~яд (Б) = 'с (А). В общем случае для Б-грамматики Г имеем, очевидно, агу7л,(п)- и, и существуют Б-грамматики, для которых это неравенство переходит в равенство, — примером может служить хотя бы грамматика Г = ((а), (1), 1, (1- 1а,1- а)); впрочем, язык Е(Г) = а' может быть порожден и А-грамматикой, т. е.
грамматикой левой глубины !. Естественно спросить, существуют ли Б-языки, не порождаемые никакими Б-грамматиками левой глубины, меньшей и. Ответ на этот вопрос отрицателен; более того, для любой Б-грамматики Г и любого действнтсльного числа с, 0(с 1, можно построить Б. грамматику Г', эквивалентную Г и такую, что для всех достаточно больших и имеет место неравенство флг, (и) -= сп (так что для любой линейной функции 1(п) = сп, с ) О, имеем 2'гв~ (Б) = 2'(Б).
(А 1ог(1ог1 это утверждение верно также для разброса и активной емкости.) Действительно, нужным свойством будет обладать всякая грамматика, удовлетворяющая требованию теоремы 6.3, если только взять фигурирующее в условии этой теоремы число з достаточно большим (на- 11 пример, положить з) — 1. с1' В то же время существуют Б-языки (и даже линей ные языки), удовлетворяющие тому условию, что для каждой порождающей такой язык Б-грамматики ее левая глубина мажорирует некоторую линейную функцию.
Приведем пример. П р и м е р 1, Рассмотрим язык Е = (ааЬ" ~ и = 1, 2,...) и произвольную порождающую его Б-грамматику Г = ((а, Ь), 177, 1,В). Мы можем считать, что à — приведенная грамматика без правил вида А- В, А, В ~ Я7; действительно, при переходе от произвольной Б-грамматики к приведенной (лемма 4.8) множество полных выводов не меняется, а переход к грамматике без правил вида А — В можно, как показывает очевидный анализ доказательства леммы 4.1, осуществить так, чтобы 226 сложность вывод» а Б гР»мм»тик»х !гл. т ГЛУБИНА И РАЗБРОС 22Т $ тз! между множествами полных выводов в старой и новой грамматиках существовало взаимно однозначное соответствие со следующим свойством; для каждой цепочки ьт из полного вывода в старой грамматике найдется цепочка ьт' из соответствующего вывода в новой такая, что [ьт'[ = [ьт[ и на всех местах, на которых в ьт стоят основные (соответственно вспомогательные) символы,в ьт' также стоят основные (вспомогательные) символы, и обратно.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
