Преобразование КС-грамматик к приведенному виду

Содержание

Введение…………………………………………………………………..3

1. Основные понятия  и определения теории формальных  языков……4

2. Классификация  грамматик и языков по Хомскому…………………6

3. Приведенные  грамматики…………………………………………….8

4. Преобразования  грамматик…………………………………………...9

      4.1. Алгоритм удаления бесплодных  символов…………………9

     4.2.  Алгоритм удаления недостижимых  символов……………..9

     4.3. Преобразование неукорачивающих  грамматик……………10

     4.4. Исключение цепных правил………………………………...12

5. Разработка  программы……………………………………………….14

Литература

Приложение  

Аннотация

       В курсовой работе рассматривается преобразование КС-грамматик к приведенному виду. Рассмотрены основные понятия и  концепции преобразования.

       Работа  содержит     страниц машинописного  текста,     библиографических источников.

Введение

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

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

           Если бы все языки состояли  из конечного числа предложений,  то не было бы проблемы синтаксиса. Но, так как язык содержит неограниченное (или довольно большое) число правильно построенных фраз, то возникает проблема описания бесконечных языков с помощью каких-либо конечных средств.

           Различают следующие виды описания  языков:

           1) порождающее, которое предполагает наличие алгоритма,             последовательно порождающего все правильные предложения языка;

           2) распознающее, которое предполагает  наличие алгоритма, определяющего

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

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

       Алфавит - это конечное множество символов.

       Например, алфавит A = {a, b, c, +, !} содержит 5 букв, а  алфавит B = {00, 01, 10, 11} содержит 4 буквы, каждая из которых состоит из двух символов.

       Цепочкой  символов в алфавите V называется любая конечная последовательность символов этого алфавита.

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

       Более формально цепочка символов в  алфавите V определяется следующим образом:

       1) l - цепочка в алфавите V;

       2) если α - цепочка в алфавите V и a - символ этого алфавита, то αa или аa - цепочка в алфавите V;

       3) β - цепочка в алфавите V тогда и только тогда, когда она является таковой в силу (1) и (2).

       Если  α и β - цепочки, то цепочка αβ называется конкатенацией (или сцеплением) цепочек α и β.

       Например, если α = ab и β = cd, то αβ = abcd.

       Для любой цепочки α всегда αl = lα = α.

       Обращением (или реверсом) цепочки α называется цепочка, символы которой записаны в обратном порядке.

       Обращение цепочки α будем обозначать α^R.

       Например, если α = abcdef, то α^R = fedcba.

       Для пустой цепочки: l = l^R.

       n-ой  степенью цепочки  α(будем обозначать αⁿ) называется конкатенация n цепочек α

       α⁰ = l; αⁿ = αα^n-1 = α^n-1α. 

       Длина цепочки - это число составляющих ее символов.

       Например, если α = abcdefg, то длина α равна 7.

       Длину цепочки α будем обозначать |α|. Длина l равна 0.

       Язык  в алфавите V - это подмножество цепочек конечной длины в этом алфавите.

       Обозначим через V^* множество, содержащее все цепочки в алфавите V, включая пустую цепочку l.

       Например, если V={0,1}, то V^* = {l, 0, 1, 00, 11, 01, 10, 000, 001, 011, ...}.

       Обозначим через V⁺ множество, содержащее все цепочки в алфавите V, исключая пустую цепочку l.

       Следовательно, V^* = V⁺ U {l}.

       Ясно, что каждый язык в алфавите V является подмножеством множества V^*.

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

  2. Классификация грамматик и языков по Хомскому

       Н.Хомский  определил четыре типа грамматик: тип0, тип1, тип2 и тип3.

       Формально грамматика G  - это совокупность четырех объектов.

                     G = (VT, VN, Р, S)

