programming.systems.cpp.11.grammars (Лекции Волковой 2015)
Описание файла
Файл "programming.systems.cpp.11.grammars" внутри архива находится в папке "Лекции Волковой 2015". PDF-файл из архива "Лекции Волковой 2015", который расположен в категории "". Всё это находится в предмете "практикум (прикладное программное обеспечение и системы программирования)" из 4 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст из PDF
Теория формальных языков и грамматик. Определения 1.Цепочка символов в алфавите V - любая конечная последовательностьсимволов этого алфавита.Пустая цепочка ( ) - цепочка, которая не содержит ни одного символа.Если и - цепочки, то цепочка - конкатенация цепочек и .Например, если = ab и = cd, = = .то = abcd,Обращение (или реверс) цепочки - цепочка, символы которой записаны вобратном порядке, обозначается как R.Например, если = abcdef,то R = fedcba, = R.n-ая степенью цепочки (n) – конкатенация n цепочек ;0 = ;n = n-1 = n-1 .Длина цепочки - количество составляющих ее символов.Например, если = abcdefg, то длина равна 7.Длину цепочки обозначается | | .
| | = 0Определения 2.Язык в алфавите V - это подмножество цепочекконечной длины в этом алфавите.V* - множество, содержащее все цепочки конечнойдлины в алфавите V, включая пустую цепочку .Например, если V = { 0, 1 }, тоV* = {, 0, 1, 00, 11, 01, 10, 000, 001, 011, ...}.V+ - множество, содержащее все цепочки конечнойдлины в алфавите V, исключая пустую цепочку .V* = V+ { }.Порождающая грамматикаПорождающая грамматика G - это четверкаG = (T, N, P, S) ,гдеT – непустое множество терминальных символов( алфавит терминалов ),N – непустое множество нетерминальных символов(алфавит нетерминалов), не пересекающийся с T,P - конечное подмножество множества (T N)+ (T N)*.Элемент (, ) множества P называется правилом вывода изаписывается в виде → ,причем содержит хотя бы один нетерминальный символ.S - начальный символ (цель) грамматики, S N.Декартовым произведением A B множеств A и B называетсямножество { (a,b) | a A, b B}.Соглашения1) Большие латинские буквы будут обозначать нетерминальные символы.2) S - будет обозначать начальный символ (цель) грамматики.3) Маленькие греческие буквы будут обозначать цепочки символов.4) Все остальные символы (маленькие латинские буквы, знаки операций и пр.)будем считать терминальными символами.5) для записи правил вывода с одинаковыми левыми частями 1 2 ...
nбудем пользоваться сокращенной записью 1 | 2 |...| n.Каждое i , i = 1, 2, ... ,n , будем называть альтернативой правила вывода изцепочки .Пример грамматики:G1 = ( {0,1}, {A,S}, P, S), где P состоит из правил:S 0A10A 00A1A Определения 3.Цепочка (T N)* непосредственно выводима из цепочки (T N)+ вграмматике G = (T, N, P, S) , обозначается: ,если = 1 2, = 1 2, где 1, 2, (T N)*, (T N)+и правило вывода содержится в P.Цепочка (T N)* выводима из цепочки (T N)+ в грамматикеG = (T, N, P, S), обозначается ,если существуют цепочки 0, 1, ...
, n (n >= 0), такие, что = 0 1 ... n = .Последовательность 0, 1,..., n называется выводом длины n.Язык, порождаемый грамматикой G = (T, N, P, S) - L(G) = { T* | S }.Сентенциальная форма в грамматике G = (T, N, P, S) - цепочка (T N)*,для которой S .Язык, порождаемый грамматикой - множество терминальныхсентенциальных форм.Определения 4.Грамматики G1 и G2 называются эквивалентными,если L(G1) = L(G2).Например,G1 = ({0,1}, {A,S}, P1, S)иG2 = ({0,1}, {S}, P2, S)P1: S 0A1P2: S 0S1 | 010A 00A1Aэквивалентны, т.к.
обе порождают язык L(G1) = L(G2) = { 0n 1n | n > 0}.Грамматики G1 и G2 почти эквивалентны,если L(G1) {} = L(G2) {}.Например,G1 = ( {0,1}, {A,S}, P1, S )P1: S 0A10A 00A1A почти эквивалентны, так какL(G1) = { 0n 1n | n > 0 }, аиG2 = ( {0,1}, {S}, P2, S )P2: S 0S1 | L(G2) = { 0n 1n | n >= 0 }.Классификация грамматик и языков по ХомскомуТИП 0:Грамматика G = (T, N, P, S) - грамматика типа 0, если на ее правила вывода ненакладывается никаких ограничений.ТИП 1:Грамматика G = (T, N, P, S) - неукорачивающая грамматикой, если каждоеправило из P имеет вид → , где (T N)+, (T N)+ и | | <= | |.Исключение - в неукорачивающей грамматике допускается наличие правилаS → , при условии, что S (начальный символ) не встречается в правыхчастях правил.Грамматика G = (T, N, P, S) - контекстно-зависимая ( КЗ ), если каждоеправило из P имеет вид → , где = 1 A 2; = 1 2; A N; (T N)+; 1, 2 (T N)*.В КЗ-грамматике допускается Исключение.Грамматику типа 1 можно определить как неукорачивающую либо какконтекстно-зависимую.Классификация грамматик и языков по ХомскомуТИП 2:Грамматика G = (T, N, P, S) - контекстно-свободная ( КС ), если каждоеправило из Р имеет вид A → , где A N, (T N)*.Грамматика G = (T, N, P, S) - неукорачивающая контекстно-свободная(НКС), если каждое правило из Р имеет вид A → , где A N, (T N)+.В неукорачивающей КС-грамматике допускается Исключение.Грамматику типа 2 можно определить как контекстно-свободную либо какнеукорачивающую контекстно-свободную.ТИП 3:Грамматика G = (T, N, P, S) - праволинейная, если каждое правило из Р имеетвид имеет вид: A → wB либо A → w, где A, B N, w T *.Грамматика G = (T, N, P, S) - леволинейная, если каждое правило из Р имеетвид: A → Bw либо A → w, где A, B N, w T *.Грамматику типа 3 (регулярную, Р-грамматику) можно определить какправолинейную либо как леволинейную.Автоматная грамматика - праволинейная (леволинейная) грамматика, такая,что каждое правило с непустой правой частью имеет вид: A → a либо A → aB(для леволинейной, A → a либо A → Ba), где A, B N, a T.Соотношения между типами грамматикнеук.
Р неук. КС КЗ Тип 0(1) Любая регулярная грамматика является КСграмматикой.(2) Любая неукорачивающая КС-грамматика является КЗ,грамматикой.(3) Любая неукорачивающая грамматика являетсяграмматикой типа 0.Язык L(G) является языком типа k по Хомскому, если егоможно описать грамматикой типа k, где k - максимальновозможный номер типа грамматики по Хомскому.Соотношения между типами языковР КС КЗ Тип 0(1) Каждый регулярный язык является КС-языком, но существуют КСязыки, которые не являются регулярными( например, L = { an bn | n > 0 }).(2) Каждый КС-язык является КЗ-языком, но существуют КЗ-языки,которые не являются КС-языками( например, L = { an bn cn | n > 0 }).(3) Каждый КЗ-язык является языком, типа 0, но существуют языки типа0, которые не являются КЗ-языками(например: язык, состоящий из записей самоприменимыхалгоритмов Маркова в некотором алфавите).(4) Кроме того, существуют языки, которые вообще нельзя описать спомощью порождающих грамматик.
Такие языки не являютсярекурсивно перечислимым множеством.Проблема, можно ли язык, описанный грамматикой типа k, описатьграмматикой типа k + 1 (k = 0, 1, 2), является алгоритмическинеразрешимой.Диаграмма Венна для классов языков.