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

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

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

где 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® 0 A 1;2)0 A® 00 A 1;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 помощью правил множества Р, т.е. множество .