1. Стартовый символ, задающий вид строк описываемого языка на самом верхнем уровне (S);
2. Нетерминальные символы (переменные), традиционно обозначаемые заглавными латинскими буквами (VN);
3. Терминальные символы – базовые, атомарные элементы языка, формирующие его алфавит (VT);
4. Собственно правила вывода, каждое из которых сопоставляет некоторой переменной или стартовому символу строку, состоящую из конкатенации произвольных терминальных и нетерминальных символов (P).

         Соответствующий тип грамматики  определяется теми ограничениями,  которые налагаются на продукцию  Р. Если таких ограничений нет, грамматика принадлежит к типу 0.

       Единственное  ограничение, налагаемое налагаемое на длину цепочек α и β:

                         │α│ ≤ │β│

       относит грамматику к типу 1. Такие грамматики также называют контекстно-зависимыми, грамматиками непосредственных составляющих (НС-грамматики).

       В том случае, когда цепочка α  состоит из одного символа, то есть α є VN, грамматики относят к типу 2. В это случае их называют бесконтекстными (контекстно-свободными или КС-грамматиками).

       Регулярными грамматиками (типа3) называют такие, для которых α є VN, а       β є VT VN либо β є VT. Иными словами, правые части продукций регулярных грамматик состоят либо из одного терминального и одного нетерминального символов, либо из одного терминального символа.

       В курсовой работе будем рассматривать контекстно-свободные грамматики (КС-грамматики). Правила имеют вид А → с, где А – переменная, а с – строка над алфавитом (VT U VN). Такая грамматика называется контекстно-свободной потому, что правило А → с может применяться независимо от того, в каком контексте встретилась переменная А (то есть независимо от того, какие символы её окружают). Обычно стартовый символ грамматики не выделяют явным образом: по умолчанию считается, что переменная в левой части самого первого правила и есть стартовый символ.

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

       Например

       S → aS | bS | cS

       Здесь три правила, а не одно. 
 
 
 
 
 
 
 
 
 

3. Приведенные грамматики

       Приведенные грамматики — это КС-грамматики, которые не содержат недостижимых и бесплодных символов, циклов и l-правил («пустых» правил). Приведенные грамматики называют также КС-грамматиками в каноническом виде.

       Для того, чтобы преобразовать произвольную КС-грамматику к приведенному виду, необходимо выполнить следующие действия:

• удалить все бесплодные символы;
• удалить все недостижимые символы;
• удалить l-правила;
• удалить цепные правила.

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

  4. Преобразования грамматик

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

       Определение: символ A є VN называется бесплодным в грамматике G = (VT, VN, P, S), если множество { a | a є VT^*, A => a} пусто.

       Определение: символ x є (VT U VN) называется недостижимым в грамматике G = (VT, VN, P, S), если он не появляется ни в одной сентенциальной форме этой грамматики. 

4.1. Алгоритм удаления бесплодных символов

       Вход: КС-грамматика G = (VT, VN, P, S).

       Выход: КС-грамматика G’ = (VT, VN’, P’, S), не содержащая бесплодных символов, для которой L(G) = L(G’).

       Метод:

       Рекурсивно  строим множества N₀, N₁, ...

1. N₀ = Æ, i = 1.
2. N_i = {A | (A → a) є P и a є (N_i-1 U VT)^*} U N_i-1.

3. Если N_i ≠ N_i-1, то i = i+1 и переходим к шагу 2, иначе VN’ = N_i; P’ состоит из правил множества P, содержащих только символы из     VN’ È VT; G’ = (VT, VN’, P’, S). 
   

  

4.2.Алгоритм удаления недостижимых символов

       Вход: КС-грамматика G = (VT, VN, P, S)

       Выход: КС-грамматика G’ = (VT’, VN’, P’, S), не содержащая недостижимых символов, для которой L(G) = L(G’).

       Метод:

1. V₀ = {S}; i = 1.
2. V_i = {x | x є (VT U VN), (A → axb) Î P и A є V_i-1} U V_i-1.
3. Если V_i ≠ V_i-1, то i = i+1 и переходим к шагу 2, иначе VN’ =  
   V_i Ç VN;  VT’ = V_i Ç VT; P’ состоит из правил множества P, содержащих только символы из Vi; G’ = (VT’, VN’, P’, S).

       Удаление  символов сопровождается удалением  правил вывода, содержащих эти символы.

       Если  в этом алгоритме переставить  шаги (1) и (2), то не всегда результатом будет правильным.