XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 103
Текст из файла (страница 103)
Букве а алфавита У сопоставим алфавит Ув = (О, Ц, выбрав в качестве языка Ьв множество (О"1")и > О. Букве Ь Е У сопоставим алфавит Уь = (а) и в в2 этом алфавите — язык Ь| = (а":и > 0). Наконец, букве с алфавита У сопоставим алфавит Ус = (а,б,с) = У и в качестве языка Ьс возьмем язык Ь, пополненный пустой цепочкой, т.е. Х с = (а"Ьис": и > 0). Возьмем цепочку ааЬЬсс е Ь и первый символ а заменим цепочкой 0011 Е Ьв, второй символ а — цепочкой 01 Е Ьв, первый символ Ь вЂ” цепочкой от~~ е Ье (при и = 27), второй символ Ь вЂ” пустой цепочкой, первый символ с — пустой цепочкой, второй символ — цепочкой аЬс е Ьс.
В результате получим следующую цепочку, принадлежащую суперпозиции 656 8. КОНТЕКСТНО- СВОБОДНЫЕ ЯЗЫКИ Б(Б11'ю|Бь~~с). 001101а™9аЬс=001101 аа...а аЬс. 729 раз Проделывая аналогичные действия с любой другой цепочкой языка Ь или же производя другие замены символов той же самой цепочки, будем получать все новые цепочки определенной выше суперпозиции. В данном случае будем иметь А Е $(й>Ъ~,Ъ|,Ь,), так как каждый из языков Ба, Ь| и Бс содержит пустую цепочку.
Пример 8.19. Пусть алфавит У есть русский алфавит (А, Б, ..., Э,Ю, Я1, а язык Ь вЂ” множество всех слов русского языка. Каждой букве русского алфавита сопоставим язык, состоящий из единственной однобуквенной цепочки а, которая стоит рядом с указанной русской буквой на клавиатуре компьютера. Так, Ьл = Щ, ББ = (<1 и т.д. Все зти языки можно считать языками в латинском алфавите, дополненном определенными специальными символами, такими, как (, ], (, ), <, > и т.п.
Тогда, если мы в качестве исходной цепочки языка Х возьмем слово У ЧЕБНИК, то получим такую цепочку в супеРпоэиции Б(Ь,Ьл,...,Ья): ЕХТ <УВЯ. Разобранные примеры показывают, что суперпозицию можно рассматривать как своего рода „кодирование" цепочек языка Ь с заменой в них каждой буквы цепочкой другого языка. Действительно, такая замена является одним из простейших способов „шифровки" текстов. Замечание 8.11. Суперпозицию можно определить через соошеешсшвие. Введем соответствие о' С У х (Ь„0... ОЬ „) так, что для каждого 1 = 1, и упорядоченная пара (а;, р) принадлежит и тогда и только тогда, когда у Е Б,.
В этом случае Ят„Ь.„...,Ь ) = Ц а(х(1))...п(х(Ь)) и((Л) ПЬ), яеС,ЧЛ) где х = х(1)... х(й). В.5. Аагебравчесвне свойства КС-ваывов 657 В терминах суперпозиции могут быть представлены и такие операции над языками как объединение, соединение и итерация. Объединение. Пусть 11 и г.г — два произвольных языка в каком-то алфавите ее'. Возьмем произвольный двухбуквенный алфавит т = (а, Ь) и язык г зададим как г, = У (т.е. юык Ь состоит из двух однобуквенных цепочек а и Ь). Рассмотрим суперпозицию$(й,й„,г.ь), где г' =Ам Ьь =г г. Докажем, что эта суперпозиция совпадает с объединением г 1 0 а г. Действительно, если мы возьмем цепочку а Е г, то ее единственную букву мы можем, согласно определению суперпозиции, заменить любой цепочкой языка Ь1.
Точно так же, строя суперпозицию, вместо цепочки Ь Е г. получим все цепочки юыка Хг. Итак, е 10Ьг =$((а, Ь),т'мг'г). Соединение. Снова фиксируем произвольно в произвольном алфавите тт' языки г.1 и г.г. Опять-таки проювольно выберем двухбуквенный алфавит 1,а, Ь), определив язык е = (аЬ). Положим, как и вьппе, т', =.с.м т'а = а.г. Тогда суперпозиция $(й,йа,уь) =$ЯаЬ),й„йь) совпадет с соединением й1йг. В самом деле, символ а единственной цепочки аЬ язьпса Ь можно при построении суперпозиции заменять любой цепочкой языка т:м а символ Ь вЂ” любой цепочкой языка г.г.
В результате записанная вьппе суперпозиция совпадет с множеством всех цепочек, представимых как соединение хр, где х е Ьм у е г г. Но зто и есть соединение г.1т' г. Итак, а1аг =$((аЬ) ЬмЬг). Итерация. Рассуждая аналогично, можно показать, что итерация г.' языка г. равна = $(а,т ), 658 В.
КОНТЕКСТНО-СВОБОДНЫЕ ЯЗЫКИ а позитивная итерация х,+ = б(а+,Ь) (для любых алфавита Ж, языка Х С 1т" и однобуквенного алфавита У = (а)). Основное свойство суперпозиции применительно к КС-языкам выражает следующая важная теорема. Теорема 8.9. Если языки Ь„., 1= 1,п, контекстно-свободные, язык Ь также контекстно-свободный, то суперпозиция о(Ь,Ью,...,Ь „) есть КС-язык. < Пусть У = (а1,...,ао) и каждыи язык Ь„., в = 1, н, задается КС-грамматикой Св,.
= (У ., Ф ., о' ., Р .), а язык Ь задается КС-грамматикой с = (У, Ф, о, Р). Без ограничения общности можно предполагать, что нетерминэльные алфавиты всех указанных грамматик попарно не пересекаются (так как всегда можно провести нроиедуру переименования нетерминалов любой грамматики). Построим следующую грамматику: где У'=~„0...0Рв„, Ф'=МОИ„,0...0Ф,„, Р'= Р„,0...0 0Р „0(А-+а'. для любого правила А-+а в Р). Здесь цепочка а~ получается из цепочки а следующим образом: все нетерминвлы в а остаются без изменений, а каждое вхождение каждого терминала Ь Е У, т.е. Ь = а; для некоторого 1 = 1, и, заменяется аксиомой Яв грамматики Св (заметим, что, согласно этим правилам замены, для любых цепочек а, 13 в объединенном алфавите грамматики 6' (а~3)' = а~,У и Л' = Л). Неформально система правил Р' получается объединением всех множеств правил грамматик 6в,. и добавлением „перекрашенных" правил грамматики С.
„Перекрашивание" выражается в том, что каждый терминал а; грамматики С заменяется 8.8. Алгебраические свойства КС-клыков 659 аксиомой Яа,, грамматики С „ а нетерминалы остаются в неприкосновенности. В частности, для любой цепочки «3 Е № имеет место,У =,О. Докажем теперь, что грамматика 6», контекстно-свободная по построению, является искомой, т.е.
она порождает суперпозицию о(с.,Ьа1,...,Ье„). Прежде всего докажем, что для проювольных нетерминала А Е д«и цепочки у Е (У 0 Ф)' из А ~~ у следует А «-~, у', т.е. если в грамматике 6' ю нетерминзла А выводится цепочка у в объединенном алфавите, то в грамматике 6е из того же не- терминала А выводится „двойник" цепочки у, получаемый из последней заменой каждого ее терминального символа Ь аксиомой соответствующей грамматики 6е = 6,.
для некоторого 1=1,п. Доказательство проведем индукцией по длине 1 вывода цепочки у из нетерминала А. Для вывода нулевой длины утверждение тривиально, так как А «.е А = А'. Пусть утверждение доказано при всех 1 < тп — 1, и пусть А ~~~ у. Тогда существует цепочка с, такая, что А «-~~ 1 с «-с у. Согласно предположению индукции, отсюда следует, что А «-~, (', а так как с «-о у, то существует такое правило вывода В -+ Д в множестве Р, что с = ~1Всз (для некоторых см сз е (Уо~~~)" ) и у = «Щз. Следовательно, с' = ЦВЦ, а так как в множестве правил вывода Р' есть правило В -««у, то с' «-с ф3'Ц = у'. Итак, окончательно получаем А «-~, (' «-ог у'.
Из доказанного следует, что для любой цепочки х Е Ь = = Ц6), т.е. такой цепочки х, что Я «-~ х, выполняется Я «-~, х'. Если х=Л, то тогда из ЛеЬ следует, что ЛеЬ(6е). Если х~ Л, тогда для некоторого й > 0 х = х(1)...х(к) и х' = Я О)...Я <ьр а так как для каждого у = 1, и выполняется Я ОО ~~, 91, какова бы ни была цепочка у Е е щ, то х' «-~, у1.~.уь. Но последняя цепочка есть проювольная цепочка суперпозиции 8(Ыа„...,Ье„) (не считая пустой цепочки, непосредственно выводимой ю аксиомы Я), так как она получена из проювольной непустой цепочки х юыка Ь путем замены в ней каждого 660 К КОНТЕКСТНО-СВОБОДНЫЕ НЗЫКИ символа х(у) произвольной цепочкой языка Ь ~д. Поскольку нз Я «О Л следует Я «6 Л, любая цепочка суперпозиции 8(Ь, Ь„,..., Ь, ) порождается грамматикой С'.
Докажем теперь, что если цепочка ю в алфавите У' (терминальном алфавите грамматики С') выводится из аксиомы Я в грамматике С', то она принадлежит суперпозиции 8(Ь,Ь,ц,...,Ь „). Для этого сначала докажем, что для любых нетерминала А е Ф и цепочки у Е (У 0 Ф)" нз А «о, у' следует А«д у. Опять воспользуемся индукцией по длине вывода, но на этот раз вывода цепочки у' из нетерминала А в грамматике С'. Случай вывода нулевой длины, как и вьппе, тривиален. Пусть для некоторого гп > 0 выполняется А «$ у'. Тогда существует такая цепочка р, что А «~~, 1 р «с у'. Каждый символ цепочки у' есть либо одна из аксиом Я...
1 = 1, п, либо нетерминал из М. Так как КС-грамматики С и Сио 1 = 1, н, в силу результатов, полученных в 8.2, можно считать заданными в приведенной форме, то правые части правил вывода каждой из рассматриваемых грамматик не содержат аксиомы. Кроме того, нетерминвльные алфавиты Ф и Ф,. всех этих грамматик попарно не пересекаютсл. Отсюда следует, что цепочка у' не может быть непосредственно выведена из цепочки р применением какого-либо правила из множества Р ., т.е. какого-либо правила вывода грамматики С ., а выводится нз р применением некоторого правила вида В + ~У, построенного, как указано в определении грамматики С', по правилу В -+,8 системы правил грамматики С. Тогда мы можем написать: у' = у(р'у~ (для некоторых цепочек у1 и 'уз в алфавите У 0 Ф), р = у~1Вуз — — (у1Вуз)'.
Это значит, что,и =Е при с ='у~В7з, т.е. А«~~, 1Е. Согласно предположению индукции, отсюда следует, что А «~ ~, а так как ~ = 'у~В 1г и в множестве правил вывода грамматики С содержится правило В -+ ~3, то 4 «а уцУуз = у и окончательно А «д ч. В частности, отсюда следует, что для произвольной цепочки х Е У', такой, что Я «о, х', имеет место Я «~ х, т.е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
