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

Порождающей грамматикой называется упорядоченная четверка 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, zc индексами или без них - цепочки, составленные из терминальных сим­волов, а буквами a,b,g … - из любых символов. Кроме того, для обозначения правил

a®b₁

a®b₂

_………..

a®b_n

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

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