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

Грамматика, правила, цепочки.

Формальная порождающая грамматика

Язык.

Язык в некотором алфавите – это подмножество цепочек конечной длины в этом алфавите.

Если задан алфавит A, то существует A^* – множество всевозможных цепочек, которые могут быть построены из букв алфавита A; предполагается, что пустая цепочка (ε или $) также входит в множество A^*.

Пусть V^* – множество, содержащее все цепочки в алфавите V, включая пустую цепочку ε, тогда, если V={0,1}, то V^* = {ε, 0, 1, 00, 11, 01, 10, 000, 001, 011,...}

Таким образом, каждый язык в алфавите V является подмножеством множества V^*.

Порождающая грамматика (грамматика Хомского) – один из видов формальной грамматики.

Порождающая грамматика есть упорядоченная четверка

G = (T, N, S, P)

где T – конечное множество терминальных (основных) символов (терминалов) – основной алфавит

N – множество нетерминалов – вспомогательных символов

T и N – не пересекающиеся конечные множества

S – символ из N, называемый начальным

Р – конечное подмножество множества, называемого множеством правил, которое описывает процесс порождения цепочек языка

Элемент p_i = (a, b) множества Р называется правилом(продукцией)

a Þ b или a ->b

Это означает, что цепочка a порождает цепочку b (из цепочки a выводится цепочка  b), a, b – цепочки, состоящие из терминалов и нетерминалов.

Таким образом, правило P имеет две части: левую, определяемую, и правую, подставляемую.

Обозначения для описания абстрактных языков:

· терминалы: буквы a, b, c, d или цифры 0, 1,..., 9;

· нетерминалы: буквы A, B, C, D, S (нетерминал S – это начальный символ грамматики);

· отдельные терминалы или нетерминалы: буквы U, V,..., Z;

· цепочки терминалов и нетерминалов: a, b, g...;

· цепочки терминалов: u, v, w, x, y, z;

· пустая цепочка (не содержащая ни одного символа) – знак e;

· порождает (есть по определению): знак ®, который отделяет левую часть правила от правой.

Обозначения определяют некоторый язык, предназначенный для описания правил построения цепочек, а значит, для описания других языков. Язык, предназначенный для описания другого языка, называется метаязыком.

Терминальной цепочкой, порождаемой грамматикой G, называется выводимая цепочка грамматики G, не содержащая нетерминалов.

Язык L(G), порождаемый грамматикой G, – это множество терминальных цепочек, порождаемых грамматикой G. Таким образом, L(G) – это все цепочки в алфавите T, которые выводимы из S (начальный символ) с помощью P (правила).

Цепочка α Î (T U N)^*, для которой S Î α, называется сентенциальной формой в грамматике G = (T, N, S, P).

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

Дата добавления: 2014-01-11