XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 104
Текст из файла (страница 104)
х Е Ь. 8.о. Аегебраичесвие свойства КС-замков 661 Теперь докажем, что произвольная цепочка а, выводимая в грамматике С' из аксиомы Я, имеет вид а|аз... сьа (еп ) 1), где для каждого у =1, ш цепочка а либо пуста, либо для некоторого символа Ь е У выводится из аксиомы Я~,, грамматики Се,, т.е. Яе,. ~-й„сеу, либо является некоторой цепочкой нетерминалов иэ М. Действительно, сама аксиома Я удовлетворяет этому требованию. Далее, пусть доказываемое справедливо для любой цепочки, выводимой в С' за любое число шагов, не превьппающее 1 — 1 для некоторого 1 > 1. Предположим, что Я 1-~о, а. Тогда, как это мы уже делали в аналогичных ситуациях, рассмотрим последний шаг этого вывода, т.е.
для некоторой цепочки 7 будем иметь Согласно предположению индукции, цепочка 7 представима в виде 7 =7172" Ъа> где 7, = Л, у = 11еп, или Яе,. 1-~, 71 для некоторого Ь Е У, или 7 Е №. Так как к цепочке 7 применяется некоторое правило грамматики С' (на последнем шаге вывода цепочки се иэ аксиомы Я), то в 7 входит по крайней мере один нетерминал грамматики С'. Если это есть некоторый символ А Е Ф, то он может входить только в оДнУ из таких подцепочек 7е, которая состоит иэ нетерминалов алфавита Ф.
После замены А посредством некоторого правила вида А + ф', соответствующего правилу А ~ ~9 грамматики 6', получится цепочка, в которую могут входить только нетерминэлы множества М и аксиомы Яе грамматик бе для каких-либо Ь Е У. Следовательно, если цепочка се на последнем шаге ее вывода иэ аксиомы получена применением некоторого правила А -+,У, то она также может быть представлена соединением цепочек такого же вида, что и цепочки 7 . 662 б. КОНТЕКСТНО-СВОБОДНЫЕ ЯЗЫКИ Если же оь. ~-~ уу для некоторого Ь.
Е У и на указанном Ю Ьу шаге применяется правило из множества Рь,, то оно, ввиду того что все множества Ф и Фь (для различных Ь Е У) попарно не пересекаются, может быть применено только к такой подце- ПОЧКЕ У, КОтОРан ВЫВОДИТСЯ ИЗ аКСИОМЫ ОЬГч И тОГДа В ЦЕПОЧКЕ сг полУчим поДЦепочкУ, опЯть-таки вывоДимУю из оЬу, т.е. и в этом случае' цепочка сг образуется соединением подцепочек того же вида, что и цепочки уу. Пусть теперь цепочка ю Е У'* такова, что з Ь-~„е. Если ю = Л и Б ~О~ Л, то зто означает наличие правила вывода Я-г Л в множестве Р' и, следовательно, в множестве Р, т.е. Л ц л.
и Л ц 8(л.,л.а„...,Ьа„). Таким образом в этом случае пустая цепочка, порождаемая грамматикой С', действительно принадлежит указанной суперпозиции. Иначе в силу доказанного выше свойства любой цепочки, выводимой в грамматике С' из аксиомы, цепочка ш, не содержащая по условию вхождений нетерминалов из Ф, допускает представление в виде ю1ю2... юь где для каждого у = 1, Й имеет место выводимость Бьу Ь-О, и~у (возможно для некоторых у, что шу — — Л; в частности, может оказаться, что и ю = Л).
Таким образом, о г а' 'зЬ1~Ьз'''ОЬь Ь С' Ш1Ю2 ° ° .ЮЬ~ где для каждого у = 1, Й цепочка 1о; принадлежит языку л.ь, Так как при этом о ~с Ь1Ь2...Ьь, т.е. Ь1Ь2...Ьь Е л, то и Е Е 8(с.,л.~„...,л. „). Итак, доказав, что любая цепочка ш в терминальном алфавите У' грамматики 6', выводимая из аксиомы, есть элемент 'Заметим, что в приведенном выше доказательстве существенно используетсл тот факт, что нетерминальиые алфавиты № №„..., №„попарно не пересекаютсл. Если бы зто было не так, то в некоторой подцепочке уе, выводимой иэ аксиомы Бь,.
дли некоторого Ьу б У, мы могли бы заменить вхождение нетермннала иэ №, применив правило вывода „чужой" грамматики О,ь, аь;Ь Ь;, и получить в составе цепочки а подцепочку, ие выводимую ни вэ одной „дочерней" аксиомы Бь, Ь Е У. 8.5. Алгелрав чесвве свойства КС-лвьпсов 663 суперпозиции о (Ь, Ьеы..., Ьа„), мы тем самым завершили дока- зательство теоремы. ° Следствие 8.3. Семейство КС-языков замкнуто относительно операций объединения, соединения, итерации и позитивной итерации. ~ Доказательство получается немедленно из приведенных вьппе определений операций объединения, соединения, итерации и позитивной итерации как частных случаев суперпозиции.
Ь Заметим, что объединение бесконечного семейства КС-языков не является, вообще говоря, КС-языком. Так, язык с восо в. ~~ 0) не являющийся КС-языком (см. 8.3), может быть представлен в виде объединения счетного семейства, каждый элемент которого есть язык (авЬвсв) для фиксированного натурального и, т.е. язык, состоящий ю одной цепочки, а следовательно, регулярный и контекстно- свободный. ~м1> 8е<и У1 Уе Рис. 8.84 Замечание 8.12. Вывод цепочки тс из суперпозиции о(Ь,Ь„,...,Ье„) (если она не является пустой цепочкой, непосредственно выводимой из аксиомы Я) в грамматике С', построенной в доказательстве теоремы 8.9, можно провести по „двухуровневой" схеме, приведенной на рис.
8.34. Сначала порождаем, используя „перекрашенные" правила грамматики С, т.е. правила вида А -~ у' для А е Ф и у е (У 0 Ф)', „двойника" произвольной цепочки я е Х,, т.е. цепочку Я 0)... Я сар Из нее затем, используя правила „дочерних" грамматик, порождаем самУ цепочкУ и, из каждой аксиомы Яе(3 выводЯ некотоРУю цепочку уу так, что то = у1... уь. Пример 8.20.
Рассмотрим конструкцию ю доказательства теоремы 8.9 на конкретном примере. 664 В. КОНТЕКСТНО-СВОБОДНЫЕ ЯЗЫКИ Язык 1 определим как язык, порождаемый грамматикой С со следующим множеством правил вывода: Я -+ аЬ | аЯЬ! ЯЯ. Языки Ь и Ьь определим так: Ь.=СО"1":п>О), Йь = (к: к Е (а, Ь) и х = к ) (т.е. Ьь есть язык палиндромов в алфавите (а, Ь1). Запишем множества правил вывода грамматик Са и Сь, порождающих языки Ьв и Ьь соответственно: Я -+ ОЯ1|01| Л (грамматика Ся) и Я-+ аЯа|ЬЯЬ|аа|ЬЬ|а|Ь|Л С'= Ц0,1,а,Ь1, 1Я,Т,Я Т Яь ТьЪ Я, Р'), порождающей супернозицию Я(Ь, Ьв, Ьь): Я- Я,Я |Я,ТЯ |ТТ, Т-+ Я.Я,|Я.ТЯ,|ТТ, Я„ -+ ОТ,1|01|Л, ~а ь О~ю1 |01з Яь ~аТьа|ЬТьЬ|аа|ЬЬ!а|Ь|0|Л, Ть — > аТьа | ЬТьЬ | аа | ЬЬ | а | Ь | О.
(8.19) (грамматика Сь). Преобразуя грамматики С, С„ и Сь к приведенной форме (убирая аксиому из правых частей правил вывода) и переименовывая нетерминалы так, чтобы множества Ж, Фя и Пь попарно не пересекались, построим, как описано в доказательстве теоремы 8.9, множество Р' правил вывода грамматики В.б. Алгебраическое свойства КС-языков 665 Рассмотрим дерево вывода цепочки 010011аЬаЬ,изображенное на рис. 8.35. Если при порождении этой цепочки использовать „двухуровневую" схему, описанную в замечании 8.12, то получим такой вывод: $1 ЯаТЯь~-$ Я ЯЬЯь| 01$аБЬБь1 ~ 010Т 1$ьЯь ~ 010011$ЬБь Р 010011аТьаБЬ ~ ~ 010011аЬаЯь |- 010011аЬаЬ. Сначала порождается „двойник" цепочки аЬа место первого символа (замененного аксиомой Яа „дочерней" грамматики Са) подставляется цепочка 01, на место второго символа — цепочка 0011, на место третьего— аЬа,на место четвертого — цепочка Ь.
Заметим, что в общем случае построения вывода в грамматике С' (если не обязательно придерживаться „двухуровневой" стратегии) едочерняяк грамматика может начать еработать",как только в выводе появляется ее аксиома. Так,по изображенному на рис. 8.35 дереву вывода может быть построен следующий левый вывод: Ь е Ь, а затем на О Т, 1 а Ть а О 1 Ь Рис.
8.88 $1- БвТБь ~ 01БеБьБь ~ 010Те1$ьЯь1 ~ 010011$ьБь Ь. 0100ПаТьаЯь ~- ~ 010011аЬаЯЬ 1- 010011аЬаЬ. Я 1- Б„Т$ь 1- 01Т$ь ~ 01ЬЬЯь ~ 0166а. Но если мы пренебрежем требованием, чтобы нетерминальные алфавиты грамматик С, С„и Сь попарно не пересекались, и отождествим, скажем, нетерминалы Т„, Ть и Т, положив Т = Ть = Т, то сможем вывести цепочку, не принадлежащую суперпозиции $(ы, Ьа,.5ь). Например, 666 8. КОНТЕКСТНО-СВОБОДНЫЕ ЯЗЫКИ В самом деле, цепочка 01 может быть получена применением либо правила о -+ 01, либо правила Т„-+ 01; цепочка 66— применением правила Ть ~ ЬЬ или Яь -+ ЬЬ, цепочка а — применением правила Яь -+ а или Ть — > а.
Можно легко убедитьсл в том, что в этом случае единственная цепочка, состоящзл иэ аксиом „дочерних" грамматик, т.е. символов Я~, Ям иэ которой может быть выведена цепочка 0166а, равна Я„ЯьЯь. Но зта цепочка не выводима из аксиомы о. Если же мы, анализируя цепочку 0166а, стали бы рассматривать в качестве правой части правила вывода не цепочку 66, а цепочку Ь, то получили бы подцепочку Ьа, не являющуюся правой частью ни одного правила вывода, и тогда имели бы БвБьЬа — цепочку, не выводимую иэ Ь'.
Мы вывели „плохую" цепочку здесь потому, что „перепутав" нетерминалы грамматик, позволили „вклиниться" „дочерней" грамматике Сь в работу грамматики „верхнего уровня". Аналогично можно построить пример, когда разные „дочерние" грамматики „мешают" друг другу. Итак, требование, согласно которому нетерминальные алфавиты грамматик С и всех С . попарно не пересекаются, является существенным.
ф Исследуем теперь вопрос о пересечении КС-языков. Введем обозначение: если дан алфавит (Ьм..., 6|~, то через ]Ьв~ ...Ьь] обозначим язык (Ьв~ ... Ь~", и ) 01. Теорема 8.10. Класс КС-языков не замкнут относительно пересечения. ~ Языки а*]6"с"] и ]а"6"]с', как можно легко доказать, являются КС-языками, но их пересечение есть язык ]а"Ь"с"], который — как это было доказано в примере 8.11 — не КС-язык.
~в Следствие 8.4. Дополнение КС-языка в общем случае не является КС-языком. < Действительно, если бы для любого КС-языка Ь его дополнение Х бь|ло бы КС-языком, то для пересечения любых двух 8оь Авгебракческке свойства КС-вэыков 667 КС-лзыков Ь| и Ьз мы имели бы: Ь| ОЬз = Ь| 0Ьз — КС-язык, что противоречит теореме 8.10.
~ Однако оказывается, что класс КС-лзыков замкнут относительно операции суженного пересечекил лзыиов — опера ции пересечении с регулярными лзыками. Теорема 8.11. Если Ь вЂ” КС-язык, а  — регулярный лзык, то Ь П В вЂ” КС-язык. ~ Пусть С = (К Ф, Я, Р) — КС-грамматика, порождающал язык Ь, а М = (Я, У, до, Р, о) — конечный автомат, допускающий язык В (см. 7.5). Будем считать, что грамматика С дана в приведенной форме, причем аксиома не содержится в правых частлх правил вывода (см. 8.2).
Конечный же автомат М являетсл детерминированным. Б основе конструкции грамматики длл пересечения Ь П В лежит следующзл неформальная идея. Мы хотим построить такую КС-грамматику се, которая порождала бы все цепочки, одновременно порождаемые грамматикой С и допускаемые конечным автоматом М. Это значит, что любая цепочка х, порождаемая грамматикой С', должна удовлетворять двум требованилм: 1) Я 1-~ х и 2) в М должен найтись единственный путь из начального состоянии в одно из заключительных состолний, на котором читается цепочка х. Если цепочка х пустая, то она принадлежит пересечению Ь П В тогда и только тогда, когда в Р есть правило Я вЂ” ~ Л, а начальное состолние автомата М валяется и заключительным.
Для непустой цепочки х = х(1) х(2)... х(к) из пересечения Ь П В тогда должна существовать единственны последовательность состолний до, ем ..., ва и дс (ду Е Р) множества Я, в которой до -+ .00 вм Будем тогда в качестве нетерминалов грамматики С' рассматривать всевозможные упорядоченные тройки вида (от], 668 8. КОНТЕКСТНО-СВОБОДНЫЕ ЯЗЫКИ где д, г — состояния конечного автомата М, а Х вЂ” символ нэ объединенного алфавита грамматики С (похожий прием мы применяли, строя КС-грамматику, эквивалентную заданому МП-автомату, см. 8.4). Заставим грамматику С' вьпюдить из аксиомы все непустые цепочки вида [цех(1)в1][в1х(2)зэ]... [зз 1х(й)ду] для всех Е б Р и всех последовательностей вм вг, ..., вь 1 состояний из Я при условии, что о 1-с х(1)х(2)...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
