Теория формальных языков и грамматик. Определения 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) для записи правил вывода с одинаковыми левыми частями n будем пользоваться сокращенной записью 1 | 2 |...| n. Каждое i, i = 1, 2,...,n, будем называть альтернативой правила вывода из цепочки. Пример грамматики: G1 = ( {0,1}, {A,S}, P, S), где P состоит из правил: S 0A1 0A 00A1 A

Определения 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), такие, что = 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 | 01 0A 00A1 A эквивалентны, т.к. обе порождают язык L(G1) = L(G2) = { 0 n 1 n | n > 0}. Грамматики G1 и G2 почти эквивалентны, если L(G1) { } = L(G2) { }. Например, G1 = ( {0,1}, {A,S}, P1, S )иG2 = ( {0,1}, {S}, P2, S ) P1:S 0A1P2:S 0S1 | 0A 00A1 A почти эквивалентны, так как L(G1) = { 0 n 1 n | n > 0 }, а L(G2) = { 0 n 1 n | n >= 0 }.

Классификация грамматик и языков по Хомскому ТИП 0: Грамматика G = (T, N, P, S) - грамматика типа 0, если на ее правила вывода не накладывается никаких ограничений. ТИП 1: Грамматика G = (T, N, P, S) - неукорачивающая грамматикой, если каждое правило из P имеет вид, где (T N) +, (T N) + и | |

Классификация грамматик и языков по Хомскому ТИП 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 = { a n b n | n > 0 }). (2)Каждый КС-язык является КЗ-языком, но существуют КЗ-языки, которые не являются КС-языками ( например, L = { a n b n c n | n > 0 }). (3)Каждый КЗ-язык является языком типа 0, но существуют языки типа 0, которые не являются КЗ-языками (например: язык, состоящий из записей самоприменимых алгоритмов Маркова в некотором алфавите). (4) Кроме того, существуют языки, которые вообще нельзя описать с помощью порождающих грамматик. Такие языки не являются рекурсивно перечислимым множеством. Проблема, можно ли язык, описанный грамматикой типа k, описать грамматикой типа k + 1 (k = 0, 1, 2), является алгоритмически неразрешимой.,

Диаграмма Венна для классов языков