Введение в формальный анализ естественных языков - Ляпунова А.А.
Скачать (прямая ссылка):
W1 <Z),
то2 < (Z) — Ot1) D — D2 — Ot1O,
Ot3 [(D2 — W1D) — Ot2J D-D3 — W1D2 — W2D,
Wa^Dn — Ot1Z)"-1—W2D'"'1— ... —w„_lD.
Делением последней строки на Dn получаем
/= і
Ho если n^-Ci для всех і, то произошло суммирование по всем закодированным словам, откуда и получаем соотношение по формуле (4). Чем ближе для данного кода неравенство (4) под-.ходит к равенству, тем ближе подходит данный код к минимизации средней длины своих слов. [Неравенство (4) выполняется также для «едревовидных кодов (Mandelbrot, 1954; Mc Millan1 .1956).]
Для всех древовидных кодов, включая, конечно, все натуральные коды, имеется некоторая функция OJj1 определяющая число закодированных слов длины /. Эта функция представляет некоторый теоретический интерес, поскольку она выражает в чрезвычайно простом виде значительную информацию относительно структуры кодового дерева.
Наконец, следует отметить, что код можно рассматривать как простого вида автомат (см. след, главу), который принимает символы в одном алфавите и переводит символы в другой алфавит в соответствии с заранее составленными правилами, которые зависят только от входного сигнала и внутреннего состояния автомата. Некоторых более тонких трудностей, возникающих при построении хороших кодов, можно будет коснуться только после того, как мы припишем различным словам различные вероятности (см. гл. 13).
16»
244
Н. Хомский, Дж. Миллер
3. НЕКОТОРЫЕ ОСНОВНЫЕ понятия лингвистики
Центральным понятием данной работы является понятие языка, Гіоуіому ему необходимо дать ясное определение. Мы считаем, что язык L сечь миожесчио (конечное или йескопеч-ное) предложений, каждое из которых имеет конечную длину и построено с помощью операции соединения из конечного множества элементов. Это определение включает как естественные, таки искусственные языки логики и теории программирования.
Чтобы точно определить язык, необходимо установить некоторые общие принципы, которые отделяют последовательности атомарных элементов, являющиеся предложениями, от последовательностей, таковыми не являющихся. Это различие нельзя выразить просто списком, поскольку во всех представляющих интерес системах не накладывается ограничений на длину предложения. В таком случае определить язык можно двумя способами: можно попытаться разработать какую-либо операционную процедуру, которая будет отличать предложения от ие-предложений, или же можно построить рекурсивные правила, которые будут перечислять все предложения бесконечного списка. Первая из этих возможностей почти не исследовалась1) и останется за пределами нашего обзора. Вторая же составляет один из аспектов того, что естественно назвать грамматикой языка. Мы ограничимся здесь вторым подходом — исследованием грамматик.
При практическом исследовании естественного языка всякая операционная процедура проверки грамматической правильности, а также всякая грамматика должны удовлетворять определенным эмпирическим требованиям. До того как начата разработка анализирующей или порождающей процедуры, необходимо выделить конечный класс Ki последовательностей, которые с достаточной уверенностью могут быть включены в множество предложений, а также, по-видимому, класс Кг последовательностей, которые можно с достаточной уверенностью исключить из этого класса. Эмпирическая значимость той или иной анализирующей или порождающей процедуры в значительной мере определяется тем, сколь успешно они могут выразить различие между классами К\ и Кь Однако вопрос эм-
>) Это утверждение едва ли верно. Алгоритмы синтаксического анализа текста, предназначенные для машинного перевода, как правило, строятся таким образом, что их без труда можно превратить в операционную процедуру для определения грамматической правильности. Ср. также одну иэ работ, в которых возможности построения разрешающих алгоритмов для естественных языков научаются в непосредственном виде: И. Бар-Хнл-лел, Разрешающие процедуры для структуры естественных языков, сб. «Ма* тематическая лингвистика», М., 1964, стр. 108—125. — Прим. перев.
Формальный анализ естественных языков
245-
лирической адекватности и многочисленные соображения, которые с ним связаны, выходят за рамки данного обзора.
Итак, мы займемся теперь изучением грамматик, Под грамматикой понимается набор правил, которые (в частности) рекурсивно перечисляют предложения языка. Всякое правило, которое нам может потребоваться, имеет внд
Ф„ Ф„->ф„+1, (S)
где ф,- есть какая-то структура, а отношение —* интерпретируется как выражающее тот факт, что если наш процесс рекурсивного определения порождает структуры фь .. ., ф„, то он порождает также структуру
Точное определение вида правил, которые могут быть разрешены в грамматике, — это одна из важных проблем математической лингвистики, и именно к ней мы сейчас обратимся. Рассмотрим следующий частный случай правил вида (5). Пусть в правиле (5) п= 1, а фі и фг— цепочки символов некоторого алфавита (или словаря). И пусть имеется конечный язык, состоящий ИЗ предложений CTj, ..., On, H абстрактный ЗЛЄМЄНТ 5 (от слова sentence — «предложение»), который мы выберем в качестве начального, данного. Тогда грамматику можно представить так; '
