Лекции (16) (Презентации лекций (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), является алгоритмическинеразрешимой.Диаграмма Венна для классов языков.