Гладкий - Формальные грамматики и языки - 1973 (947381), страница 40
Текст из файла (страница 40)
1. Теорему 6.4 нетрудно было бы усилить, потребовав, чтобы между каждыми двумя «рабочими» шагами читалось не менее я входных символов, где я — произвольное фиксированное натуральное число. 2. Машина, удовлетворяющая требованию теоремы 6.4, является Э-машиной без растяжения (9 3.2). Таким образом, иерархии основных классов грамматик: Г:э НС ~ Б ~ Л отвечает иерархия классов Э-машин: произвольные Э-машины:э Э-машины без растяжения :з МП-машины без растяжения:э конечные автоматы.
Можно было бы включить в эту иерархию также н соответствующие машины для классов языков, рассмотренных в Ц 5.3 и 5.4 (упражнение 6.9). 200 дополнитальиыв свздзния б в-ГРАММАтикАх !гл. з ДОМИНАЦИОННЫВ . ГРАММАТИКИ 201 й 6.3. Доминационные грамматики Для лингвистических приложений полезно иметь возможность задавать язык таким образом, чтобы каждой его цепочке сопоставлялось описание ее синтаксической структуры в виде дерева подчинения, подобно тому, как с помощью НС-грамматики цепочкам сопоставляются описания в виде систем составляющих. Ввиду наличия простой связи между системами составляющих и проективными деревьями подчинения (й П1.3) для этой цели можно использовать те же НС-грамматики, некоторым образом «иерархизуя» их, так, чтобы для каждой системы составляющих, которую «выдает» данная грамматика, автоматически указывалась некоторая иерархизация и тем самым определялось дерево подчинения.
Примером могут служить упоминавшиеся в $ 6.1 прямая и обратная иерархизации категориальных грамматик. Сейчас мы проведем соответствующие построения в общем виде, ограничиваясь, впрочем, случаем Б-грамматик (о распространении на произвольные НС-грамматики см. упражнение 6.18). Будем называть доминацнонной грамматикой (Д-гра м мати кой) упорядоченную пару 6 = = (Г, 1), где Г = (Р', УР', 1, )т) — Б-грамматика без правил вида А — В, А, В ~ Ю', и А — а, А еп %' — (т'), а ~ 'Р' (такие Б-грамматики будут в дальнейшем называться у дл и н я ю щ и м и), и 1 — отображение, сопоставляющее каждому правилу Г = А — Г» ен )т, кроме правил вида т' — а„ а ~ 'Р', некоторое непустое подмножество )'(Г) множества (1, ..., ~ГА~).
Если Г = А - ~раф еп )т, а еп )Г 1.) йг и ~~ра1я1(Г), мы будем называть вхождение Ч~ »а +ф символа сГ в правую часть Г отмеченным. Пусть Т вЂ” дерево полного вывода в Г и С вЂ” соответствующая система составляющих; поскольку грамматика Г удлиняющая, дерево Т, рассматриваемое как дерево без меток, изоморфно системе С.
Пусть далее ив произвольный невисячий узел Т и А-».ГА — правило, применяемое на шаге вывода, отвечающем узлу а. Назовем о т м е ч е н н ы м и те нз подчиненных а узлов, которые соответствуют отмеченным вхождениям символов в в. Будем называть иерархизацию С' системы С до пуст им о й (для 6), если все главные (т.
е. принадлежащие С') составляющие отвечают отмеченным узлам Т. По теореме П!.2 существует единственное связанное с (С, С') (и определяемое по (С, С') эффективно) дерево подчинения 0 для цепочки х = ц(Т); мы скажем, что О сопоставляется цепочке х грамматикой 6. 3 а м е ч а н не. Возможен другой способ определения Д-грамматик, при котором они трактуются как частный случай удлиняющих Б-грамматик. Для этого нужно: а) ввести для каждого символа а ~ 'Р'() (Р' «двойника»вЂ” новый вспомогательный символ а', б) заменить каждое правило Г ~ Т-~- а(а ~ 1Г) системой правил, отличающихся от Г тем, что в правой части каждого нового правила одно вхождение символа отмечается штрихом, а также добавить правила а'- а для всех азу 'Р'()йг. Каждому дереву выводу в такой грамматике отвечает единственная иерархизованная система составляющих: главными составляющими в ней будут те, которые соответствуют узлам, помеченным штрихованиыми символами.
Будем говорить, что Д-грамматики 6, = (Гь 1Г) и О,= (Г»,Ц сильно эквивалентны, если Г, эквивалентна Г» и при этом дерево подчинения тогда и только тогда сопоставляется цепочке грамматикой Оь когда оно сопоставляется той же цепочке грамматикой 6» Скажем, кроме того, что Б-грамматика ГА и Д-грамматика 6 =(Г,1) слабо эквивалентны, если Г, эквивалентна Г, и сильно эквивалентны, если они слабо эквивалентны и при этом: а) для всякой системы составляющих С, отвечающей полному выводу какой-либо цепочки в Г, найдется дерево подчинения, сопоставляемое той же цепочке грамматикой О и согласованное с С; б) для всякого дерева подчинения Т, сопоставляемого какой-либо цепочке грамматикой О, найдется система составляющих, отвечающая некоторому полному выводу той же цепочки в Г«и согласованная с Т.
Будем говорить, наконец, что Б-грамматика Г в клады в а ется в Д-грамматику (Г, 1). Мы рассмотрим теперь один специальный класс Д-грамматик, представляющий особый интерес (в частности, для приложений), . зов дОпОлнительные свеДения О Б-ГРАммАтикАх )гл. а з с.з! домннлционные грамматики гоз Будем называть Д-грамматику п р о с т о й '), если во всех ее правилах отмечены только вхождения основных символов. Если Д-грамматика (Г, !) простая, то во всех строящихся с ее помощью иерархизованных системах составляющих главными составляющими могут быть только точечные. Для случая, когда à — приведенная грамматика, справедливо и обратное. Понятие простой Д-грамматики естественно обобщается следующим образом.
Пусть Г=((У, ))7, Р, )х), ~)— Д-грамматика. Введем на множестве У 0 В' бинарное отношение Я следугощим образом: ссЯ)! означает, что в некотором правиле Г с левой частью а правая часть содержит отмеченное вхождение (). Если граф (У 0 В', Я) не содержит циклов (замкнутых путей ненулевой длины), будем называть 6 Д-г р а м м а т и ко й без ци кл ов. Л е м м а 6.1. Для всякой Д-грамматики без циклов можно построить сильно эквивалентную гй простую Д-грамматику. Дока з а тел ьс т в о. Пусть й — наибольшая длина пути в графе (У 1) !)У; Я) для данной Д-грамматики 6 =(Г,!), где Г =(У, йр,1,)с). Б-грамматнку Г мы можем считать приведенной. (Действительно„если Г'= =(У, ))Г, 1, Л'~ — грамматика, соответствующая Г по лемме 4,8, и ! — функция, которую ) индуцирует на )с', то Д-грамматика (Г', !) сильно эквивалентна 6, а ее граф (У () %"', Я') является подграфом исходного графа (У() НУ;Я).) Поэтому при й = 1 грамматика 6 простая.
Пусть й)'1 и утверждение доказано для всех й' ( й. Назовем рангом вспомогательного символа А наибольшую длинупутив графе (У()К; Я) с началомА. Ясно, что правые части правил Г, имеющих левыми частями символы ранга 1, являются цепочками в У. Заме-' ним теперь каждое правило, содержащее в правой части вхождения символов ранга 1, правилом, получающимся нз данного путем замены всех вхождений.символов ранга 1 в правую часть вхождениями цепочек в У, непосредственно выводимых из этих символов. «) В литературе лля простых д-грамматик часта используется термии «грамматики зазисимостеа» (аигл.
оерепс)епсе Егапипагз). Функцию ! переопределим на новых правилах так, чтобы для каждого такого правила отмеченными вхождениями были, во-первых, те, которые были таковыми в старом правиле и не были заменены при переходе к новому, и, во-вторых, те, которые возникают нз отмеченных вхождений символов в правые части правил вида А- х, хан У+, при подстановке х вместо отмеченного вхождения А в правую часть старого правила. Построенная таким образом новая Д-грамматика будет, очевидно, сильно эквивалентна 6, и в то же время каждый максимальный путь в графе (У 0 )!"; Я) при переходе к новой грамматике укорачнваетси на единицу; остается воспользоваться индуктивным предположением.
Будем далее называть Д-грамматику 6 = (Г, !) Дграмматикой ограниченной ширины, если существует такое число й, что ширина дерева подчинения, сопоставляемого грамматикой 6 цепочке из Е(Г), не может превосходить этого й. Наименьшее из таких чисел будет называться шириной грамматики 6. Л ем м а 6.2, а) Если 6 = (Г, !) — Д-грамматика без циклов, Г =(У, ))У„Т', )1) и наибольшая длина пути в графе (У () МУ; Я) равна й, то 6 есть грамматика ограниченной ширины, и ширина гг нг превосходит й ° (д — 1), гдг д — максимум длин правглх частей правил Г. (В частности, ширина простой Д-грамматики нг превосходит и — 1.) б) Если à — привгдгнная Б-грамматика и 6 = =(Г,!) — Д-грамматика ограниченной ширины, то 6 не имеет циклов.
в) Если в условиях пункта а) грамлгатика Г приведенная, то ширина 6 не меньше й. Доказательство. Назовем путь в дереве полного вывода в Г отмеченным, если все его узлы, кроме, быть может, начального, отмечены. Для дальнейшего заметим, что в произвольном дереве полного вывода нз любого узла идет хотя бы один отмеченный путь в висячий узел, Пусть ссз, ..., а, — отмеченный путь в дереве полного вывода, причем узел а„висячий, н Аз, ..., А„— соответствующая последовательность составляющих. Вспоминая указанный в доказательстве теоремы П1.2 способ построения дерева подчинения, 2ОВ В в.з) ЙомииАциоииыв ГРАмматики Йоб связанного с данной иерархизованной системой составляющих, мы видим, что если прн какой-то иерархизации все составляющие Аь ..., А„окажутся главными, а Ао — не главной, то узлу соответствующего дерева подчинения, являющемуся главной точкой Ам будут подчинены все узлы, являющиеся главными точками не главных составляющих, непосредственно вложенных в Ао, Аь ..
А„ь и только они. Но число таких узлов не меньше и и не больше и (д — 1). Если Π— грамматика без циклов и наибольшая длина пути в графе ()г 0 ))7; Я) есть и, то длина отмеченного пути в дереве вывода не может быть больше й, и, следовательно, никакой узел дерева подчинения не может подчинять более тт.(й — 1) узлов. (Вспомним, что всякая точка цепочки главная для некоторой не главной составляющей.) В то же время из самого определения отношения Я следует, что хотя бы в одном дереве вывода должен быть хотя бы один отмеченный путь длины й, идущий в висячий узел; а если грамматика Г приведенная, то любое дерево вывода можно вложить в дерево полного вывода, так что, по предыдущему, в некотором дереве подчинения, сопоставляемом какой-либо цепочке грамматикой ст, найдется узел, подчиняющий не менее й узлов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
