Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
Теперь мы «стянем в точку» каждый путь в растянутом дереве Т' — {М'\ вывода D, не имеющий
боковых ответвлений и такой, что все его узлы представляют собой вхождения одного и того же символа*). (Иначе говоря, устраняются все узлы-«копии» и остаются лишь те, которые возникают при применении правил.) Каждый узел А возникающего таким образом дерева представляет собой множество элементов М', являющихся вхождениями одного и того же символа; этот символ мы будем обозначать ё'(Л). Понятно, что если два «старых» узла В и В' оказались «стянутыми» в один «новый» узел, то для любого «старого» узла С
*) Формально эту операцию можно описать как переход к фактор-биграфу по некоторой — строящейся очевидным образом — кон-груэнцщ.
§ з-п*
ДЕРЕВЬЯ ВЫВОДОВ
81
тогда и только тогда В <^С, соответственно С В, когда В' -< С {С В'). Поэтому на множестве М «новых» узлов естественным образом определяется отношение частичного порядка Полученный так объект естественно представлять себе как нагруженный биграф Т = {М\ <<, V[}W, g)\ мы будем называть его де-
ревом вывода/).
Выражения «непосредственный потомок», «потомок» и «предо к» будут использоваться в отношении узлов дерева вывода так же, как это делалось для растянутого дерева.
При графическом изображении дерева вывода удобно для каждой пары узлов А, В помещать А выше В, если А-ь-В, и левее В, если А В.
Полезно заметить, что длина вывода равна числу невисячих узлов его дерева.
Пример. На рис. 3 изображено дерево вывода, соответствующее растянутому дереву рис. 2. (Цифры в скобках нужны для дальнейшего.)
Заметим еще, что отношение индуцирует на множестве висячих узлов дерева вывода линейный порядок, относительно которого это множество изоморфно последней цепочке соответствующего вывода *).
В дальнейшем нам придется рассматривать деревья, сходные с деревьями вывода, в общем виде. Поэтому будет полезно следующее определение.
Назовем расположенным деревом с помеченными узлами (сокращенно Ргдеревом) нагруженный биграф (М; <(, U, g) такой, что:
а) (М; -») — дерево; б) для каждого невисячего узла А
*) Это утверждение имеет следующий точный смысл: если Т = {М; g) — дерево вывода (а>о, .... соп), со„ = pi ... pft
(Pi, ..., Ра — элементарные символы) и Мв — множество висячих уз-лоз Т, то существует взаимно однозначное отображение т множества {1, ..., к] на Мв, переводящее естественный порядок в и такое, что g(T(/)) = pj.
Рис. 3.
82
ГРАММАТИКИ СОСТАВЛЯЮЩИХ
[ГЛ. 3
дерева (М; -*?) отношение индуцирует на кусте А линейный порядок; в) В << С тогда и только тогда, когда найдутся В0 и Со, подчиненные одному узлу и такие, что из них ведут пути (возможно, нулевой длины) в б и С соответственно и при этом В0 -< С0.
Ясно, что есть частичный порядок. Любое дерево вывода является, очевидно, Pi-деревом.
В следующей главе нам понадобится также понятие расположенного дерева с помеченными узлами и дугами (Рг-Д ерева). Так мы будем называть упорядоченную систему (М; U, Z, g, h), где
(М; <<, U, g) — Р[-дерево, Z — конечное множество
и h — отображение множества дуг дерева (М; ->) в Z.
Для каждого Pi-и Рг-дерева Т отношение индуцирует на множестве его висячих вершин линейный порядок. Если Аи ..., Аи — последовательность, составленная из всех висячих узлов Т в соответствии с этим порядком, то цепочка g(.di) ... g(Ah) будет обозначаться ц(Т).
Говоря о пути в Р]- или Рг-дереве, мы всегда будем подразумевать ->-путь.
Пусть Т = (М\ g-) — дерево вывода D в
НС-грамматике Г= (У, W, /, R), оканчивающегося цепочкой и. «Стянув в точки» все пути в Т, не имеющие боковых ответвлений, мы получим новое Pi-дерево Тt = = (Mi; Ui,gi), где: Ui — множество всех подмно-
жеств V U W\ каждый элемент Mi есть множество элементов М, «стянутых в одну точку»; для каждого Л) е Mi множество gi(-^i) имеет вид {g(/4) \'A^Ai). Это Ргдерево, обладающее, очевидно, тем свойством, что всякий его невисячий узел имеет не менее двух подчиненных, мы назовем сжатым деревом вывода D. Если теперь для произвольного узла А^М\ обозначить через c(Ai) множество всех висячих узлов Ti, являющихся потомками Аи и положить С = {с(^41) |Ai е Mi}, то легко видеть, что С есть система составляющих цепочки со (§ П1. 1) и соответствующее дерево составляющих изоморфно дереву (М^ -*?). Более того, если сопоставить каждой составляющей с(Л^ в качестве меток все элементы множества g-i(^41), то получится размеченная система составляющих цепочки со, изоморфная «нагруженному дереву» (М1; gi).
ДЕРЕВЬЯ ВЫВОДОВ
83
Рис. 4.
Пример. На рис. 4 изображено сжатое дерево вывода, отвечающее дереву рис. 3. Оно дает для цепочки abcdba систему составляющих a(b(cd)) (ba).
Таким образом, НС-грамматика позволяет естественным образом сопоставить каждой цепочке порождаемого ею языка некоторую размеченную систему составляющих (вообще говоря, не одну — пример см. в упражнении 3.4), которая оказывается тесно связанной с «историей» цепочки, т. е. ее выводом. Это обстоятельство (объясняющее и сам термин «грамматики составляющих») делает НС-грамматики особенно важными для лингвистических приложений — они позволяют не только порождать «грамматически правильные» цепочки, но и автоматически сопоставлять каждой такой цепочке описание ее синтаксической структуры. Неединственность описания дает возможность учитывать явление синтаксической омонимии (см. § П1.1). НС-грамматика, в которой каждая принадлежащая порождаемому ею языку цепочка имеет единственное дерево вывода, называется однозначной.
