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



страница4/22
Дата07.11.2012
Размер1.2 Mb.
ТипКонспект
1   2   3   4   5   6   7   8   9   ...   22

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


Порождающей грамматикой называется упорядоченная четверка G=< VN, VT, S, R>, где VT алфавит терминальных или основных символов; VNалфавит нетерминальных или вспомогательных символов (VTVN = ); Sначальный символ или аксиома, S VN, R конечное множество правил или продукций вида , где (VTVN )* VN (VTVN )*, (VTVN )* – различные цепочки, а специальный символ, не принадлежащий VTVN и служащий для отделения левой части правила от правой . Такие символы, которые служат для описания языка, но не принадлежат самому языку, будем называть метасимволами. Определим, что цепочка 1 непосредственно выводима из цепочки 0 (обозначается 01 ), если существуют такие 1, 2, , , что 01 2, 11 2 и существует правило  ( R). Иными словами 01, если в 0 найдется вхождение левой части какого-либо правила грамматики, а цепочка 1 получена заменой этого вхождения на правую часть правила.

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


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

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

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

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

L(G) = {x / S * x & xVT* }.

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

Определим, что грамматики G1 и G2 эквивалентны, если L(G1 )=L(G2).

Например,

G1 = < {S}, {a}, S, { Sa, S a a S}>, L(G1)= {a 2n+1, n 0}.

G2 = < {S, A}, {0, 1}, S, R>, R = {S 1 A, A 1 A, A 0 A, A 0 }, L(G2) – множество четных двоичных чисел, больших нуля.

G3 = < {S, A}, {0, 1}, S, R>, R = {S 1 A 0, A 1 A, A 0 A, A  }, L(G2) = L(G3), грамматики G2 и G3 эквивалентны.

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

Правила вида , где VT*, называются заключительными.
1   2   3   4   5   6   7   8   9   ...   22

Похожие:

Конспект лекций москва 2004 удк 519. 713(075)+519. 76(075) ббк 22. 18я7 С32 iconМетодические указания к практическим занятиям Рязань 2004 удк 519. 713 (075)
Теория автоматов в задачах. Ч1: Методические указания к практическим занятиям/ Рязан гос радиотехн акад. Сост.: Н. И. Иопа. Рязань,...
Конспект лекций москва 2004 удк 519. 713(075)+519. 76(075) ббк 22. 18я7 С32 iconУчебное пособие для студентов всех специальностей Москва 2003 ббк 22. 17я7 удк 519. 22 (075. 8) 6Н1 к 60
Калинина В. Н., Соловьев В. И. Введение в многомерный статистический анализ: Учебное пособие / гуу. – М., 2003. – 92 с
Конспект лекций москва 2004 удк 519. 713(075)+519. 76(075) ббк 22. 18я7 С32 iconКонспект лекций москва 2003 ббк вкб / 075 : 378 я 14
История экономики России XX века (1900 – 1917 гг.) : Конспект лекций. – М.: Мгту "Станкин", 2003. – 45 с
Конспект лекций москва 2004 удк 519. 713(075)+519. 76(075) ббк 22. 18я7 С32 iconКонспект лекций санкт-петербург 2009 удк 532. 6(075. 8) Ббк в334я73 а 65 Рецензент И. П. Арешев
Охватывает ток (рис. 16), то
Конспект лекций москва 2004 удк 519. 713(075)+519. 76(075) ббк 22. 18я7 С32 iconКонспект лекций м осква 2000 ббк ВКП / 075 : 378 я 14
История экономики России XIX века: Конспект лекций. М.: Мгту "Станкин", 2000. 68 с
Конспект лекций москва 2004 удк 519. 713(075)+519. 76(075) ббк 22. 18я7 С32 iconКонспект лекций по философии Часть 1 Античная философия Новосибирск 2007 удк 101. 8 (075) ббк ю3я73-1
Савостьянов А. Н. Конспект лекций по философии / Новосиб гос ун-т. Новосибирск, 2007. Ч. Античная философия. 68 с
Конспект лекций москва 2004 удк 519. 713(075)+519. 76(075) ббк 22. 18я7 С32 iconУчебное пособие для студентов всех специальностей Саратов 2009 удк 519. 17 Ббк 22. 174 С 32 Рецензенты
С32 Ведение в теорию графов: учеб пособие. Саратов: Сарат гос техн ун-т, 2009. 36с
Конспект лекций москва 2004 удк 519. 713(075)+519. 76(075) ббк 22. 18я7 С32 iconКонспект лекций Таганрог 2001 удк 621. 382. 019. 3 (075. 8) Механцев Е. Б
Обеспечение надежности электронных средств: конспект лекций. Таганрог: Изд-во трту, 2001
Конспект лекций москва 2004 удк 519. 713(075)+519. 76(075) ббк 22. 18я7 С32 iconКурс лекций Для студентов вузов Кемерово 2006 удк 113/119(075) ббк 87я7 М42 Рецензенты

Конспект лекций москва 2004 удк 519. 713(075)+519. 76(075) ббк 22. 18я7 С32 iconУчебное пособие Москва 2006 удк 341. 645: 347. 922(075) ббк 67. 412. 2 О 23

Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org