Формальные свойства грамматик - Хомский Н.
Скачать (прямая ссылка):
Таким образом, бесконтекстный язык однозначно определяется выбором некоторого регулярного языка (т.е. конечного автомата), и каждый такой выбор дает нам некоторый бесконтекстный язык при фиксированных /(, Это позволяет определить простые алгебраические характеристики бесконтекстных языков.
Из теоремы 18 немедленно следует тот результат, что каждый бесконтекстный язык L является гомоморфным образом пересечения К. с некоторым 1-ограниченным языком D. (Напомним, что, как было .показано в разд. 1.2, каждый регулярный язык есть гомоморфный образ некоторого 1-ограниченного языка.) Далее, различные категории бесконтекстных языков, которые были определены выше, легко определяются простыми условиями, налагаемыми на D (подробнее см. в работе [69 ]). Из разд. 1.2 известно, что регулярные языки состоят из цепочек в основном с периодической структурой.
Из той роли, которую играет К в описании бесконтекстных языков, мы видим, что в некотором смысле структурная симметрия составляет фундаментальное формальное свойство цепочек бесконтекстного языка (и подцепочек, из которых они составлены). Можно сказать, правда, довольно расплывчато, что в той мере, в какой характер некоторого аспекта упорядоченного поведения определяется условиями, налагаемыми на соседние части (например, ассоциативные связи), естественно рассматривать организм, имеющий это поведение, в основных чертах как ограниченный автомат; в той -мере, в какой это поведение обладает периодической и ритмической структурой (как в случае примеров, приводимых Лэшли [39] в связи с его критикой теории «ассоциативных цепей»), организм ведет себя подобно строго конечному автомату; в той мере, в какой это поведение проявляет иерархическую организацию и симметрию, организм ведет себя подобно устройству, внутренние свойства которого выражаются бесконтекстной грамматикой.
Естественно, эта слишком краткая (и неточная) классификация не исчерпывает всех возможностей для комплексных, упорядоченных или сгруппированных актов поведения, и можно только надеяться, что по мере того, как будет развиваться теория более богатых порождающих систем (в частности, для языка, теория трансформационных грамматик), будут обнаруживаться и объясняться все более глубокие и далеко идущие формальные свойства такого поведения.
Отметим, что цепочка (27) представляет собой структурное описание входной цепочки tt aacbb w в соответствии с выводом на рис.9.
№
И, Хомский
Точнее говоря, цепочка (27) превращается в структурное описание вида, описанного иа стр. 170, следующим гомоморфным преобразованием: для а ? Vt , /(я) =а и /(я')=е\ для я ? K/v, /(а)= I. н/(я')=1. Это сводится к замене T с командами (25) н (26) преобразователем T', отличающимся от T лишь тем, что он не печатает я' для а ? Vt и печатает ] вместо а'для каждого а ? Vn. Как непосредственное следствие теоремы 17, имеем теорему.
Теорема 19. Если задан бесконтекстный язык L, то можно построить модифицированную нормальную грамматику 0, порождающую L, и преобразователь Т, обладающие следующим свойством; если G порождает х со структурным описанием 9, то T преобразует х в ®; если T преобразует х в 9 и ср сводится к е последовательными сокращениями подцепочек вида Ia а], где a?VT , то G порождает х со структурным описанием ср.
Преобразователь Т, о котором говорит теорема 19, представляет собой, таким образом, «алгоритм распознавания» (т.е. модель восприятия), который приписывает любому предложению его структурное описание относительно G. Однако это не есть строго конечный метод распознавания в силу условия, что выходная цепочка должна сводиться к е. Мы еще вернемся (разд. 4.6) к проблеме построения оптимальной строго конечной процедуры распознавания для бесконтекстных грамматик. В силу результатов, установленных в этом разделе, существует технический прием построения алгоритма распознавания с помощью автомата PDS для каждой нормальной бесконтекстной грамматики, а следовательно, для каждого бесконтекстного языка по крайней мере в одном из его грамматических представлений (а также, как можно предполагать, и во всех).
Итак, мы имеем следующие результаты. Существует фиксированный гомоморфизм /, такой, что для любого регулярного языка R можно найти такой 1-ограниченный язык L, что R=f(L). Существуют фиксированные гомоморфизмы ^1, g2, такие, что для каждой данной бесконтекстной грамматики 0', порождающей язык L(G'), существует модифицированная нормальная грамматика G, порождающая язык L(G)=L(G') н порождающая множество структурных описаний S(G), и существует 1-ограниченный язык L, такой, что L(G)-gI(KftL) и Z(G)=gt(KftL), где К — фиксированный бесконтекстный язык, определенный выше. Таким образом, слабая порождающая способность любой бесконтекстной грамматики и сильная порождающая способность любой модифицированной нормальной грамматики однозначно определяются этим способом путем выбора определенного 1-ограниченного языка.
Мы уже знакомы с различными свойствами трех искусственных языков, введенных в разд. 3 предыдущей главы. Все три языка
