6.28. Лингвистика

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

Типичная задача математической лингвистики состоит в определении принадлежности заданной цепочки 20 к некоторому языку. При решении такой задачи цепочка изображается в виде диаграммы, в ней выделяются грамматические типы, например, существительные, глаголы и группы (рис. 6.64). В общем случае естественные языки нельзя полностью характеризовать только одними грамматиками (Чомский, 1962). Важнейшие задачи состоят в том, чтобы найти:

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

При анализе цепочек естественного языка возникают следующие две задачи.

1. Задача, связанная с наличием абсурдных цепочек, например, «зеленые идеи спят свирепо».

2. Задача, связанная с грамматической неопределенностью, например, pretty little girlscamp.

Рис. 6.64.

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

Определение грамматики [1]

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

1. Произвольные множества односимвольных цепочек.

2. Произведение категорий; С содержит все цепочки где

3. Объединение категорий;

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

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

Пример грамматики.

Пусть типы вершин, соответствующие трем типам категорий. Приведенную выше грамматику можно представить графом (рис. 6.65) [4].

Рис. 6.65.

Рис. 6.66.

Заметим, что поименованными в графе оказываются только вершины типа а и рекурсивно используемая вершина. Используя распределительное свойство и подстановки, имеем

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

1. Переменная.

2. Двоичный оператор, за которым следуют две формулы.

3. Единичный оператор, за которым следует одна формула.

Соответствующий граф показан на рис. 6.66. Граф грамматики называется -графом языка и используется для получения всех цепочек и опознавания любых произвольно заданных цепочек. Цепочки префиксного языка имеют вид;

Заметим, что

1. Г-граф языка конечен.

2. Множество всех цепочек 2 конечно.

3. Множество всех цепочек 2 иеречислимо.

4. Произвольная цепочка может быть представлена деревом. Например, на рис. 6.67 показано дерево, соответствующее цепочке 2б, приведенной выше.

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

Рис. 6.67.

заданной грамматике. Задача определения неоднозначной грамматики или вообще языка (который может иметь много различных грамматик) оказывается более сложной. Действительно, было показано [2], что задача определения однозначности (или неоднозначности) формальной грамматики рассматриваемого типа неразрешима. С другой стороны, если цепочки языка перечислимы, то можно проверить на однозначность достаточно большое их число [4].

Основной задачей математической лингвистики является создание эффективных алгоритмов машинного опознавания цепочек. При этом используется много различных приемов, в частности, указатели ограничений просмотра назад и функции предшествования для каждой категории (например, «не выходить за пределы структуры предложения», «не искать глагольной группы до нахождения группы существительного»). Ряд исследований специальных классов ограниченных грамматик рассмотрен в работе [3].

Полезно найти особые ограничения или обобщения -графов языка. Одно из интересных обобщений связано с заданием некоторых функций длины на дугах графа. В начальный момент длины всех дуг одинаковы. По мере последовательного использования дуг значения их функции длины возрастают. Альтернативные варианты путей выбираются всегда с учетом длины. Таким образом, накапливая «опыт», машина улучшает качество своей работы. Если такую взвешивающую схему встроить, например, в транслятор с ФОРТРАНа, то транслятор сможет в некотором смысле обучиться распознаванию стиля и почерка отдельных программистов.

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

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

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

ЛИТЕРАТУРА к разделу 6.28

Специальные вопросы

(см. скан)