Грамматика, правила, цепочки.
Date: 2015-10-07; view: 482.
Порождающая грамматика (грамматика Хомского) – один из видов формальной грамматики. Порождающая грамматика – грамматика G=(T,N,S,P), состоящая из упорядоченной четверки: T – конечного множества терминальных (основных) символов – терминалов, которое составляет основной алфавит, N – множества нетерминалов – вспомогательных символов (T и N – не пересекающиеся конечные множества), S – символа из множества N, называемого начальным символом, Р – конечного подмножества множества, называемого множеством правил, которое описывает процесс порождения цепочек языка.
Элементpi=(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;
· порождает (есть по определению): знак ®, который отделяет левую часть правила от правой (A® cd – A порождает cd).
Обозначения определяют некоторый язык, предназначенный для описания правил построения цепочек, а значит, для описания других языков. Язык, предназначенный для описания другого языка, называется метаязыком.
Терминальной цепочкой, порождаемой грамматикой G, называется выводимая цепочка грамматики G, не содержащая нетерминалов. a Þ b или a ->b – из цепочки a выводится цепочка b, aи b – цепочки, состоящие из терминалов и нетерминалов, b – выводимая цепочка.
Язык, порождаемый грамматикой, – язык L(G), порождаемый грамматикой G=(T, N, S, P), – это множество терминальных цепочек, порождаемых грамматикой G. Таким образом, L(G) – это все цепочки в алфавите T, которые выводимы из S (начального символа) с помощью правил P.
Сентенциальная форма в грамматикеG=(T, N, S, P) – это цепочка, принадлежащая объединению терминалов и нетерминалов: αÎ (T È N)*, для которой S Î α. Таким образом, язык, порождаемый грамматикой, можно определить как множество терминальных сентенциальных форм.
| <== previous lecture | | | next lecture ==> |
| Формальная порождающая грамматика | | | Некоторые свойства грамматик. |