2.6. Соединения типа дерева

Обращаясь к соединениям 2 типа дерева, мы встречаемся со случаями, когда арность конфигурации не ограничена. Выходная арность любой образующей равна единице, но входная арность может быть равна произвольному неотрицательному целому числу. Внутренняя структура некоторой конфигурации с с составом может иметь вид, приведенный на рис. 2.6.1.

Рис. 2.6.1.

На множестве образующих введена древовидная топология, при которой выходная связь некоторой образующей (возможно) соединена нереверсивной стрелкой с одной из входных связей другой образующей. Это означает, что всегда равна единице для любой в то время как может быть произвольной и неограниченной.

Комбинацию двух заданных конфигураций можно определить просто с помощью где фиксирует выходную связь или одну из входных связей другой конфигурации.

Классы конгруэнтности в данном случае можно определить так же, как это было сделано в разд. 2.5.

Случай 2.6.1 (речные системы). Рассмотрим в качестве образующих ориентированные отрезки, расположенные на плое

кости; при их записи указываются координаты концов отрезка — Выходная арность, естественно, равна единице, кроме этого вводится условие равенства двум входной арности. Рассмотрим, например, подконфигурацию с одной выходной связью и четырьмя входными, представленную на рис. 2.6.2. Отношение согласования требует, чтобы две входные связи были обязательно равны. в данном случае задавая группой топологических отображений плоскости на себя.

В случае реальной речной системы отрезки заменяются дугами и вводится дополнительное ограничение, состоящее в том, что дуги не должны пересекаться нигде, за исключением концевых точек; входная арность может быть больше двух.

Прежде чем перейти к случаю, в котором бесконтекстные языки рассматриваются как конфигурации с соединениями древовидного типа, напомним вкратце некоторые необходимые понятия. Более подробную информацию о бесконтекстных языках и связанных с ними вопросах читатель может найти в монографии Гинзбурга (1966).

В грамматике непосредственных составляющих основными понятиями являются:

Обозначение А означает совокупность всех конечных цепочек, образованных из элементов любого множества кроме того, вводится обозначение

В лингвистике множества всегда предполагаются конечными, с тем чтобы, как гласит известное изречение, добиться бесконечного конечными средствами. Для нас конечность будет иметь скорее второстепенное значение, однако в данном случае она должна предполагаться.

Остановимся на применении правил. Для двух цепочек а и принадлежащих V, можно записать если существуют цепочки такие, что и отношение принадлежит множеству правил 31. Дальнейшее расширение отношения позволяет утверждать, что если или если существует некоторое и цепочки такие, что и при

Последовательность называется выводом

Цепочками, порождаемыми грамматикой, являются входящие в цепочки, которые выводимы из начального символа. Важным классом грамматик непосредственных составляющих является множество бесконтекстных грамматик. Этот класс предполагает, что все правила, входящие в , имеют вид причем

Рис. 2.6.2.

Пример. Правильно построенные выражения в исчислении высказываний можно получить следующим образом. Пусть заданы терминальные элементы

синтаксическая переменная а и правила

При этом все цепочки, порождаемые грамматикой, будут являться правильными выражениями в исчислении высказываний. Этот пример следует сопоставить со случаем 1.2.4.

Известная теорема (см., например, книгу Гинзбурга (1966), гл. 2) утверждает, что бесконтекстные языки эквивалентны множествам цепочек, допускаемым автоматом с магазинной памятью. Подобный автомат определяется:

Множества предполагаются конечными и непустыми, обозначает пустой вектор. Автомат с магазинной памятью действует следующим образом. Рассмотрим тройку , где состояние автомата, входная цепочка и находится на ленте магазина. Посредством сдвига где осуществляется операция перехода в состояние замена на у и обработка входного символа Эти операции осуществимы, если содержит Входная цепочка допускается автоматом, если, находясь в начальном состоянии и имея на ленте магазина автомат может за конечное число шагов перейти в состояние

Подмножества бесконтекстных грамматик образуют правосторонние линейные грамматики, у которых все правила, входящие в , имеют вид а или где а -Правосторонние линейные грамматики эквивалентны конечным автоматам. Поэтому в данном случае можно употреблять также понятия автоматных грамматик и соответствующих языков. Конечный автомат задается:

Автомат этого типа работает следующим образом. Входная цепочка допускается в том случае, если она является пустым

словом или в множестве К существует последовательность такие, что

Обратим внимание также на следующее хорошо известное соотношение (см. книгу Гинзбурга (1966), гл. 2). Рассмотрим специальный случай отношения конгруэнтности для бесконтекстного языка, когда две цепочки х и у конгруэнтны, если для любых двух цепочек и и либо обе цепочки порождаются данной грамматикой, либо ни одна из них. В таком случае язык относится к конечно-автоматному типу в том и только том случае, если число соответствующих классов эквивалентности конечно.

Случай 2.6.2 (подвыводы в бесконтекстных языках). Обра» зующие соответствуют правилам подстановки, их выходные арности равны единице, а показатель связи — подставляемой синтаксической переменной. Входная арность — число символов в преобразованной цепочке, показатели связей — соответствующие символы, взятые в соответствующем порядке. Тип соединения «древовидная структура», отношение согласования «равенство».

В таком случае есть совокупность подвыводов в данной грамматике. Все регулярные конфигурации будут иметь выходную арность, равную единице, и произвольную входную арность.

Если, кроме того, ввести принимающую образующую с нулевыми входной и выходной арностямн и показателем связи, равным начальному символу, и операторы назначения с единичной входной и нулевой выходной арностями и показателем связи, равным одному из терминальных символов, то регулярные конфигурации с нулевой арностью являются выводами цепочек, порождаемых грамматикой данного языка.

Вернемся к случаю 1.2.2, в котором рассматривается один из вариантов кода Морзе. Может создаться впечатление, что код имеет сугубо линейную структуру, однако более естественно рассматривать его как совокупность объектов с типом соединения «древовидная структура». На самом деле можно считать, что здесь мы имеем бесконтекстную грамматику с синтаксическими переменными , обладающими

терпретацией:

терминальными символами:

и правилами подстановки:

Случай 2.6.3 (линеевские образы). Пусть совокупность функций, заданных на опорном пространстве область значений функции На множестве вводится простое отношение порядка

Образующая задается функцией одной входной связью и произвольным количеством выходных связей Каждая связь представляет собой функцию истинности, причем

при некоторых при

Тип соединения 2 — «древовидный», так что конфигурации имеют древовидную структуру, и эта структура предполагается совместимой с отношением на растущих вверх ветвях.

Отношение согласования для выходной связи присоединенной к входной связи следует интерпретировать как Р влечет Р, т. е. «влечет».

Среди образующих имеется одна, «всякая», входная арность которой равна нулю, а единственная выходная связь

тождественно истинна. Согласно отношению порядка, эта образующая — наибольшая. Имеется еще одна образующая, «инд», представляющая отдельные объекты; эта образующая — наименьшая. Она не имеет выходных связей и располагает одной входной связью. Последняя является функцией истинности некоторого элемента

Рис. 2.6.3. (см. скан)

Пример совокупности образующих размер, цвет, текстура, на которой введено упорядочение рассмотренного типа, приведен на рис. 2.6.3.