Определение формальной грамматики

Формальная грамматика – это математическая система, определяющая язык посредством порождающих правил.

ОпределениеФормальной грамматикой называется четверка вида:

,

где V_N - конечное множество нетерминальных символов грамматики (обычно прописные латинские буквы);

V_T - множество терминальных символов грамматики (обычно строчные латинские буквы, цифры, и т.п.), V_T ÇV_N =Æ;

Р – множество правил вывода грамматики, являющееся конечным подмножеством множества (V_TÈ V_N)⁺ ´ (V_TÈ V_N)^*; элемент (a, b) множества Р называется правилом вывода и записывается в виде a®b (читается: «из цепочки a выводится цепочка b»);

S - начальный символ грамматики, S ÎV_N.

Для записи правил вывода с одинаковыми левыми частями вида используется сокращенная форма записи .

ПримерГрамматика G₁=({0, 1}, {A, S}, P₁, S), где множество Р состоит из правил вида: 1) S® 0A1;2)0A® 00A1;3) A®e.

ОпределениеЦепочка b Î (V_TÈV_N)^* непосредственно выводима из цепочки в грамматике (обозначается:aÞb), если и , где , и правило вывода содержится во множестве Р.

Определение Цепочка b Î (V_TÈV_N)^* выводима из цепочки в грамматике (обозначается aÞ*b), если существует последовательность цепочек (n³0) такая, что .

ПримерВ грамматике G₁ SÞ*000111, т.к. существует вывод .

ОпределениеЯзыком, порожденным грамматикой ,называется множество всех цепочек в алфавите V_T, которые выводимы из начального символа грамматики S c помощью правил множества Р, т.е. множество .

ПримерДля грамматики G₁ язык L(G₁)={0ⁿ1ⁿ | n³0}.

Определение Цепочка , для которой существует вывод SÞ*a, называется сентенциальной формой или сентенцией в грамматике .

ОпределениеЯзыком, порожденным грамматикой G называется множество терминальных сентенциальных форм грамматики.