5.Основы теории формальных грамматик

5.1.Основные понятия

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

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

-всякая ли фраза может быть переведена с одного языка на другой при заданном наборе правил и заданном объеме машинной памяти;

-как описать множество текстов, доступных для перевода в данных условиях? и.т.д.

Попытки ответить на подобные вопросы сразу же потребовали формализации понятий «словарь», «грамматика», «язык».

Появление трансляторов сделало проблему перевода центральной в построении общей теории вычислительных систем.

Совершенно независимо развивалось направление науки, связанное с построением формальных моделей динамических систем. Типичным примером такого рода является модель «конечный автомат». Охватывая многие процессы, заданные на конечных множествах и развивающиеся в счетном времени, конечные автоматы оказались вместе с тем настолько узкой моделью, что для них удалось создать продуктивную теорию.

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

Независимо и параллельно развивалась общая теория алгоритмов как ветвь современной математики. Была установлена эквивалентность понятий «нормальный алгоритм Маркова», «общерекурсивная функция» и «машина Тьюринга», а тезис Чёрча связал эти три понятия с интуитивным представлением об алгоритме.

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

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

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

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

Эта теория возникла в 50-е годы в работах американского лингвиста

Н. Хомского. По характеру используемого математического аппарата теория формальных грамматик и языков близка к теории алгоритмов и к теории автоматов.

Дадим некоторые определения.

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

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

Словоформа или просто слово – это последовательность (цепочка ) морфем.

Морфема – это мельчайшая грамматически значимая часть слова.

Например, слово «ведший» состоит из морфем вед+ ш+ий (корень, суффикс, окончание).

Словосочетание или предложение – это цепочка словоформ.

Грамматика языка – это конечное множество правил, определяющих этот язык.

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

Синтаксис языка – это правила построения предложений в языке.

Семантика языка – толкование этих правил, правила использования синтаксиса.

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

Первым и основным требованием к грамматике является следующее:

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

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

Вторым требованием к грамматике является ее конечность.

Если допустить грамматики с неопределенным множеством правил, то сама проблема построения грамматик снимется как неразрешимая.

Классификация грамматик может быть представлена в следующем виде:

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

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

Это делает формальные грамматики сравнительно простыми с точки зрения их логического строения и облегчает изучение их свойств Однако формальные грамматики оказываются весьма громоздкими для описания естественных языков и поэтому предназначаются исключительно для теоретического исследования наиболее общих свойств языка.

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

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

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

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

,

где - конечное множество символов, называемых терминальным

или основным словарем G.

- набор исходных элементов, из которых строятся цепочки или словарь основных слов, из которых строятся предложения.

- конечное непустое множество символов, называемых нетерминальным (вспомогательным) словарем G.

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

Элементы и называются соответственно нетерминальными и терминальными символами.

- словарь грамматики G.

Произвольную конечную последовательность элементов будем называть цепочкой в словаре .

Пустая цепочка обозначается , т.о. . Число членов этой цепочки назовём ее длиной и будем обозначать .

Цепочки символов словаря получаются с помощью операции конкатенации
Например, . Символ может опускаться там, где не возникает неоднозначности.

Операция конкатенации ассоциативна, но не коммутативна.
эквивалентно .

S – начальный символ грамматики.

Это выделенный нетерминальный символ, обозначающий класс тех языковых объектов, для описания которых предназначается данная грамматика. Иногда в литературе S называют аксиомой или целью грамматики,

P – правила грамматики или конечное множество цепочек вида j à y, где j и y - слова в словаре V и цепочка j cодержит по крайней мере один символ из словаря Vн .

Конечое двуместное отношение à интерпретируется как “заменить j на y”.

Это отношение несимметрично и нерефлексивно.

Цепочка вида j à y называется правилами грамматики или правилами подстановки, а множество P – схемой грамматики.

Если задана грамматика , то будем говорить:

Цепочка w’ получается непосредственно из цепочки w применением правила j à y, если w=x1jx2 , w'=x1jx2 и {j à y}ÎP.

Последовательность цепочки j=j0, j1, j2 … , jn = y (n³1) ,

где 0 £ i £ n и j - есть вывод цепочки y, если для каждого i ji+1 следует из ji .

Наличие j - вывода цепочки y будем обозначать: j => y.

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

Цепочка y выводится из цепочки j, если она получается из j примененных некоторых правил грамматики G .

Вывод цепочки y считается законченным, если не следует цепочка, которая следует из j.

Цепочка, состоящая только из терминальных символов, называется терминальной цепочкой.

Множество цепочек, выводимых в грамматике G, называется языком, порожденным этой грамматикой, и обозначается L(G).

Язык L(G) называется терминальным, если L-множество терминальных цепочек грамматики G.

Условимся:

-первыми строчными латинскими буквами a, b, c, … обозначать элементы терминального словаря Vт ,

-прописными латинскими буквами A, B, C, … - элементы нетерминального словаря Vн ,

-строчными греческими буквами a, b, … - элементы общего словаря V.

Предложения, составные из этих предложений будем обозначать последними буквами этих алфавитов, т. е. x1 , y1 , … - предложения составляемые из элементов Vт , X, Y, … - предложения, составляемые из элементов Vн , w, j, y , … - предложения составляемые из элементов общего словаря V.

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

Рассмотрим пример:

G=( Vт, Vн,P,S), где Vт={a, b}; Vн={A,B,C}; S=C; P={Càab, CàaCb}.

Пусть w=aCb, w'=aaCbb. Цепочка w' непосредственно выводится из w применением одного правила.

j-вывод: aCb, aaCbb, aaaCbbb, aaaabbbb (терминальная).

Длина вывода = 3.

Из примера видно, что порождающая грамматика не является алгоритмом.

Правила подстановки грамматики – это не последовательность предписаний, а совокупность разрешений.

Это означает следующее:

Правило j à y понимается как “ j может быть заменено на y”, а не “должно быть заменено”;

Порядок применения правил произволен, а в алгоритме был бы задан точный порядок.

Две грамматики G1 и G2 называются слабо эквивалентными, если они порождают один и то же язык L(G1)= L(G2), то есть совпадает множество порождаемых ими фраз.

Две грамматики называются сильно эквивалентными, если они не только порождают одни и те же цепочки, но и приписывают одинаковым цепочкам одинаковые описания структуры.

Основным объектом применения таких формальных грамматик являются не произвольные грамматики, а грамматики некоторых специальных типов.

Выделение этих типов производится по виду правил.

В теории Хомского выделяются четыре типа языков, порожденных четырьмя основными типами грамматик.

Грамматика называется грамматикой типа 0 в тех случаях, когда не накладывается никаких ограничений на правила j à y, где j и y могут быть любыми цепочками из словаря V.

Грамматика называется грамматикой типа 1, если в системе Р правила j à y удовлетворяют условию j = j1Аj2 y = j1wj2,

где А – нетерминальный символ,

j, y, w - цепочки из словаря V.

Таким образом, нетерминальный символ А переходит в непустую цепочку w в контексте j1 и j2 (j1 и j2 могут быть пустыми цепочками).

Грамматики типа 1 называют контекстными.

Грамматика называется грамматикой типа 2 – бесконтекстной, если в системе правил Р допустимы лишь правила вида:

А à w,

где А – нетерминальный символ,

w - непустая цепочка из V.

Грамматика называется грамматикой типа 3, когда допустимы лишь правила вида:

А à w,

где w = аВ либо w = а.

Веденные классы могут быть разбиты на подклассы, но об этом немного позже

Предлагаю ознакомиться с аналогичными статьями: