Сентенциальная форма грамматики. Язык, заданный грамматикой

Вывод называется законченным, если на основе цепочки р, полученной в результате вывода, нельзя больше сделать ни одного шага вывода. Иначе говоря, вывод называется законченным, если цепочка β, полученная в результате вывода, пустая или содержит только терминальные символы грамматики G(VT,VN,P,S): βeVT*. Цепочка β, полученная в результате законченного вывода, называется конечной цепочкой вывода.

В рассмотренном выше примере все построенные выводы являются законченными, а, например, вывод S =>* -4FF (из первой цепочки в примере) будет незаконченным.

Цепочка символов aeV* называется сентенциальной формой грамматики G(VT, VN,P,S), V = VTuVN, если она выводима из целевого символа грамматики S: S =>* а. Если цепочка ае VT получена в результате законченного вывода, то она называется конечной сентенциальной формой.

Из рассмотренного выше примера можно заключить, что цепочки символов «—479» и «18» являются конечными сентенциальными формами грамматики целых десятичных чисел со знаком, так как существуют выводы S =>* -479 и S =>* 18 (примеры 1 и 2). Цепочка F8 из вывода 2, например, тоже является сентенциальной формой, поскольку справедливо S =>* F8, но она не является конечной цепочкой вывода. В то же время в выводах примеров 3—5 явно не присутствуют сентенциальные формы. На самом деле цепочки «350», «1004» и «5» являются конечными сентенциальными формами. Чтобы доказать это, необходимо просто построить другие цепочки вывода (например, для цепочки «5» строим: S => Т => F => 5 и получаем S => * 5). А вот цепочка «TFT» (пример 4) не выводима из целевого символа грамматики S, а потому сентенциальной формой не является.

Язык L, заданный грамматикой G(VT,VN,P,S), — это множество всех конечных сентенциальных форм грамматики G. Язык L, заданный грамматикой G, обозначается как L(G). Очевидно, что алфавитом такого языка L(G ) будет множество терминальных символов грамматики VT, поскольку все конечные сентенциальные формы грамматики — это цепочки над алфавитом VT.

Следует помнить, что две грамматики G(VT,VN,P,S) и G'(VT',VN',P',S') называются эквивалентными, если эквивалентны заданные ими языки: L(G) = L(G'). Очевидно, что эквивалентные грамматики должны иметь, по крайней мере, пересекающиеся множества терминальных символов VTnVT' ≠ O (как правило, эти множества даже совпадают VT = VT), а вот множества нетерминальных символов, правила грамматики и целевой символ у них могут кардинально отличаться.

Левосторонний и правосторонний выводы

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

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

Если рассмотреть цепочки вывода из того же примера, то в нем выводы 1 и 5 являются левосторонними, выводы 2, 3 и 5 — правосторонними (вывод 5 одновременно является и лево- и правосторонним), а вот вывод 4 не является ни левосторонним, ни правосторонним.

Для грамматик типов 2 и 3 (КС-грамматик и регулярных грамматик) для любой сентенциальной формы всегда можно построить левосторонний или правосторонний выводы. Для грамматик других типов это не всегда возможно, так как по структуре их правил не всегда можно выполнить замену крайнего левого или крайнего правого нетерминального символа в цепочке.

А вот рассмотренный выше вывод S => * aaaabbbbcccc для грамматики G₃, задающей язык L(G₃) = (Oⁿlⁿ|n > 0}, не является ни левосторонним, ни правосторонним. Грамматика относится к типу 1, и в данном случае для нее нельзя построить такой вывод, на каждом шаге которого только один нетерминальный символ заменялся бы на цепочку символов.