Конспект лекций москва 2004 удк 519. 713(075)+519. 76(075) ббк 22. 18я7

Вид материала

Конспект

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

Подобный материал:

• Учебное пособие тверь 2008 удк 519. 876 (075. 8 + 338 (075. 8) Ббк 3817я731-1 + 450., 2962.9kb.
• Тексты лекций Москва 2008 удк 339. 9(075. 8) Ббк 65. 5я73-2, 1528.45kb.
• Программно-технический комплекс Учебное пособие Новочеркасск юргту (нпи) 2010. Удк, 3911.73kb.
• Удк 152. 27 (075. 8) + 157 (075. 8) + 152. 3 (075, 60.12kb.
• Краткий конспект лекций Кемерово 2002 удк: 744 (075), 1231.26kb.
• Методические указания по курсу Новосибирск 2004 ббк ю 937. 4 Удк 152. 26 (075), 802.63kb.
• Москва 2011 ббк 63. 3 (2)я 7 к 90 удк 947 (075) История России, 110.08kb.
• Курс лекций Гродно 2005 удк 631. 1 (075., 1193.16kb.
• Удк 070(075. 8) Ббк 76. 01я73, 5789.66kb.
• Удк 339. 9(470)(075. 8) Ббк, 7329.81kb.

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

Порождающей грамматикой называется упорядоченная четверка G=< V_N, V_T, S, R>, где V_T – алфавит терминальных или основных символов; V_N — алфавит нетерминальных или вспомогательных символов (V_TV_N =  ); S – начальный символ или аксиома, S V_N, R – конечное множество правил или продукций вида   , где  (V_TV_N )* V_N (V_TV_N )*,  (V_TV_N )* – различные цепочки, а  специальный символ, не принадлежащий V_TV_N и служащий для отделения левой части правила  от правой . Такие символы, которые служат для описания языка, но не принадлежат самому языку, будем называть метасимволами. Определим, что цепочка ₁ непосредственно выводима из цепочки ₀ (обозначается ₀₁ ), если существуют такие ₁, ₂, , , что ₀₁  ₂, ₁₁  ₂ и существует правило  ( R). Иными словами ₀₁, если в ₀ найдется вхождение левой части какого-либо правила грамматики, а цепочка ₁ получена заменой этого вхождения на правую часть правила.

Существенно, что при определении отношения непосредственной выводимости обозначаемого  (, разумеется, также метасимвол) не указывается, какое правило нужно применять и к какому именно вхождению (если их несколько). Здесь проявляются характерные черты исчислений, к классу которых относятся и порождающие грамматики. Исчисления представляют собой "разрешения" в отличие от алгоритмов, являющихся "предписаниями".

Определим, что цепочка _n выводима из цепочки ₀ за один или несколько шагов или просто выводима (обозначается ₀⁺_n ), если существует последовательность цепочек ₀, ₁, ₂,…, _n (n>0), такая, что _i_i+1, i{0, …, n-1}. Эта последовательность называется выводом _n из ₀, а n – длиной вывода. Выводимость за n шагов иногда обозначается ₀ⁿ _n. Наконец, если ₀⁺_n или ₀=_n , то пишут ₀*_n.

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

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

Множество цепочек в основном алфавите грамматики, выводимых из начального символа, иначе множество сентенциальных форм, состоящих из терминальных символов (иначе, сентенций), называется языком, порождаемым грамматикой 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(G₂) = L(G₃), грамматики G₂ и G₃ эквивалентны.

Для сокращения записи грамматик и выводов будем изображать нетерминальные символы прописными буквами латинского алфавита А , В , С , … , S с индексами или без них, терминальные – строчными буквами a, b, c,… и цифрами. Прописными буквами U, V, Z будем обозначать символы, которые могут быть как терминальными, так и нетерминальными; строчными буквами u, v, x, y, z c индексами или без них – цепочки, составленные из терминальных символов, а буквами    … – из любых символов. Кроме того, для обозначения правил ₁, ₂,…, _n будем пользоваться записью ₁₂…_n .

Правила вида   , где   V_T*, называются заключительными.