Формальные грамматики

Теория формальных грамматик - раздел дискретной математики, изучающий способы описания закономерностей, характеризующих всю совокупность правильных текстов того или иного языка.

Формальные грамматики - это абстрактные системы, позволяющие с помощью единообразных процедур получать правильные тексты данного языка вместе с описанием их структуры. Теория формальных грамматик занимает центральное место в математической лингвистике, так как именно она позволяет моделировать наиболее существенный аспект функционирования языка - переработку смыслов в тексты и обратно. Вместе с тем она выделяется среди других разделов математической лингвистики большей сложностью математического аппарата (сходного с аппаратом теории алгоритмов и общей теории автоматов) и возникающих в ней математических задач. Формальные грамматики наиболее разработанных типов представляют собой системы (устройства), которые позволяют порождать или распознавать множества конечных последовательностей (цепочек), интерпретируемые обычно как множества правильных предложений, а также сопоставлять входящим в эти множества цепочкам описания их синтаксической структуры в терминах систем составляющих или деревьев подчинения.

Грамматикой называется четверка G = (N, T, P, S), где N - конечное множество нетерминальных символов (нетерминалов), T - множество терминалов (не пересекающихся с N), S - символ из N, называемый начальным, Р - конечное подмножество множества:

(N È T)^* N (N È T)^* x (N È T)^*,

называемое множеством правил. Множество правил Р описывает процесс порождения цепочек языка. Элемент p_i = (a, b) множества Р называется правилом (продукцией) и записывается в виде a Þ b. Здесь a и b - цепочки, состоящие из терминалов и нетерминалов. Данная запись может читаться одним из следующих способов:

• цепочка a порождает цепочку b;
• из цепочки a выводится цепочка b.

Таким образом, правило P имеет две части: левую, определяемую, и правую, подставляемую. То есть правило p_i - это двойка (p _i1, p_i2), где p _i1 = (N È T)^* N (N È T)^* - цепочка, содержащая хотя бы один нетерминал, p_i2 = (N È T)^* - произвольная, возможно пустая цепочка (e - цепочка).

Если цепочка a содержит p_i1, то, в соответствии с правилом p_i, можно образовать новую цепочку b, заменив одно вхождение p_i1 на p_i2. Говорят также, что цепочка b выводится из a в данной грамматике.

Для описания абстрактных языков в определениях и примерах будем пользоваться следующими обозначениями:

• терминалы обозначим буквами 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”.

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

Пример грамматики G1:

G1 = ({A, S}, {0, 1}, P, S),

где P:

1. S ® 0A1;

1. 0A ® 00A1;

2. A ® e.

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

Язык L(G), порождаемый грамматикой G, - это множество терминальных цепочек, порождаемых грамматикой G.

Введем отношение Þ_G непосредственного вывода на множестве (N È T) *, которое будем записывать следующим образом:

j Þ_G y.

Данная запись читается: y непосредственно выводима из j для грамматики G = (N, T, P, S) и означает: если abg - цепочка из множества (N È T) * и b ® d - правило из Р то abg Þ_G adg.

Через Þ_G⁺ обозначим транзитивное замыкание (нетривиальный вывод за один и более шагов). Тогда j Þ_G⁺ y читается как: y выводима из j нетривиальным образом.

Через Þ_G^* - обозначим рефлексивное и транзитивное замыкание (вывод за ноль и более шагов). Тогда j Þ_G^* y означает: y выводима из j.

Пусть Þ^k k - я степень отношения Þ. То есть, если a Þ^k b, то существует последовательность a₀a₁a₂a₃ ... a_k из к+1 цепочек

a = a₀, a₁,... a_{i -1} Þ a_i, 1 ≤ i ≤ k и a_k = b.

Пример выводов для грамматики G1:

S Þ 0A1 Þ 00A11 Þ 0011;

S Þ¹ 0A1; S Þ² 00A11; S Þ³ 0011;

S Þ⁺ 0A1; S Þ⁺ 00A11; S Þ⁺ 0011;

S Þ ^* S; S Þ ^* 0A1; S Þ ^* 00A11; S Þ ^* 0011;

где 0011 Ì L(G1).