8.2. ПОНЯТИЯ ТЕОРИИ ФОРМАЛЬНЫХ ЯЗЫКОВ

Возникновение теории формальных языков в середине 50-х годов связано с разработкой Ноамом Хомским математических моделей грамматик при исследовании естественных языков. Одной из первоначальных задач лингвистов, работающих в данной области, было создание «вычислительных» грамматик, способных описывать естественные языки, например английский. Была надежда на то, что если замысел удастся, не составит большого труда научить машину «понимать» естественные языки в целях машинного перевода и решения задач. И хотя, по всеобщему мнению, надежды пока не оправдались, побочные результаты этих исследований оказали важное влияние в других областях, например при разработке компиляторов, в языках программирования, теории автоматов и, совсем недавно, в распознавании образов. В этом разделе мы прослеживаем развитие основных идей теории формальных языков в связи с проблемами синтаксического распознавания образов и обучения ЭВМ.

8.2.1. Определения

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

Алфавит — любое конечное множество символов.

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

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

Язык — произвольное множество (не обязательно конечное) предложений в некотором алфавите.

Так же как и в естественных языках, серьезное изучение теории формальных языков должно концентрироваться на грамматиках и их свойствах. Грамматикой мы называем четверку

где

Предполагается, что принадлежит множеству и что — непересекающиеся множества. Алфавит V является объединением алфавитов

Рис. 8.1. Правила подстановки, использованные при порождении предложения и соответствующего семантического дерева.

В данном случае будет полезно сравнить приведенное выше определение формальной грамматики со стандартными понятиями грамматики английского языка. Это поможет читателю лучше понять обозначения и терминологию. Рассмотрим простое предложение The boy runs (мальчик бежит). На рис. 8.1 показана запись этого предложения в виде дерева. Порождение

данного предложения происходит следующим образом. Мы начинаем с абстрактного понятия, которое называем (предложение). На этом этапе (предложение) — не более чем синтаксическое понятие, представляющее все правильные предложения английского языка. Затем мы заменяем (предложение) на (именная составляющая) плюс (глагольная составляющая). В теории формальных языков мы всегда начинаем с описаииого выше символа Правила подстановки грамматики вида (8.2.1) соответствуют в английском языке следующему, например, замещению: (предложение) заменяется на (именная составляющая) и (глагольная составляющая). Как видно из рис. 8.1, в результате дальнейшего применения грамматических правил или правил подстановки (именная составляющая сводится к (артикль) плюс (существительное), а (глагольная составляющая) к (непереходный глагол). Наконец, применение правил подстановки, отображающих (артикль) в «the», (существительное) в «bоу», а (непереходный глагол) в «runs», приводит к искомому предложению. Нетерминальные символы грамматики сответствуют синтаксическим категориям (именная составляющая), (глагольная составляющая), тогда как терминальные символы соответствуют словам естественного языка «the», «bоу», «runs». Другими словами, нетерминальные символы играют роль переменных, терминальные — констант.

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

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

Множество Р правил подстановки состоит из выражений вида , где — цепочка в словаре — цепочка в словаре V. Иначе говоря, символ означает замещение цепочки: цепочкой 13. Символ будет использован для обозначения операций вида в грамматике указывает на замещение в результате применения правила подстановки при этом у и бостаются неизменными. В тех случаях,

когда ясно, о какой грамматике идет речь, опускается и используется символ .

Пример. Рассмотрим грамматику , где . Применяя первое правило раз, получаем

Применение второго правила приводит к цепочке

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