Лекции Русакова (1021002), страница 11
Текст из файла (страница 11)
С учетом перечисленных свойств операции оэта пара представляет собой полугруппу с единичным элементом ε илимоноид.Определение.Полугруппой в алгебре называют только множество (в данном случаеА*), снабженное всюду определенной ассоциативной операцией.Определение группы.Пусть задано множество элементов 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.106Определение.Любое множество цепочек L ≤ А* ( где А* – моноид, множество всехвозможных цепочек), называется формальным языком, если это множествоцепочек определено на алфавите А.Пример 1.
Пусть А – множество букв русского алфавита. Тогдамножество цепочек, составленных из пяти букв, представляет собойформальный язык L1.Другой пример языка, определенного на том же алфавите – множествоL2 пятибуквенных слов русского языка, которые можно разыскать ворфографическом словаре. Очевидно L2 ⊂ L1, так как многие цепочки языкаL1 не являются русскими словами.Определение.Пусть В и С – некоторые подмножества множества А*. Произведениеммножеств В и СназываетсямножествоD цепочек, являющихсяконкатенацией цепочек из В и С, т.
е. D = { X o Y | X ∈ B, Y ∈ C}.Обозначается произведение следующим образом: D = ВC.Определение.Рассмотрим алфавит А.Обозначим множество, состоящее из ε, через А0.Определим степень алфавита как Аn = An-1oA для каждого n ≥ 1.Нетрудно показать, что множество всех возможных цепочек алфавитаТакое множество называют итерацией алфавита А.107Определение.Усеченной итерацией алфавита А называютЕсли 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 являются смежными цепочками.108Определение.ЦепочкаХnсоотносимасцепочкойХ0,еслипоследовательность цепочек Х0, Х1, ..., Хn , такая, что Хi-1существуети Хi являютсясмежными цепочками.Пример 2. Пусть А – множество букв русского алфавита, на которомопределим соотношение Туэ, заключающееся в праве замены любой однойбуквы слова на любую другую.
Тогда в последовательности цепочек МУКА,МУЗА, ЛУЗА, ЛОЗА, ПОЗА, ПОРА, ПОРТ, ТОРТ, две любые соседниецепочки являются смежными, а цепочки МУКА и ТОРТ являютсясоотносимыми в смысле заданных соотношений.Введение соотношений Туэ позволяет выделить среди множестваязыков определенные их классы, которые используются при построенииавтоматно лингвистических моделей самого различного типа.Определение.Соотношения Туэ являются двусторонними, если цепочка Х являетсясмежной по отношению к цепочке Y, и наоборот, цепочка Y являетсясмежной по отношению к цепочке Х.Более интересными, с точки зрения теории формальных грамматик,являются соотношения, в которых введено направление.Определение.Если в соотношении Туэ определено направление, то их называютполусоотношениями Туэ или продукциями и обозначают следующимобразом:109(Р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. Определение и способы описания формальныхграмматик.Теория формальных языков (формальных грамматик) занимаетсяописанием, распознаванием и переработкой языков.
Описание любого языкадолжно быть конечным, хотя сам язык может содержать бесконечноемножество цепочек. Полезно иметь возможность описания отдельных типовязыков, имеющих те или иные свойства, т. е. иметь различные типыконечных описаний.110Предположим, что имеется некоторый класс языков L, которыйзадается определенным типом описаний.Теория формальных языков позволяет ответить на ряд вопросов,возникающих во многих прикладных задачах, в которых используютсяавтоматно-лингвистические модели. Например, могут ли языки из класса Lраспознаваться быстро и просто; принадлежит ли данный язык классу L и т.д.
Важной проблемой является построение алгоритмов, которые давали быответы на определенные вопросы о языках из класса L, например:«Принадлежит цепочка Х языку L или не принадлежит?»Существуют два основных способа описания отдельных классовязыков.1. Описание, основанное на ограничениях, которые налагаются насистему полусоотношений Туэ (продукций), на базе которых определяютсяграмматики как механизмы, порождающие цепочки символов.2.
Описание языка в терминах множества цепочек с помощью некоторогораспознающего устройства. Такие устройства будем называть автоматами(автоматами-распознавателями).Определение.Термин формальная грамматика представляет собой общее названиенескольких типов исчислений, используемых в математической лингвистикедляописаниястроенияестественныхязыков,атакженекоторыхискусственных языков, в частности, языков программирования.Определение.Подграмматикамивматематическойлингвистикепонимаютнекоторые специальные системы правил, задающие (или характеризующие)111множества цепочек (конечных последовательностей) символов. Эти объектымогут интерпретироваться как языковые объекты различных уровней,например, как словоформы, словосочетания и предложения (цепочкисловоформ) и т. п.Следовательно, формальные грамматики имеют дело с абстракциями,возникающими в результате обобщения таких стандартных лингвистическихпонятий как словоформа, словосочетание и предложение.
Из определенногонабора символов (обозначающих, например, все словоформы русского языка)можно строить произвольные цепочки; одни из них естественно считатьправильнымиилидопустимыми,адругие-неправильнымиилинедоступными.Структурные методы распознавания базируются на порождающейграмматике — системе, состоящей из четырех частей: основной, илитерминальный словарь; вспомогательный словарь; начальный символ; наборправил подстановки исходных элементов, из которых строят цепочки,порождаемые грамматикой.Определение.Элементыосновногословаря(понятийязыка)называюттерминальными (основными) символами.Определение.Нетерминальный (вспомогательный) словарь.
Это набор символов,которыми обозначаются классы исходных элементов или цепочек исходныхэлементов, а также в отдельных случаях некоторые специальные элементы(вспомогательные или нетерминальные).112Определение.Начальный символ. Это выделенный нетерминальный символ,обозначающий совокупность (класс) всех тех языковых объектов, дляописания которых предназначается данная грамматика.Так в грамматике, порождающей предложения, начальным будетсимвол, означающий предложение; в грамматике, порождающей допустимыеслоги, начальный символ означает слог, и т. п.Определение.Правила подстановки (продукции). Это выражения вида «X —> Y»,«Х вместо Y», где Х и Y – цепочки, содержащие любые терминальные илинетерминальные символы.Определение.Непосредственная выводимость.
Если имеются цепочки Х и Y,которые можно представить в виде X = Z1 a Z2 и Y = Z1 b Z2, где а a» b – одноиз правил грамматики G, то говорят, что цепочка Y непосредственновыводима из цепочки Х в грамматике G. Другими словами, цепочка Х можетбыть переработана в цепочку Y за один шаг применением однойподстановки: Х получается из Y подстановкой b на место некотороговхождения цепочки а.
Это обозначается как Х / G = Y.Определение.Выводимость. Если имеется последовательность цепочек Х0, Х1 ,..., Хn,в которой каждая следующая цепочка непосредственно выводима из113предыдущей, то цепочка Хn выводима из цепочки Х0. Последовательностьцепочек Х0, Х1, ..., Хn называется выводом Хn изХ0—в грамматике G.Существенно, что порождающая грамматика не есть алгоритм,поскольку правила подстановки представляют собой не последовательностьпредписаний, а совокупность решений. Это означает, что, во-первых,правило вида а → b понимается в грамматике как «а можно заменить на b»(но можно и не заменять); в алгоритме же а → b означало бы «а следуетзаменить на b» (нельзя не заменять); во-вторых, порядок применения правилв грамматике произволен: любое правило, в принципе, разрешаетсяприменять после любого.Определение.Язык,порожденныйграмматикойэтоСовокупностьвсехтерминальных цепочек, т. е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
