Главная Промышленная автоматика. (2) 2 -не пересекающееся с N конечное множество терминальных символов, или терминалов, (3) Р - конечное подмножество множества (NU2)*N(NU2)*X(NUS)* (элемент (а, р) множества Р называется правилом (или продукцией) и записывается в виде а-*-р); (4) 5 -выделенный символ из N, иагиваеиъш начальным (или исходным) символом. Пример 2.1. Примером грамматики служит четверка =({Л, 5}, {О, 1}, Р, S), где Р состоит из правил 5->0Л1 ОЛ --О0Л1 Ае Нетерминальными символами являются Л и 5, а терминальными- О и 1. □ Грамматика определяет язык рекурсивным образом. Рекур-сивность проявляется в задании особого рода цепочек, называемых выводимыми цепочками грамматики G(N, 2, Р, S): (1) 5 -выводимая цепочка. (2) Если ар7~выводимая цепочка и р - б содержится в Я, то аб7-тоже выводимая цепочка. Выводимая цепочка грамматики G, не содержащая нетерминальных символов, называется терминальной цепочкой, порождаемой грамматикой G. Язык, порождаемый грамматикой G (обозначается L{G)),- это множество терминальных цепочек, порождаемых грамматикой G. Теперь введем терминологию, которая окажется далее полезной. Пусть G = {N, 2, Р, S) -грамматика. Определим отношение на множестве (NUS)* (ф=:>о1) читается непосредственно выводима из ф) следующим образом: если ау - цепочка из (Nu2) и р-6 -правило из Р, то apYoafiv. Транзитивное замыкание отношения =>с обозначим через =>о (ф= чтгется:выводима из нетривиальным образом), а его рефлексивное и транзитивное замыкание -через =Фа (ф=ф*1) читается: i? выводима из ф). В тех случаях, когда из контекста ясно, о какой грамматике идет речь, нижний индекс G будем опускать. Таким образом, L{G){w\w2*, S=w\. Через будем обозначать -ю степень отношения Иначе говоря, а р, если существует последовательность а, а, ..., а, состоящая из /г+1 цепочек (не обязательно различных), для которых сс = сС(,, a,- i=>a,. при и сср. Эта последо- вательность цепочек называется выводо.м длины k цепочки р из цепочки а в грамматике G. Отметим, что сс=>*р тогда и только тогда, когда a=f> для некоторого t>0, и 0L->f> тогда и только тогда, когда а=4>р для некоторого i> Ь Пример 2.2. Рассмотрим грамматику G из примера 2 Л и вывод 5=фОЛ 1 фООЛ 11 =?>0011. На первом шаге этого вывода 5 заменяется на 0Л1 в соответствии с правилом 5-0Л1. На втором шаге ОЛ заменяется на 00Л1, и на третьем шаге А заменяется на е. Можно сказать, что 5=;>з0011, 5==>+00И, 5=Ф*0011, и что ООН принадлежит языку l{Gj). Можно показать, что L(Gj = {0"l"]n> 1} Доказательство оставляем в качестве упражнения. □ Соглашение. Для обозначения п правил а а удобно пользоваться сокращенной записью Примем еще следующие соглашения относительно различных символов и цепочек, связанных с грамматикой: (1) а, Ь, с, d и цифры О, 1, ...,9 обозначают терминалы; (2) А, В, С, D, S обозначают нетерминалы; 5 - начальный символ; у (3) U,V, ..,, Z обозначают либо нетерминалы, либо терминалы; (4) а, р,.... обозначают цепочки, которые могут содержать как терминалы, так и нетерминалы; (5) и, V, ,.., Z обозначают цепочки, состоящие только из терминалов. Эти согдашения распространяются также и на буквы с нижними и верхними индексами. Мы не будем напоминать об этих соглашениях, когда рассматриваемые символы им удовлетворяют. Таким образом, грамматику, все терминалы и нетерминалы которой подчиняются соглашениям (1) и (2), можно определить, просто выписав все ее правила. Например, грамматику можно задать списком правил S ОЛ 1 ОЛ ООЛ1 А-е Теперь нет необходимости говорить о множествах терминалов и нетерминалов или о начальном символе. Приведем еще примеры грамматик. Пример 2.3. Пусть G({<цифра>}, {О, 1. ....9}, {<цифра>-> 0[ 11.. .9}, .<цнфра». Здесь <цифра> рассматривается как единственный нетерминальный символ, L (G) - это, очевидно, множество, состоящее из десяти цифр. Заметим, что L{G) - конечное множество. П Пример 2.4. Пусть G, = {{E, Т, F}, {а, -]-, (, )}, Р, £), где Р - состоит из правил F-~{E)\a Вот пример вывода в этой грамматике Е-Е-\~Т =>F+T -Фй+Г =Ф tt + G * =?> Q + й * Язык 1(<?о) представляет собой множество арифметических выражений, построенных из символов а, +, х-, ( н ). □ Грамматика из примера 2.4 не раз встретится нам в этой книге; мы всегда будем обозначать ее G. Пример 2.5. Пусть G определяется правилами S-aSBC\abC СВ-~*ВС ЪВ-ЪЬ bCbc сС-сс В грамматике G возможен вывод S-aSBC =Ф ааЬСВС =:ааЬВСС =Ф aabbCC aabbcC =Ф ааЬЬсс Эта грамматика порождает язык {а"Ь"с"\п 1}. □ 108 Пример 2.6. Пусть G - грамматика с правилами
Пример вывода в грамматике G: S=>CD =aCAD =>abCBAD abBAD => abBaD =Ф abaBD =P ababD abab Покажем, что L{G) = {ww\w{a, b}*\, т. e, E(G) состоит из цепочек четной длины, составленных из букв а и Ь, причем первая половина каждой цепочки совпадает со второй половиной. Так как L{G) - множество, то самый легкий способ показать, что L{G){ww\w{a, b}*}, состоит в том, чтобы показать, что {ww\we{a, b}*}L(G) и L{G){ww\we\a, 6}*}. Чтобы показать, что {ww\w {а, о}*} L{G), надо показать, что каждую цепочку вида ww можно вывести из 5. Простой индукцией можно доказать, что в G возможны такие выводы: (1) 5=;>CD. (2) Для я>0 где для всех lin с~а тогда н только тогда, когда Х=Л, и Ci=b тогда и только тогда, когда ХВ. (3) X,.,,X,X,D:= X„...X,c,D = cX„...X,c,D =Ф"-с,с,Х„,.,Х,0 .CjjXXjj... .Xj Детали доказательства мы опускаем, так как они проверяются непосредственно. В выводе (2) из С выводится цепочка, составленная из букв (2 н Ь, за которой следует ее зеркальное отражение, составленное соответственно из букв Л и В. В выводе (3) нетерминалы А я В перемещаются к правому концу цепочки, где А становится терминалом а, si В становится терминалом Ь, вступая в контакт с нетерминалом D, который действует как правый концевой маркер. Нетерминалы А н В могут превратиться в терминалы единственным способом -только передвинувшись к правому концу цепочки. При этом цепочка, составленная из букв Л и S, будет обращена и совпадет, таким образом, с цепочкой букв а и Ь, выведенной из С в выводе (2). Комбинируя выводы (1) - (3), получаем для пО где с,-{(2, Ь} для 11 п. Итак, {ww\w{a, b}*}L{G). Теперь покажем, что L(G) {wuD\w{a, Ь]*\. Для этого надо показать, что из 5 выводятся только те терминальные цепочки, которые имеют вид ww. Вообще говоря, показать, что грамматика порождает цепочки только данного вида (т. е. что она не может породить других цепочек), гораздо труднее, чем показать, что она может породить все цепочки данного вида. Здесь удобно задать два гомоморфизма g и k, удовлетворяющие условиям g(a) = a, g(b) = b, g{A) = g{B)e h{a) = h ф) =e, h{A) = A, h(B)B Для нашей грамматики G можно показать индукцией по ml, что если S"a, то а можно представить в виде сс.. xUV, где (1) с. для всех /=1,2, ..., п-либо а, либо 6; (2) и-либо С, либо е\ (3) р-такая цепочка из языка {а, Ь, Л, что ёФ) = с,с,...с,, /i(P)X„X„.,...X,,i Ху = Л, если Cj = a, н Х~В, если Cj = b (t</n); (4) I/-либо D, либо е. Детали индукции опускаем. Заметим, что все выводимые цепочки грамматики G, состоящие лишь из терминальных символов, имеют вид сс.. .ссс. -где Ь} для всех t = l,...,n. Таким образом, L(G)s {wwlw {а, b}*}. Наконец, заключаем, что L{G) = {ww\w{a, b}*}, □ 2.1.3. Грамматики с ограиичениями на правила Грамматики можно классифицировать по виду их правил. Пусть G(N, 2, Р, S) -грамматика. Определение. Грамматика G называется (1) прсшолинейной, если каждое правило из Р имеет вид А-хВ или А-х, где Л, В N, л: 2*; (2) контекстно-свободной (или бесконтекстной), если каждое правило из Р имеет вид Л-)-а, где Л N, cx(NU2)*; (3) контекстно-зависимой (или неукорачивающей), если каждое правило из Р имеет вид а-р, где сср. Грамматика, не удовлетворяющая ни одному из указанных ограничений, называется грамматикой общего вида (или без ограничений). Грамматика примера 2.3 праволинейная. Другой пример праволинейной грамматики - грамматика с правилами Эта грамматика порождает язык {О, 1}*. Важным примером контекстно-свободной грамматики служит грамматика примера 2.4. Заметим, что, согласно нашему определению, каждая праволинейная грамматика контекстно-свободная. В примере 2.5 грамматика, очевидно, контекстно-зависимая. Следует подчеркнуть, что определение контекстно-зависимой грамматики не допускает правил вида Л -н-е, обычно называемых е-правилами. Такнм образом, контекстно-свободная грамматика, содержащая е-правила, не является контекстно-зависимой. Запрещение е-правил в контекстно-зависимой грамматике вызвано желанием гарантировать рекурсивность порождаемого ею языка. Иначе говоря, мы хотим иметь алгоритм, который для произвольной контекстно-зависимой грамматики G и входной цепочки W определял бы, принадлежит ли эта цепочка языку L(G) (см. упр. 2.1.18). Если допустить, что среди правил контекстно-зависимой грамматики есть только одно е-правнло (не снимая с грамматики остальных ограничений), то расширенный класс грамматик уже способен порождать все рекурсивно-перечислимые множества (см. упр. 2.1.20). Грамматика примера 2.6 - это грамматика без ограничений. Заметьте, что она не является ни праволинейной, ни контекстно-свободной, ни контекстно-зависимой. Соглашение. Если язык L порождается грамматикой типа х, то L называется языком типа х. Это соглашение относится ко всем „типам х", которые мы уже определили, и к тем, которые еще определим. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 [17] 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 0.0019 |