XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 75
Текст из файла (страница 75)
Правило вывода принято записывать в таком виде: разделяя левую и правую части „стрелкой", которая рассматривается как „метасимвол" и не принадлежит ни одному из алфавитов грамматики. Буквы терминального алфавита грамматики называют тперминальными символами (или просто тперминалами); буквы нетерминального алфавита называют нетперминалъными символами (или нетперминалами). Любую цепочку в терминальном (нетерминальном) алфавите называют тперминальной (нетперминальной) цепочкой. Алфавит У О И называют обьединеннмм алфавитном грамматики С.
Пример 7.3. Четверка бе = На, Ь), (Я, А, В), Я, (Я -+ аАВ6, аА -+ аВ, аВ -+ аВа, аА -+ аа, аВЬ -+ ааЬЬ, аВа -~ аЬВЬа, ВЬ -+ АЬ)) задает грамматику с терминальным алфавитом У = (а, Ь), с нетерминальным алфавитом И = (Я,А,В), с аксиомой Я и множеством правил вывода Р, злементы которого перечислены в фигурных скобках после аксиомы. Обычно ради наглядности правила вывода грамматики выписывают отдельно: Я -+ аАВЬ, аА -+ аВ, аВ -+ аВа, аА -т аа, аВЬ -+ ааЬЬ, аВа -т а6ВЬа, ВЬ -+ АЬ. 474 7. КОНЕЧНЫЕ АВТОМАТЫ И РЕГУЛЯРНЫЕ ЯЗЫКИ Замечание 7.1.
Нам будет удобно условиться о некоторых обозначениях, которыми мы все время будем пользоваться, имея дело с грамматиками. Терминалы будем обозначать малыми латинскими буквами из начала латинского алфавита: а, Ь, с и т.д.; нетерминалы — большими латинскими буквами из начала и середины латинского алфавита: А, В, С, В, Т и т.д.; терминальные цепочки (т.е. слова в терминальном алфавите)— малыми латинскими буквами из середины и конца латинского алфавита: я, 1, р, д, х, у, л и т.д.; цепочки в объединенном алфавите — малыми греческими буквами. Наконец, большими латинскими буквами из конца алфавита будем обозначать символы объединенного алфавита или пустую цепочку. Определение грамматики указывает пока только на то, что следует фиксировать, чтобы задать какую-либо грамматику. А именно следует фиксировать два непересекаюппгхся алфавита, выделив в одном из них символ, названный аксиомой, а также конечное множество правил вывода.
Но мы еще не знаем, каким образом „работает" грамматика как инструмент порождения (и преобразования) слов. Чтобы это понять, нужно определить важнейшее понятие выводимости в данной грамматике. Неформально каждое правило вывода грамматики трактуется как „правило замены", разрешающее произвольное вхождение левой части правила в некоторую цепочку в объединенном алфавите заменить его правой частью, получив (или выведя) тем самым новую цепочку. Так, для примера 7.3 мы можем от цепочки Я, используя правило В-~ аАВЬ, перейти к цепочке аАВЬ. В этой цепочке есть вхождение левой части правил аА -> аВ и аА -> аа, а также левой части правила ВЬ вЂ” ~ АЬ.
Можно использовать любое из них (но какое-нибудь одно!): если мы заменим (в данном случае единственное) вхождение цепочки аА правой частью правила аА -> аВ, то получим цепочку аВВЬ и т.д. Таким образом мы и строим так называемые выводы — последовательности цепочек, в которых каждый последующий член получается из предыдущего заменой, подобной только что рассмотренной. 475 7.2. Порокдаелцие грамматики Определение 7.6..Цепочка б непосредстпвенно выводима в грамматике ст вз цепочки у (или из у непосредственно выводится 6), если существуют такие цепочки о и р и такое правило вывода а -+ р' из Р, что у = пар (т.е. существует вхождение левой части правила вывода в цепочку у), а б = орр. Бинарное ошноитение на множестве цепочек в объединенном алфавите, которое состоит из всех упорядоченных пар (у, 6), таких, что вторая цепочка непосредственно выводится из первой, называют отпношением непосредстпвенной выводимостпи.
Его будем обозначать символом 1-с, опуская зачастую имя грамматики: у ~- б. В этом случае говорят также, что правило а -+,0 применяется к цепочке 7 (и что цепочка б получена применением правила а ~,9 к цепочке у или, что равносильно, в результате замены данного вхождения левой части правила а -+)т его правой частью). В общем случае, если левая часть правила вывода входит в данную цепочку, говорят, что правило применимо к этой цепочке (или имеет место применимостпь правила вывода к цепочке). Если же левая часть правила вывода не входит в цепочку, то говорят, что правило не применимо к данной цепочке. Рефлексивно-иранзиптивное замыкание оптношенил непосредственной выводимости обозначаем ~.с (опять-таки опуская имя грамматики с ',' если зто не приводит к недоразумению: >-') и называем отпношением выводимостпи.
Иначе говоря, выводимостпь цепочки б из цепочки 7, 7 ~-с б, в грамматике 6' имеет место, по определению, тогда и только тогда, когда найдутся такие слова ае = 7, а1, ..., а„= б, где и > О, что ао~"Са1~ С ° ° ° ~ Сао-1~ Сао. Для данной цепочки 7 в объединенном алфавите, если к ней применимо хотя бы одно правило вывода рассматриваемой грамматики, существует в общем случае не одна, а много цепочек, непосредственно выводимых из нее. Эта неоднозначность 476 7. КОНЕЧНЫЕ АВТОМАТЫ И РЕГУЛЯРНЫЕ ЯЗЫКИ связана с двумя факторами.
Во-первых, может существовать несколько разных правил вывода, применимых к цепочке у. Так, для грамматики примера 7.3 к цепочке аАаВЬ применимы все правила грамматики, кроме первого. Тогда любая цепочка, полученная применением к указанной цепочке любого из этих правил, будет непосредственно выводима из нее. Вовторых, если уже фиксировано правило вывода, применимое к цепочке у, то существуют, вообще говоря, несколько различных вхождений левой части этого правила в цепочку у. Тогда любая цепочка, полученная заменой любого из этих вхождений правой частью выбранного правила вывода, будет непосредственно выводима из у. Для грамматики примера 7.3, правила аВ -+ Ва и цепочки 7 = БаВаВа получим: БаВаВа 1- 6ВааВа и 6аВаВа )- ЬаВВаа. Разные вхождения левой части некоторого правила в заданную цепочку могут и пересекаться.
Так, правило аВа -+ 6ВЬ грамматики примера 7.3 можно к написанному выше слову у применить двояко: ЬаВаВа ~- ЬЬВЬВа и ЬаВаВа ~- ЬаВЬВЬ. Заметим, наконец, что множество цепочек, непосредственно выводимых иэ данной, пусто тогда и только тогда, когда среди правил вывода грамматики нет ни одного, применимого к данной цепочке. Для примера 7.3 в качестве такой цепочки можно взять хотя бы цепочку аВА. Определение 7.7. Выводом в эрамматиие С называют произвольную, конечную или бесконечную, последовательность слов ае, ам ..., а„, ..., в которой для любого й ) )О ол 1- а;~м если цепочка а;~.1 существует. Число и > О называют длиной вывода, если указанная последовательность конечна и а„— ее последний элемент.
В этом случае говорят также, что а„ выводится иэ ае за и шагов. Для положительного и пишем ае 1-+ а„или, если нужно специально оговорить длину вывода С~с ~ С~я ° Из определений следует, что выводимость 7 ~' 6 равносильна тому, что существует вывод 7 = ао,а1,..., ая — — б, где и > О. т.л Порождающие грамматаии 477 Мы будем использовать также термин „дтрагментп вывода", понимая под этим такую подпоследовательность вывода, которая сама является выводом. В частности, фрагмент вывода, состоящий из двух соседних его членов, называется шагом вывода. Построение вывода в порождающей грамматике можно трактовать как „игру", правила которой заданы множеством Р. Подобно тому как в игре (например, в шахматах) можно из заданной позиции перейти в одну из множества следующих позиций, используя правила игры, так и при проведении вывода в грамматике можно из данной цепочки получить одну из множества непосредственно выводимых из нее, заменяя в ней произвольное вхождение левой части правила его правой частью.
При этом мы можем выбрать любое правило, применимое к очередной цепочке, и среди различных вхождений его левой части выбрать любое. На основании сказанного можно предположить, что существуют несколько различных выводов фиксированной цепочки т3 из фиксированной цепочки а. Далее на примерах мы убедимся в том, что это действительно так. Введенные вьппе понятия непосредственной выводимости, выводимости и вывода можно уподобить известным из теории графов понятиям непосредстпвенной досптижимости, достпижимостии и путав ~в ориентированных графах) соответственно.
Мы специально выбирали обозначения выводимости близкими к тем, которые используют в теории графов. Нужно только заметить, что множество вершин графа конечно (по крайней мере, мы в этой книге изучаем только конечные графы), а множество слов бесконечно. Но графовзя аналогия позволяет придать введеным вьппе понятиям большую наглядность: так, построение вывода в грамматике можно уподобить „путешествию" по не которому пути в ориентированном графе. Центральным понятием в теории порождающих грамматик является понятие языка, порождаемого данной грамматикой. 478 7. КОНЕЧНЫЕ АВТОМАТЫ И РЕГУЛЯРНЫЕ ЯЗЫКИ Определение 7.8. Язык, порождаемый зрамматпикой с', — это множество Ь(0) всех выводимых из аксиомы грамматики шерманальных цепочек: ЦС) = (х: Я «-о х,х Е У'). Продолжал „игровую аналогию", мы можем теперь сказать, что у „игры", во-первых, появилась выделенная „начальная позиция", аксиома; во-вторых, возникла „цель" — строя вывод в согласии с правилами грамматики, получить цепочку, не содержащую нетерминалов.
Так, скажем, и в шахматах, мы начинаем игру не с произвольной позиции, а со вполне определенной начальной позиции, предусматривающей строго фиксированную расстановку фигур, а закончить игру стремимся в любой позиции, в которой вражескому королю поставлен мат. Но при этом нужно понимать, что правила вывода грамматики априори никак не связаны с ограничением строить выводы терминальных цепочек иэ аксиомы, а определяют возможность построения любого вывода, даже бесконечного.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
