Гладкий - Формальные грамматики и языки - 1973 (947381), страница 16
Текст из файла (страница 16)
5 1.1, стр. 20). Кроме того, договоримся для каждого ! располагать цепочку юсн! (т.е. соответствующую прямую) ниже цепочки юь При таком способе изображения можно, не опасаясь д недоразумений, заменить обозначения В! символами би. Если в (М;-») из а в идет путь ненулевой длины, мы будем называть й потомком аи а — предком р.
П р и м е р. Пусть схема НС-грамматики Г содержит правила А - аВЛ, ВЛ » ВВЛ, ВВ — »ВРВ,  — »Ь, ЬРВ-» Ьсг(В, ЬА — » Ьа. Тогда размеченному выводу (еА*, а»ВА«, ОВ*ВА*, а*ВВВ*А, а В*РВА, и>ЬРВ»Л„аЬсс1«В«А, аЬсг(«ЬА«, абсс(Ьа) будет отвечать (в данном случае единственное) растянутое дерево вывода, изображенное на рис. 2. Рно. 2. Теперьмы «стянем в точку» каждый путь в растянутом дереве Т' = (М'! -», () вывода Р, не имеющий боковых ответвлений и такой, что все его узлы представляют собой вхождения одного и того же символа "). (Иначе говоря, устраняются все узлы-«копии» и остаются лишь те, которые возникают при применении правил.) Каждый узел А возникающего таким образом дерева представляет собой множество элементов М', являющихся вхождениями одного и того же символа; этот символ мы будем обозначать д(Л).
Понятно, что если два «старых» узла В и В' оказались «стянутыми» в один «новый» узел, то для любого «старого» узла С *) Формально зту операцию можно апнсать как переход к фактор-бнграфу по некоторой — строящейся очевидным образом — кон. груанцня. тогда и только тогда В ( С, соответственно С «, В, ког- да В'(С(С(В'). Поэтому на множестве М «новых» узлов естественным образом определяется отношение частичного порядка (. Полученный так объект естест- венно представлять себе как нагруженный биграф Т=(М; -», (, УЦ((г", д); мы будем называть его де- ревом вывода Р. Выражения «н е п о с р е д с т в е н н ы й п о т о м о к», «п о т о м о к» и «п р едок> будут использоваться в отно- шении узлов дерева вывода так же, как это делалось А (!) для растянутого дерева. При графическом изображении дерева вывода В(г) д(В) удобно для каждой пары узлов А, В помещать А ВКВ В(5) ВЯ А(7) выше В, если Л-»В, н левее В, если А ч', В.
Полезно заметить, что а длина вывода равна числу невнсячих узлов его дерева, Пример. На рис. 3 изображено дерево вывода, соответствующее растянутому дереву рис. 2. (Цифры в скобках нужны для дальнейшего.) Заметим еще, что отношение ( индуцирует на мно- жестве висячих узлов дерева вывода линейный порядок, относительно которого это множество изоморфно послед- ней цепочке соответствующего вывода *). В дальнейшем нам придется рассматривать деревья, сходные с деревьями вывода, в общем виде. Поэтому будет полезно следующее определение. Назовем расположенным деревом с поме- ченными узлами (сокращенно Рыдеревом) на- груженный биграф (М; -ч, (, У, д) такой, что: а) (М; -+) — дерево; б) для каждого невисячего узла А с Ы Рнс. 3. *) Это утверждение имеет следующнй точный смысл: если Т = (М; -», (, В) — дерево вывода (ые ..., ы ), ы„= (31 ...
13а (рь ..., рз — злементарные снмвалы) в М' — множества висячих узлов Т, то существует взанмно однозначное отображение т множества (!..., А) на М', переводящее естественный порядок в ( и такое, что В(т(!)) = (]о ДЕРЕВЬЯ ВЫВОДОВ 4 хлн ГРАММАТИКИ СОСТАВЛЯЮШИХ 82 [ГЛ. 3 83 дерева (М; -») отношение( индуцирует иа кусте А линейный порядок; в) В ( С тогда и только тогда, когда найдутся Вс и Со, подчиненные одному узлу и такие, что из них ведут пути (возможно, нулевой длины) в В и С соответственно и при этом Вс( Сс.
Ясно, что «' ,есть частичный порядок. Любое дерево вывода является, очевидно, Ридеревом. В следующей главе нам понадобится также понятие расположенного дерева с помеченными узлами и дугами (Р,-дерева). Такмы будем называть упорядоченную систему (М; -», (, У, Л, д, 6), где (М; -», („У, д) — Р,-дерево, 2 — конечное множество н Ь вЂ” отображение множества луг дерева (М; -ь) в 2. Для каждого Рии Рюдерева Т отношение ( индуцирует на множестве его висячих вершин линейный порядок. Если Аь ..., АА — последовательность, составленная из всех висячих узлов Т в соответствии с этим порядком, то цепочка д(А1) ...
д(АА) будет обозначаться ц(Т). Говоря о пути в Ри или Рюдереве, мы всегда будем подразумевать -ь-путь. Пусть Т = (М; », «„д) — дерево вывода В в НС-грамматике Г = (У, 1«', 1, 14), оканчивающегося цепочкой а, «Стянув вточки» все пути в Т, не имеющие боковых ответвлений, мы получим новое Ргдерево Т, = = (Ми-», (, Уьд~), где: У1 — множество всех подмножеств 1~ 0 1«; каждый элементМ, естьмножествоэлементов М, «стянутых в одну точку»; для каждого А, ен М~ множество а1(Л1) имеет вид (д(А) (А~Л1). Это Р,-дерево, обладающее, очевидно, тем свойством, что всякий его не- висячий узел имеет не менеедвух подчиненных, мы назовем сжатым де р е в о м вы вода й.
Если теперь для произвольного узла А,~М1 обозначить через с(А1) множество всех висячих узлов Т» являющихся потомками Аь и положить С = (с(А1) ~Л, ~ М1), то легко видеть, что С есть система составляющих цепочки сс (5 П1. 1) и соответствующее дерево составляющих изоморфно дереву (М,; -«). Более того, если сопоставить каждой составляющей с(А|) в качестве меток все элементы множества д~(А~), то получится размеченная система составляющих цепочки са, изоморфная «нагруженному дереву» (М,;-,,). П р и м е р.
На рис. 4 изображено сжатое дерево вывода, отвечающее дереву рис. 3. Оно дает для цепочки аЬст(Ьа систему составляющих а(Ь(сс() ) (Ьа). Таким образом, НС-грамматика позволяет естественным образом сопоставить каждой цепочке порождаемого ею языка некоторую размеченную систему составляющих (вообще говоря, не одну — пример см. в упражнении 3.4), которая оказывается тес- но связанной с «историей» цепочки, т. е. ее выводом. Это обстоятельство (объясняющее и сам термин «грамматики составляющих») делает НС- грамматики особенно важными а для лингвистических прило- ,а) жений — они позволяют не только порождать «грамматн- с чески правильные» цепочки, но и автоматически сопоставлять Рис.
4. каждой такой цепочке описание ее синтаксической структуры. Неединственность описания дает возможность учитывать явление синтаксической омонимии (см. $ П1.1), НС-грамматика, в которой каждля принадлежащая порождаемому ею языку цепочка имеет единственное дерево вывода, называется однозначной. Для НС-грамматик можно определить некоторые специфические характеристики сложности выводов, весьма сходные с рассмотренными в гл.
2 сигнализирующими операторами. Именно, пусть 1(Г, С, Л) — вычислимая функция, принимающая в качестве значений натуральные числа и определенная на всевозможных тройках (Г, С,А), где Г = (1', У,1,В) — НС-грамматика (причем мы считаем, что основные и вспомогательные словари всех рассматриваемых грамматик содержатся в некоторых множествах Т и Р1 соответственно), С вЂ” система составляющих, отвечающая некоторому выводу в Г, и А еи С.
Для произвольной цепочки х ~ Т. (Г) и произвольной системы составляющих С, соответствующей какому- нибудь выводу х из ! в Г, положим 1(Г, С, х) = = шахГ'(Г, С, А); далее определим г"(Г,х) и Р(Г,п) А~С ИВУКОРАЧИВАЮШИВ ГРАММАТИКИ 2 Зл! ГРАммАтики состАВляющих !ГЛ. 2 точно так же, как в $2.!. Функцию Р(Г, и) мы будем называть НС-сигнализирующим оператором для НС-грамматик, а функцию Рг (и), получаемую из Р(Г,п) фиксированием Г,— НС-сигналнзирующей (функцней) типа Р грамматики Г.
Термин «НС-сигнализирующий оператор» (а не «НС- квазисигнализирующий») оправдывается тем, что график соответствующей функции Р(Г, х) всегда рекурсивен; более того, она сама рекурсивна, так что рекурсивна и функция Р(Г,п). Это следует из результата упражнения З.З и того очевидного факта, что длина бесповторного вывода цепочки х в НС-грамматике не может превосхо- А!2|+1 дить А †! где й — мощность полного словаря грамматики. Отметим трн важных для лингвистических приложений типа НС-сигнализнрующих, которые получаются если брать в качестве 1(Г, С, А) функции ул(А), у" (А) и ф(А) (9 П!.1).
Эти НС-сигнализирующие мы будем обозначать соответственно через У~(п), 7„"(и) и ФГ(п). Очевидно, Ф. (и) » (пнп (У~~(п), У~~(п)). Полезно также обратить внимание на простые соотношения между У л и ф~ и между т'" и 2!Г'" (упражнение 3.5, а)). Можно определить также Фг (и) и Фг (п) (ср. стр. 289). 9 3.2.
Неукорачивающие грамматики и машины Тьюринга без растяжения Пусть Г = ($', (Р', 2',Г!) — произвольная грамматика. Назовем правило 2р- фенй неукорачивающим, если )~р(» !ф). Если все правила грамматики Г неукорачивающие, то сама она тоже будет называться неукор а ч и в а ю щ е й. В частности, всякая НС-грамматика неукорачивающая. Полезно заметить, что в силу леммы 2.2 для всякой неукорачивающей грамматики Г может быть построена грамматика Г', не имеющая правил с пустой левой частью (причем простой просмотр доказательства леммы показывает, что Г' может быть также сделана неукорачнвающей), эквивалентная Г и даже такая, что каждый полный вывод в Г является одновременно полным выводом в Г' н обратно. Значение неукорачивающих грамматик определяется прежде всего следующим фактом.
Т е о р е м а 3.1. Для всякой неукорачиваюи(ей грамматики может быть построена эквивалентная ей НС-грамматика. Чтобы установить справедливость этой теоремы, мы докажем более сильное утверждение, представляющее интерес и само по себе. Будем называть грамматику Г, соответственно Э-машину М, грамматикой (машиной) без растяж е н и Я, если Зг(п)» и, соответственно Ом(п)» п. Очевидно, всякая неукорачивающая грамматика есть грамматика без растяжения (обратное неверно — см. упражнение 3.8). Теорема 3.2. а) Для всякой грамматики беэ растяжения можно построить эквивалентную ей Э-машину беэ растяжения. б) Для всякой Э-машины беэ растяжения можно построить эквивалентную ей НС-грамматику. Из этой теоремы непосредственно следует теорема 3.1. Доказательство теорем ы 32.
а) Простой просмотр доказательства пункта б) теоремы !.4 показывает, что длина рабочей ленты фигурирующей там машины М при имитации вывода в грамматике Г никогда не превышает максимальной длины встречающейся в выводе цепочки, Но если грамматика Г без растяжения, то в выводе цепочки длины и ни одна промежуточная цепочка не может быть длиннее и, б) Пусть М вЂ” Э-машина без растяжения с входным алфавитом !т. Построим для нее машину Мь как в доказательстве пункта а) теоремы 1.4. В нашем случае М, может быть простроена так, чтобы в любом ее вычислении, начинающемся с ситуации (д', Л, ~фф, Л, 4Рх), ни на одном шаге длина рабочей ленты не была больше !х), Для этого можно воспользоваться «двухэтажной» рабочей лентой, — иначе говоря, рабочим алфавитом, состоящим из кодов пар вида (а, А), где а — входной символ машины М («символ верхнего этажа») и А — рабочий символ М («символ нижнего этажа»).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
