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

Порождающей грамматикой называется упорядоченная четверка G=< V_T,V_N, S, R>, где V_T - алфавит терминальных или основных символов; V_N — алфавит нетерминальных или вспомогательных символов(V_TÇV_N = Æ); S - начальный символ или аксиома, S ÎV_N, R - конечное множество правил или продукций вида j ® y, где j Î(V_TÈV_N)* V_N (V_TÈV_N)*, y Î(V_TÈV_N)* - различные цепочки, а ® специальный символ, не принадлежащий V_TÈV_N и служащий для отделения левой части правила j от правой y. Такие символы, которые служат для описания языка, но не принадлежат самому языку, будем называть метасимволами. Го­ворят, что цепочка w₁ непосредственно выводима из цепочки w₀ (обозначается w₀Þw₁), если существуют такие x₁, x₂, j, y, что w₀=x₁ j x₂, w₁=x₁ y x₂ и существует правило j®y (j®y ÎR). Иными словами w₀Þw₁, если в w₀ найдется вхождение левой части какого-либо пра­вила грамматики, а цепочка w₁ получена заменой этого вхож­дения на правую часть правила. Существенно, что при опреде­лении отношения непосредственной выводимости обозначаемого Þ (Þ разумеется, также метасимвол) мы не указываем, какое правило нужно применять и к какому именно вхождению (если их несколько). Здесь проявляются характерные черты ис­числений, к классу которых относятся и порождающие грамма­тики. Исчисления представляют собой "разрешения" в отличие от алгоритмов, являющихся "предписаниями".

Говорят, что цепочка w_n выводима из цепочки w₀ за один или несколько шагов или просто выводима (обозначается w₀Þ⁺w_n), если существует последовательность цепочек w₁, w₂,…, w_n (n>0), такая, что w_iÞw_i+1, iÎ{0,…n}. Эта последовательность называется выводом w_n из w₀, а n – длиной вывода. Выводимость за n шагов иногда обозначается w₀Þⁿ w_n На­конец, если w₀Þ⁺w_n или w₀=w_n, то пишут w₀Þ*w_n.

Нетрудно видеть, что Þ⁺ есть транзитивное, а Þ* - транзитивно-рефлексивное замыкание отношения Þ.

Цепочка w называется сентенциальной формой, если она совпадает или выводима из начального символа грамматики, т.е. если S Þ w,

Множество цепочек в основном алфавите грамматики, вы­водимых из начального символа, иначе множество сентенциаль­ных форм, состоящих из терминальных символов, называется языком, порождаемым грамматикой G, и обозначается L(G).

L(G) = {x / S Þ* x & xÎV_T }.

Для любого перечислимого множества слов М существует грамматика G, такая, что М= L(G).

Говорят, что грамматики G₁ и G₂ эквивалентны, если L(G₁ )=L(G₂).

Например,

G₁ = < {S}, {a}, S, { S®a, S ®a a S}>

L(G₁)= {a ²ⁿ⁺¹, n³ 0}

G₂ = < {S, A}, {0, 1}, S, R>

R = {S ® 1 A, A ® 1 A, A ® 0 A, A ®0 }

L(G₂) – множество четных двоичных чисел, больших нуля.

G₃ = < {S, A}, {0, 1}, S, R>

R = {S ® 1 A 0, A ® 1 A, A ® 0 A, A ®l }

L(G₂) = L(G₃)

Для сокращения записи грамматик и выводов будем изо­бражать нетерминальные символы прописными буквами латин­ского алфавита А, В, С, …, S терминальные -строчными буквами a, b, c,… и цифрами. Прописными буквами U, V, Z будем обозначать символы, которые могут быть как терминальными, так и нетерминальными; строчными буквами u, v, z c индексами или без них - цепочки, составленные из терминальных сим­волов, а буквами a,b,g … - из любых символов. Кроме того, для обозначения правил

a®b₁

a®b₂

_………..

a®b_n

будем пользоваться записью a®b₁½b₂½…½b_n.

Правила вида j ® y, где y Î V_T, называются заключительными.