Формальные свойства грамматик - Хомский Н.
Скачать (прямая ссылка):
Основная цель теоретической лингвистики состоит в том, чтобы определить такие общие свойства устройств типов А, В и С, которые окажутся эмпирически адекватными и смогут служить объяснительными теориями для различных частных случаев. Устройства В и С, моделирующие реальное поведение, должны непременно быть строго конечными, HO Л, которое моделирует знания носителя языка, может порождать настолько сложный и «запутанный» комплекс объектов, что никакой строго конечный механизм не смог бы
128
И. Хомский
распознать или воспроизвести все его элементы. Другими словами, мы не можем на основании того факта, что содержащиеся в мозгу правила грамматики конечны, заключить, что множество порождаемых грамматических структур должно иметь тот специальный вид, с которым может иметь дело строго конечный механизм. Действительно, если Л есть грамматика естественного языка L1 то очевидно, что не обязательно существует строго конечный механизм типа В, дающий на выходе правильное структурное описание тогда и только тогда, когда на вход было подано предложение языка L. В этом нет ничего удивительного или парадоксального; это не обязательно следует из бесконечности языка L, но скорее из определенных структурных свойств порождающего механизма А.
С этой точки зрения отдельные довольно вйжные положения лингвистической теории могут, по крайней мере в принципе, считаться входящими в общую теорию (абстрактных) автоматов. Эта достаточно широко разработанная теория (обзор современного состояния см. у Мак-Нотона [45]) пока не обратила на себя должного внимания в литературе по психологии н не очень доступна для большинства психологов. Поэтому мы считаем вполне уместным дать здесь обзор некоторых общеизвестных понятий и результатов (вместе с некоторыми новыми материалами) в качестве основы для более специального исследования механизмов для порождения предложений, приводимого в разд. 2—5.
1.2. Строго конечные автоматы.
Простейшим видом автомата является строго конечный автомат. Мы можем описать его как механизм, состоящий из блока управления, считывающей головки и ленты. Блок управления содержит конечное число частей, которые могут быть установлены конечным числом различных способов. Каждая такая установка называется внутренним состоянием автомата. Лента разделена на клетки; можно считать, что она простирается неограниченно далеко как влево, так и вправо (т.е. что она бесконечна в обе стороны). Считывающая головка в каждый момент времени находится против одной определенной клетки на ленте и может распознавать символы о^,аъ...,аа, составляющие конечный алфавит А (а0 играет роль единичного элемента). Предполагается, что лента может двигаться только в одном направлении, скажем справа налево. Выделяется одно из состояний автомата, которое называется его начальным состоянием и обозначается S0. Состояния автомата обозначаются S0...Sn (я>0).
Можно описать работу автомата следующим образом. Последовательность символовQp j, ..., (? (0<^j^.D) из алфавита Л записана в подряд идущих клетках ленты, по одному символу в каждой клетке. Предполагается, что символ -t-t, не принадлежащий алфа-
Формальные свойства грамматик
129
виту А, занимает все клетки налево от ср, и все клетки направо от а^. Блок управления установлен в состоянии S0. Считывающая головка установлена против клетки, содержащей символ Cp1 . Эта начальная конфигурация машины-ленты показана на рис. 2.
• • • # # * aA Ч # # #
Считывающая голпвка
Еяон управ/гения (в состоянии Se)
Рис. 2. Начальная конфигурация машииы-ленты.
Блок управления работает так, что если он находится в некотором состоянии, а считывающая головка стоит против определенного символа, то он переходит в новое состояние, в то время как лента продвигается на одну клетку влево. Так, на рис. 2 блок управлення переходит в новое состояние S1, в то время когда лента сдвигается так, что считывающая головка оказывается против клетки с символом ср„. Это вторая конфигурация машины-ленты. Машина продолжает работать таким образом до тех пор, пока она не будет блокирована (т.е. пока не появится такая конфигурация, для которой она не имеет дальнейшей команды) или пока она не возвратится в начальное состояние. В последнем случае, если считывающая головка окажется против клетки справа от a$k (в этом случае, впрочем, машина будет блокирована, поскольку в этой клетке стоит символ # (А), мы говорим, что автомат допускает (или, что эквивалентно, порождает) цепочку #ср,...ср4 #. Множество цепочек, допускаемых автоматом, есть язык, допускаемый (порождаемый) этим автоматом.
Итак, поведение автомата описывается конечным множеством троек (і, /, k), 0</, k ^ji, где тройка (i, /, k) интерпре-
тируется как правило, говорящее, что если блок управления находится в состоянии Sj и считывающая головка стоит против символа с;, то блок управления может перейти в состояние Sk. Общая картина поведения автомата может быть представлена с помощью диаграммы, состояний, состоящей из узлов, помеченных обозначениями состояний, и ориентированных путей (стрелок), соединяю-
