lekcii_dm

А

Б

В

Г

Рис. 2.11

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

3.01.Основные определения формальных грамматик.

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

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

Любой конечный механизм задания языка называется грамматикой.

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

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

101

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

Для задания описания формального языка необходимо:

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

2.Задать формальную грамматику языка, то есть перечислить правила, по которым из символов строятся их последовательности, принадлежащие определяемому языку, – правильные цепочки.

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

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

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

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

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

102

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

Распознающая грамматика языка L – это грамматика, позволяющая установить, правильна ли произвольно выбранная цепочка и, если она правильна, то выяснить ее строение.

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

Формальные грамматики широко применяются в лингвистике и программировании в связи с изучением естественных языков и языков программирования.

Автоматные и лингвистические модели строятся на базе теории формальных грамматик, основы которой были заложены в работах лингвиста Н. Хомского.

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

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

Символы будем обозначать строчными буквами латинского алфавита, а цепочки – в виде «ffghhh», которые будем считать ориентированными слева направо.

Цепочки будем обозначать также специальными символами – прописными буквами латинского алфавита или греческими буквами, например: γ = ffg, В = аbbа.

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

103

Пустая цепочка ε это цепочка, которая не содержит ни одного символа.

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

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

Длина цепочки обозначается следующим образом: |γ| = | ffg | = 3;

|В| = | аbbа| = 4; |ε| = 0.

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

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

Конкатенацией двух цепочек Х и Y называется такая цепочка Z, которая получается непосредственным слиянием цепочки Х, стоящей слева, и цепочки Y, стоящей права.

Например, если X = ffg, Y = ghh, то конкатенация Х и Y – это цепочка Z = ffgghh. Обозначим операцию конкатенации символом о (или “.”).

Свойства операции конкатенации можно записать следующим образом:

1)свойство замкнутости:

о: А* × А* → А*;

2)свойство ассоциативности:

( Х А*, Y A*, Z A*) [(X o Y) o Z = X o (Y o Z)],

104

где через А* обозначено множество всех возможных цепочек (разумеется, бесконечное), составленных из конечного множества А базовых элементов (символов) словаря, включая пустую цепочку ε; символ х обозначает операцию декартова произведения двух множеств; а X, Y, Z – произвольные цепочки, принадлежащие А*.

Рассмотрим пару (А*, 0). С учетом перечисленных свойств операции о эта пара представляет собой полугруппу с единичным элементом ε или моноид.

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

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

Определение группы.

Пусть задано множество элементов G g1, g2, ... , gn , обладающих следующими свойствами:

1.Определен закон умножения элементов gi gj = gk, причем если gi, gj

G, то gi gj = gk G, i, j, l = 1, 2, ..., n.

2.Выполняется закон ассоциативности gi (gj gk) = (gi gj) gk.

3.Существует единичный элемент e, egi = gi, i = 1, 2, ... , n.

4.Существует обратный элемент g i-1, g i-1gi = e, i = 1, 2, ... , n. Тогда на множестве G задана группа элементов g1, g2, ... , gn

Цепочка может принадлежать или не принадлежать языку L.

105

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

Любое множество цепочек L ≤ А* ( где А* – моноид, множество всех возможных цепочек), называется формальным языком, если это множество цепочек определено на алфавите А.

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

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

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

Пусть В и С – некоторые подмножества множества А*. Произведением множеств В и С называется множество D цепочек, являющихся конкатенацией цепочек из В и С, т. е. D = { X o Y | X B, Y C}.

Обозначается произведение следующим образом: D = ВC.

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

Рассмотрим алфавит А.

Обозначим множество, состоящее из ε, через А0.

Определим степень алфавита как Аn = An-1oA для каждого n ≥ 1. Нетрудно показать, что множество всех возможных цепочек алфавита

Такое множество называют итерацией алфавита А.

106

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

Усеченной итерацией алфавита А называют

Если X и Y – цепочки множества А*, то цепочку Х называют подцепочкой цепочки Y, когда существуют такие цепочки U и V из А*, что

Y = UoXoV.

При этом, если U – пустая цепочка, то подцепочку Х называют головой цепочки Y, а если V – пустая цепочка, то Х называют хвостом цепочки Y.

Конкатенация двух цепочек X и Y обозначается ХоY или XY.

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

Рассмотрим пары цепочек (P1, Q1), (P2, Q2), ..., (Pn, Qn) из А* х А*. Соотношениями Туэ (подстановок) будем называть правила, согласно

которым любой цепочке X = U Pi V из множества А* будет ставиться в соответствие цепочка Y = U Qi V, из того же множества А* (i = 1, 2,...,n) и наоборот. Эти соотношения приводят к так называемым ассоциативным исчислениям.

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

Если цепочка Y получается из цепочки Х однократным применением одного соотношения Туэ (т. е. заменой подцепочки Pi на подцепочку Qi), будем говорить, что Х и Y являются смежными цепочками.

107

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

Цепочка Хn соотносима с цепочкой Х0, если существует последовательность цепочек Х0, Х1, ..., Хn , такая, что Х i-1 и Хi являются смежными цепочками.

Пример 2. Пусть А – множество букв русского алфавита, на котором определим соотношение Туэ, заключающееся в праве замены любой одной буквы слова на любую другую. Тогда в последовательности цепочек МУКА, МУЗА, ЛУЗА, ЛОЗА, ПОЗА, ПОРА, ПОРТ, ТОРТ, две любые соседние цепочки являются смежными, а цепочки МУКА и ТОРТ являются соотносимыми в смысле заданных соотношений.

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

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

Соотношения Туэ являются двусторонними, если цепочка Х является смежной по отношению к цепочке Y, и наоборот, цепочка Y является смежной по отношению к цепочке Х.

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

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

Если в соотношении Туэ определено направление, то их называют

полусоотношениями Туэ или продукциями и обозначают следующим образом:

108

(Р1 → Q1), (P2 →Q2), ..., (Pn → Qn).

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

В том случае, когда имеется набор продукций, говорят, что цепочка Y непосредственно порождается из цепочки Х, и обозначается как Х Y, если существуют такие цепочки U и V, что Х =U Pi V, Y = U Qi V, а (Рi → Qi) – продукция из данного набора.

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

Говорят также, что Х порождает Y. Если существует последовательность цепочек Х0, Х1, ..., Хn такая, что для каждого i = 1, 2, ..., n

Х i-1 X i , то говорят, что Хn порождается из Х0 (Х0 порождает Хn), и обозначают как Х0 * Xn. .

Грамматики Хомского соответствуют формальным комбинаторным схемам, являющимся полусистемами Туэ, в основу которых положены полусоотношения Туэ (продукции).

3.03. Определение и способы описания формальных грамматик.

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

109

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

Теория формальных языков позволяет ответить на ряд вопросов, возникающих во многих прикладных задачах, в которых используются автоматно-лингвистические модели. Например, могут ли языки из класса L распознаваться быстро и просто; принадлежит ли данный язык классу L и так далее. Важной проблемой является построение алгоритмов, которые давали бы ответы на определенные вопросы о языках из класса L, например: «Принадлежит цепочка Х языку L или не принадлежит?»

Существуют два основных способа описания отдельных классов языков.

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

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

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

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

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

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

110