XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 112
Текст из файла (страница 112)
Для этого заметим, что понятие пути в мультпиграфе слегка отличается от такового в обычном ориентированном графе. Под путем в мультиграфе понимается произвольная последовательность дуг е1, е2, ..., е„, ..., где и > 1, такал, что любая пара соседних дуг е;, еьь1 этой последовательности смежна, т.е. существует вершина 0;+1, в которую дуга е; заходит и из которой дуга егь1 выходит. Число дуг в пути (для конечного пути) назовем его длиной.
Пути в мульти- графе будем записывать как цепочки в алфавите Е: так, запись е1е~~ез обозначает путь, являющийся последовательностью дуг Е1 Е2~ ...~Е2~ЕЗ~ .. ЕЗ т раз н раз Тогда магазинная метка дуги (т.е. пути длины 1) с меткой (Я, а, у) есть цепочка у; магазинная метка пути е1, е2, ..., е„ длины и при условии, что магазинная метка пути е1, е2, ..., е„ 1, служащего началом исходного пути, определена и равна Д.8.8.
Гдеафовое представлеппе МП-автоматов 713 у, а дуга е„имеет метку (У, Ь, а), равна а(У д 7). Напомним, что для произвольных алфавита ЬУ, его буквы а и цепочки г в алфавите $У выражение а дг означает цепочку у, такую, что ау = х, и не определено, если первая буква цепочки х отлична от а (см. задачу 7.23). Таким образом, магазинная метка пути в мультиграфе, представляющем МП-автомат, может быть не определена. Введем операцию У-сефеплемдая леагаэпнееыг меетдоде двух смежных дуг ед и ез с метками (ед, а, у) и (У, Ь, а) соответственно, полагая 'у Эк а = аУ д7 (рис.
8.41). Средние компоненты меток дуг МП-автомата будем называть их входееыми аеетпкалеи. Вход- оат УЬа ная метка пути в мультиграфе абра- о т р эуется стандартно из входных меток Рис. 8.41 дуг, как в конечном автомате. Рассмотрим в качестве примера МП-автомат для языка д д = (а"Ь": п ) 0). Его система команд имеет следующий вид: Чоаг -+ 7оаг, доаа ~ доаа, д1оЬа -д ддд Л, адьо- ~дЛ, д1дЛЯ ~ дэЛ. По этой системе команд строим мультнграф (рис. 8.42 ).
Рис. 8.42 Ясно, что дуга с меткой (е, а, ае ) не может быть сцеплена сама с собой, так как выражение ае Ээ ае = ао(Я даЯ) не 714 8. КОНТЕКСТНО-СВОБОДНЫЕ ЯЗЫКИ определено. Но верхняя петля в начальной вершине может сцепиться с нижней, а последняя сцепляется сама с собой. Например, айте оа=аа(а 1аЯ) =ааЯ, аале Х„аа = аа(а 1ааЯ) = аааЯ. Неформально любой путь е1е~ 1 соответствует переписыванию с ленты в магазин и символов а. Тогда путь е1ез-~евер-~ез имеет входную метку а"Ь" и магазинную метку Л.
Так, для цепочки ааа666 будем иметь последовательность сцеплений: ((((((айте аа) Э аа) Э Л) Э Л) Э Л) Эя Л) = =(и( гэ.л)э.л)э.л)э л)=гэ л=л. Если в цепочке больше символов а, чем Ь, то мы, вычисляя магазинную метку соответствующего пути, придем к выражению а Эг Л, которое не определено. Если же в цепочке больше символов Ь, чем а, то мы не попадем в заключительную вершину, так как в нашем мультиграфе нет дуги с меткой, первая компонента которой равна Я, а вторал — 6. Обратим внимание на то, что если мы забудем о магазинных метках и будем рассматривать наш мультиграф как граф обычного конечного автомата, то получим регулярное выражение а'6+. Таким образом, вычисление магазинных меток вдоль путей мультиграфа фильтрует множество входных цепочек, допускаемых МП-автоматом, т.е.
в регуллриом лэыне выделяется подмножество более сложной структуры — некоторый КС-лэмк. Любая дуга, исходящая из начальной вершины и имеющая метку (Яе, а, у) для произвольных а Е Ъ' 0 (Л) и 'у Е Г', называется ствартовой. Тогда нетрудно дать графовую интерпретацию языка МП-автомата. Теорема 8.15. Язык МП-автомата — зто множество всех входных цепочек, являющихся в представляющем МП-автомат 715 Вопросы и эадвои мультиграфе входными метками путей, первая дуга которых стартовая, последняя заходит в заключительное состояние, а магазинная метка равна пустой цепочке.
Вопросы и задачи 8.1. Однозначна ли грамматика с системой правил Я-+ аЯа~ЬЯЬ|аа~ЬЬ|а)Ь|Л? Какой язык она порождает? Преобразовать ее к эквивалентной однозначной грамматике в приведенной форме. 8.2. Какой язык порождает грамматика с системой правил Я ~ ЬЯЯ~а? 8.3. Доказать, что каждый КС-язык может порождаться грамматикой С = (К Л, Я, Р), в которой каждое правило имеет вид А ~а или А +ы, где А Е Ф, або+, ю Е У'. 8.4. Построить КС-грамматику, порождающую язык (а"Ь~: и Фпэ, в, тп) О). 8.6.
Построить КС-грамматику с терминальным алфавитом У, порождающую все цепочки, содержащие вхождения некоторых слов из заданного конечного множества непустых слов в У. 8.8. Найти приведенную форму КС-грамматик: а) Я -~ а ) А, В + Ь, А-~АВ, С-~Яа~Л; б) Я~А~В, С-+Я~а~Л, А-+С~.0, Р-+Я~6,  — ~ХЭ~Е, Е->Я~с~Л; в) Я-+А~В, А-+аВ~ЬЯ~Ь|Л, В-+ АЗ)Ва, С-~ АЯ~Ь~Л; 716 8. КОНТЕКСТНО-СВОБОДНЫЕ ЯЗЫКИ г) В -~ аВ | ЬА | сС, А -+ сВБ | ЬА | С | Ь | Л, В-+ ЬоА|сСЬ! Я, С-» СИ|аСа; д) Я-+АВС|аА|ЬВ|Л, А-~В|Л|аВ|Ь, В-+С|ЬА|а, С-+В|ЬВ|Л; е) В-+ АВ|а|Ь, А — ~ В |Л|аЯ, В -+ В | Ь! аА.
8.7. Доказать, что любой КС-язык в однобуквенном алфавите регулярен. 8.8. Можно ли множество всех КС-грамматик с заданными алфавитами Ъ' и У описать посредством некоторой КС-грамматики? Какими будут алфавиты этой грамматики? 8.9. Построить грамматику, порождающую язык (а~: п>0) для фиксированной натуральной константы Ь. Является ли этот язык контекстно-свободным? 8.10.
Доказать, что каждый линейный язык, не содержащий пустой цепочки, порождается грамматикой, все правила которой имеют вид А -+ аВ, А — ~ Ва, А -~ а. 8.11. Доказать, что любая КС-грамматика может быть преобразована к эквивалентной КС-грамматике С = (К Ф, Я, Р), каждое правило которой имеет вид А -+ ВС или А -+ а, где А, В, С е Ф, а е У О(Л?. (КС-грамматику с такими ограничениями на правила вывода называют КС-грамматикой, заданной в нормальной форме Хомского.) 8.12. Доказать следующую лемму о разрастании для линейных языков. Если Ь вЂ” линейный язык, то найдется такая константа р, что если л Е .о и |л| > р, то з = иеюхр, где |паху| ( р, ех ф Л и (Чп > О) ие"юх"р Е Ь.
717 Вопросы и задачи Используя полученный результат, доказать, что язык правильных скобочных структур не является линейным. 8.13. Найти КС-грамматику, порождающую языки: а) 1а"Ььс": й,п>0); б) 1а"Ь"сс: й,п>0). 8.14. Доказать, что множество всех цепочек, которые могут появляться в магазине МП-автомата, регулярно. У к а з а н и е: использовать графовое представление МП-автомата (см. Д.8.3). 8.15. Построить МП-автомат, допускающий язык (а"Ь: й у~ и). 8.16. Построить МП-автомат и КС-грамматику для языка в алфавите (а, Ь), состоящего из всех таких цепочек, что в них число символов а совпадает с числом символов Ь.
8.17. Показать, что грамматика, заданная системой правил Я~А)В, А-+аАЬ~аЬ, В-+а ВЬ|аВЬ ~а Ь!оЬЬ неоднозначна. Описать язык, который она порождает. 8.18. Построить КС-грамматику, порождающую все цепочки нулей и единиц с одинаковым числом тех и других, 8.19. Будет ли контекстно-свободным язык, являющийся дополнением языка предыдущей задачи? 8.20.
Пусть 1 — КС-язык. Доказать, что: а) 1И1Т(й) = (ю: (Зх) (юх Е Ь)) есть КС-язык; б) Р1И(й) = 1ю: (Зх) (хю Е Ь)) есть КС-язык; в) $17В(й) = (ек (Зх) (Зр) (хюр Е Х )) есть КС-язык. 8.21. Доказать, что если с. — КС-язык, а  — регулярный язык, то Ь/В = (ю: юх Е Ь для некоторого х Е В) есть КС-язык. 718 В.
КОНТЕКСТНО-СВОБОДНЫЕ ЯЗЫКИ 8.22. Доказать, что следующие языки не являются контекстно-свободными: а) (а"Ьтва"Ьтв: и,ти > О); б) (а" Ььетт: тИ > И, тв, И > 0); в) (О"10" 10" 1: и > О); г) (х: х Е (а, Ь, с, и)* и число вхождений всех четырех букв в х одинаково); д) (тл": тя Е (а,6)'), где и — фиксированное число, не меньшее 2; (овЬвсв)тв. и ти > О). ж) (а"Ь"с": и)~ 0) . 8.23. Является ли контекстно-свободным язык, состоящий их всех цепочек в алфавите (а, Ь, с), таких, что число вхождений в них всех трех символов попарно различно? 8.24.
Используя конструкцию из доказательства теоремы 8.11, построить КС-грамматику для языка всех таких палиндромов в алфавите (О, 1), которые одновременно содержатся в регулярном языке: а) 0'1'0'; б) 0'1+0+1'0', в) состоящем из всех цепочек с четным числом нулей и четным числом единиц. 8.25. Пусть У и Ж вЂ” произвольные алфавиты, а Ьв 1т* -т ~ тт" — морфизм. Доказать, что: а) если Ь вЂ” КС-язык в алфавите тт, то Ь(Ь) — КС-язык в алфавите тт'; б) если К— КС-язык в алфавите тт', то Ь ~(к) — КС-язык в алфавите т'. У к аз а н не: для доказательства первого утверждения достаточно воспользоваться теоремой 8.9; чтобы доказать второе утверждение, нужно построить МП-автомат с буфером по аналогии с конструкцией конечного автомата с буфером (см.
Д.7.8). 8.26 (задача о КС-языках как решениях алгебраических систем уравнений). Пусть х'.(1т) — полукольцо всех языков в алфавите Ь'. Мультипликативным термом в ь".(Ъ') от переменных Хм ..., Х„называют выражение вида отХ1'...аХ,","ст+и где ол Е т', т =Т и+1, й > О, у = 1,и, Вопросы и задачи 719 и п > 1. Полиномом от переменных Хм ..., Х„называют произвольную (конечную) сумму мультипликативных термов. Алгебраической системой уравнений в полукольце Ю(1') называют систему уравнений относительно неизвестных Х1, Ха вида Х; = р;(Хм..., Х„), 1 = 1, и, где р;(Х1,..., Х„) — полипом от переменных Хм ..., Х„.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
