Лекции по дискретке (1021001), страница 10

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

Текст из файла (страница 10)

|γ| = | ffg | = 3;

|В| = | аbbа| = 4;

|ε| = 0.

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

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

Конкатенацией двух цепочек Х и 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)],

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

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

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

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

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

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

1. Определен закон умножения элементов gi gj = gk, причем если g_i, g_j ∈G, то g_i g_j = g_k ∈G, i, j, l = 1, 2, ..., n.

2. Выполняется закон ассоциативности g_i (g_j g_k) = (g_i g_j) g_k.

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

4. Существует обратный элемент g _i^-1, g _i^-1g_i = e, i = 1, 2, ... , n.

Тогда на множестве G задана группа элементов g₁, g₂, ... , g_n

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

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

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

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

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

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

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

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

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

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

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

Определим степень алфавита как А_n = A_n-1oA для каждого n ≥ 1.

Нетрудно показать, что множество всех возможных цепочек алфавита

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

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

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

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

Y = UoXoV.

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

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

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

Рассмотрим пары цепочек (P₁, Q₁), (P₂, Q₂), ..., (P_n, Q_n) из А* х А*.

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

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

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

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

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

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

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

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

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

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

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

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

(Р₁ → Q₁), (P₂ →Q₂), ..., (P_n → Q_n).

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

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

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

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

Х _i-1 ⇒ X _i , то говорят, что Х_n порождается из Х₀ (Х₀ порождает Х_n), и обозначают как Х₀ ⇒ * X_n. .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Элементы основ­ного словаря (понятий языка) называют терминальными (основными) символами.

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

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

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

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

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

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

Правила подстановки (продукции). Это выражения вида «X —> Y», «Х вместо Y», где Х и Y – цепочки, содержащие любые терминальные или нетерминальные символы.

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

Непосредственная выводимость. Если имеются цепочки Х и Y, которые можно представить в виде X = Z₁ a Z₂ и Y = Z₁ b Z₂, где а a» b – одно из правил грамматики G, то говорят, что цепочка Y непосредственно выводима из цепочки Х в грамматике G. Другими словами, цепочка Х может быть переработана в цепочку Y за один шаг применением одной подстановки: Х получается из Y подстановкой b на ме­сто некоторого вхождения цепочки а. Это обозначается как Х / G = Y.

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

Выводимость. Если имеется последовательность цепочек Х₀, Х₁ ,..., Х_n, в ко­торой каждая следующая цепочка непосредственно выводима из предыдущей, то це­почка Х_n выводима из цепочки Х₀. Последовательность цепочек Х₀, Х₁, ..., Х_n называ­ется выводом Х_n изХ₀—в грамматике G.

Существенно, что порождающая грамматика не есть алгоритм, поскольку пра­вила подстановки представляют собой не последовательность предписаний, а сово­купность решений. Это означает, что, во-первых, правило вида а → b понимается в грамматике как «а можно заменить на b» (но можно и не заменять); в алгоритме же а → b означало бы «а следует заменить на b» (нельзя не заменять); во-вторых, поря­док применения правил в грамматике произволен: любое правило, в принципе, раз­решается применять после любого.

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

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

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

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

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

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

Характеристики

Список файлов лекций