XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 92
Текст из файла (страница 92)
7.7. Доказать, что любая леволинейнал грамматика зквивалентна некоторой праволинейной грамматике. 7.8. Дано конечное множество слов (пп ..., иь) Е У+. Язык Ь определяется как множество всех цепочек в У', которые не начинаются ни одним из слов пм ..., щ,. Построить регулярную грамматику, порождающую язык Ь. 7.9. Доказать, что язык Ь+" = Ц Г регулярен для любого ыь)0 й при условии регулярности Ь. 7.10. Определить, какие множества цепочек задаются регулярными выражениями: а) (а+ Ь)'с'(Ь+ с); б) ((аЬ)+(са)*)', в) (а+(Ь+ с)'а+ Ь+(а+ Ь)'Ьс)*.
7.11. Доказать, что для любых регулярных выражений а и р' имеет место тождество (а+,6)' = (а'р'*)". 7.12. Инверсия цепочки х Е У* — зто цепочка символов хн, полученная переписыванием х справа налево, т.е. если х = ау1...ау„, то х = ай„...ауп Доказать, что если Ь— и регулярный язык, то Ь = (у: у=х, хЕ Ц вЂ” регулярный язык. Привести два варианта доказательства: 1) используя только определение регулярного языка; 2) используя конечные автоматы. 7.13. Доказать, что И" = А.
581 Вопросы изолачи 7.14. Написать регулярное выражение для множества цепочек в алфавите (О, 1), содержащих четное число нулей и четное число единиц. 7.16. Найти языки, допускаемые конечными автоматами, заданными на рис. 7.48. а,Ь д,ь,с а,Ь Рис. 7.48 '7.16. Доказать, что любой конечный язык регулярен. Т.17. Построить конечный автомат с входным алфавитом (О, 1, ..., 9), допускающий десятичные записи: а) всех четных чисел; б) нечетных чисел; в) чисел, делящихся на 4; г) чисел, делящихся на 3; д) чисел, делящихся на 9. 7.18.
Построить конечный автомат, допускающий десятичные записи тех и только тех натуральных чисел, которые делятся на заданное число Й. У к аз а н и е: автомат должен выполнять деление „уголком" и в нем должно быть ровно Й состояний. Т 19. Обобщенным конечным автоматом назовем ориентированный граф, размеченный над полукольцом регулярных выРажений (с выделенной начальной вершиной и подмножеством заключительных вершин), в котором метка дуги может быть произвольным регулярным выражением.
Определяя язык такого автомата аналогично языку обычного конечного автомата, доказать, что для любого обобщенного конечного автомата существует эквивалентный (т.е, допускающий тот же самый язык) конечный автомат. 582 7. КОНЕЧНЫЕ АВТОМАТЫ И РЕГУЛЯРНЫЕ ЯЗЫКИ 7.20. Построить конечные автоматы, эквивалентные следующим обобщенным конечным автоматам: а) вход до, выход дз, дуги с метками (оо, оо, (а+Ь)с)), (до, дд, а), (дд, дд, (а + с)Ь), (дь дз, а'), (до, дг, 6*), (Чг, дз, Ь*), (ддг, ог, са(а+6)+); б) вход до, выход дз; дуги (до ог, (аЬ)*), (Чг, ог, (са)'Ь), (до оь Ед), (дь дз с+) (дг дз ((Ь+ а)+с')). 7.21.
Решить систему линейных уравнений с регулярными коэффициентами хд = (01*+1)хд+хг, хг =1хд+ООхз+11, хз = хд +хг+ Л. Для регулярного выражения, задающего компоненту решения хз, построить допускающий его конечный автомат. 7.22. Доказать, что линейное уравнение х = дгх+,9 с регулярными коэффициентами имеет: а) единственное решение при Л ф а; б) бесконечно много решений при Л Е а, причем общее решение можно записать в виде х = дх'(,8+ д ), где Ь вЂ” произвольный язык. 7.23. Для произвольного алфавита 1т' определим операцию левого деления на заданную букву, а именно: для произвольных а е Ю и х = х(1)х(2)...х(Й) Е Ю' положим а дх = х(2)...х(Ь), если х(1) = а, а если х(1) ф а, то считаем, что выражение а х не определено.
В частности, выражение а дЛ всегда не определено. Доказать, что если Ь вЂ” регулярный язык (в алфавите Ю), то для всякого а е 1т' язык а ~ д = 1ш о = а дх, х е д.) регулярен. 7.24. Аналогично операции левого деления на букву можно определить операцию левого деления на слово, полагая пд дх = = р, если х = пдр (иначе деление не определено). Определяя язык 583 Воиросьги задачи ш-11, так же, как в предыдущей задаче, доказать, что этот „зык регулярен для любого регулярного 1. Т.25.
Определим операцию левого деления языка 11 на язык 1,2, положив иеь2 доказать, что если 11 и 12 регулярны, то язык 12 ~11 регу7.26. Пусть 1, — регулярный язык. Доказать, что 1И1Т(1) = (ш: (Эх)(юх Е Ь)) есть регулярный язы. Т.27. Пусть 1 — регулярный язык. Доказать, что Р1И(й) = (ю: (3х)(хю Е 2 )) есть регулярньй язык. 7 28. Пусть 1 — регулярный язык. Доказать, что БУВ(1) = (ю: (Зх)(Зу)(хюу Е 1, где х,у,ю не пусты)) есть регулярньй язык. Т 20. Построить конечный автомат, допускающий все цепочки в алфавите (а, Ь), не содержащие вхождений подцепочки аЬа.
Т 80. Построить конечный автомат, допускающий все цепочки в алфавите (а, Ь), которые не начинаются с а6 и не кончаются аЬ. 7-81 Построить конечный автомат, допускающий те и только олько те цепочки в алфавите (а,6), которые не допускает 584 7. КОНЕЧНЫЕ АВТОМАТЫ И РЕГУЛЯРНЫЕ ЯЗЫКИ следующий конечный автомат: вход щ; выход дз; дуги с метками (дм дм Ь), (4м дз1 а), (дз, Чм Ь), (дз, дз, Ь), (дз, дз, а, Ь), Для построенного автомата записать регулярное выражение, задающее его язык. 7.32. Построить конечный автомат, допускающий все последовательности нулей и единиц, кроме тех, которые содержат подпоследовательность 11011.
Т.ЗЗ. Построить конечный автомат, допускающий те и только те цепочки в алфавите (0,1), которые не начинаются цепочкой 01 и не заканчиваются цепочкой 11 (т.е.не разрешаются цепочки вида 01х и цепочки вида 911, каковы бы ни были цепочки х, р Е 10, 1) ). Указание: дополнением языка, для которого нужно построить конечный автомат, является множество всех таких цепочек нулей и единиц, которые начинаются цепочкой 01 или заканчиваются цепочкой 11. Допускающий зто множество цепочек автомат строится как автомат для объединения 01(0+ 1)'+ (0+ 1)'11 способом, который изложен при доказательстве теоремы Клини (см.
теорему 7.6). Т.З4. Минимизировать по переходам автомат, изображенный на рис. 7.49. Указ ание: предварительно удэлить недостижимые из де вершины. Рис. 7.49 Вопросы и задачи 585 7.35. Используя лемму о разрастании, доказать, что следующие множества не регулярны: а) (О" 10": и > Ц; б) (: с(о,6) ); в) множество цепочек в алфавите (О, Ц, являющееся наименьшим решением нелинейного уравнения х = Ох1+ хг + 01 в полукольце Ь(У); г) (а": и >11; д) (пс и Е (а, 6, с))' и имеет одинаковое число символов а и 6 или одинаковое число символов 6 и с; е) (О" 1": и > 0); ж) (О" 1~а: и уЕ чп, и, гп > 0); з) множество всех цепочек нулей и единиц, в которых число нулей больше числа единиц. 7.36. Решить задачу о перечеслении путей для ориентированного графа, приведенного на рис.
7.50. Вычислить полностью матрицу путей и опи- о1 сать все ее компоненты словесно. Указание: помечая дуги графа упорядоченнымц парами, составить систему уравнений с регулярными козффициентами в алфавите меток дуг для определения каждо- Рис. 7.60 го из трех столбцов матрицы стоимостей (см 5 О). Для данного графа имеем систему уравнений С х1 = (1,2)хг+ (1,3)хз+ Л хг = (2,1)х1+ (2,2)хг+ (2,3)хз, хз = (3,1)х1. Решая ее, получим: хг = (2,1)((1,2)хг+ (1,3)хз+ Л) + (2,2) хг+ (2,3)хз = = ((2,1)(1,2) + (2,2))хг+ И2,1)(1,3) + (2,3))хз+ (2,1), откуда хг = ((2,1)(1,2) + (2,2))'(((2,1)(1,3) + (2,3))хз + (2,1)).
586 7. КОНЕЧНЫЕ АВТОМАТЫ И РЕГУЛЯРНЫЕ ЯЗЫКИ Далее, х1 = (1,2)((2,1)(1,2) + (2,2))"(((2,1)(1,3) + + (2,3))(3,1)х1 + (2,1)) + (1,3)(3,1)х1 х1 = ((1,2)((2,1)(1,2) + (2,2))*(((2,1)(1,3) + + (2,3))(3,1) + (1,3)(3,1))'(1.,2)(2,1). Написанное вьппе регулярное выражение, полученное как значение переменного хм обозначает множество всех путей, начинающихся и заканчивающихся в первой вершине. Это множество можно словесно описать так: идем из первой вершины во вторую по дуге (1, 2), затем „крутимся" сколько угодно раз (или ни разу) либо по контуру 2, 1, 2 либо по петле (2, 2) (как угодно их чередуя); далее идем в третью вершину через первую по пути 2, 1, 3 или сразу по дуге (2, 3), а из третьей вершины возвращаемся в первую — получается замкнутый путь, по которому можно „крутитьсл", но не следует забывать, что можно „крутиться" и по контуру 1, 3, 1.
Кроме того, попав, как описано вьппе, во вторую вершину, можно сразу вернуться в первую, закончив „путешествие". 7.37. Для натуральных чисел, заданных в виде слов в алфавите (О, ~), определить операцию умножения и построить мапшну Тьюринга над алфавитом 10, ~'1, которая для любых натуральных чисел т н п вычисляет нх произведение. Т,38.
Построить машину Тьюринга над алфавитом (а, Ь), которая: а) к любому слову х Е (а,Ь)' присоединяет слева (сцрава) заданное слово ше; б) распознает палиндромы в алфавите (а, Ь); в) распознает двойные слова в алфавите (а, Ь ); г) удваивает произвольное слово х Е (а, Ь), т.е.
по этому слову вычисляет слово хх. 8. КОНТБКСТНО-СВОБОДНЫБ ЯЗЫКИ 8.1. КС-грамматики. Деревья вывода. Одиоэиачиость Мы приступаем к изучению одного из важнейших классов формальных языков — класса коншвксшно-свободныя языков (КС-языков). Определение КС-грамматик и КС-языков бь|ло дано в 7.3. Напомним, что порозсдающую граммашикр 0 = (К Ф, В, Р) называют контекстносвободной (или КС-грамматикой), если каждое правило вывода из множества Р имеет вид А-+ у, где А Е Ф вЂ” нетпермина ц, а у е (У 0 Ф)' — цепочка в объединенном алфавише граммагпики. Таким образом, неформально каждое правило вывода в КС-грамматике есть правило замены нетерминального символа цепочкой (возможно, пусшой) в объединенном алфавите.
Каждому выводу в КС-грамматике, начинающемуся с не- терминального символа, однозначно сопоставляется ориентаированныб гра4, являющийся деревом и называемый деревом вывода. Вершины дерева вывода помечаются символами объединенного алфавита грамматики или пустой цепочкой. Подчеркнем, что дерево вывода сопоставляется не грамматике, а конкретному выводу в данной грамматике, хотя мы увидим, что нескольким различным выводам может быть сопоставлено одно и то же дерево вывода.
Прежде чем давать математическое определение дерева вывода, покажем на примере, как по данному выводу в заданной КС-грамматике строится зто дерево. 588 В. КОНТЕКСТНО-СВОБОДНЫЕ ЯЗЫКИ Пример 8.1. Рассмотрим КС-грамматику Со = ((а, 6), (В, А, В, С), В, Ро), где множество правил вывода Ро имеет вид: В-+ АВС, А-+ВВ, А -+ Л, В-+СС, В~а, С-+АА, С-+ 6. (1) (2) (3) (4) (5) (6) (7) В этой грамматике рассмотрим такой вывод: В ~О) АВС )-(з) ВВВС)-1е) )-~в) ВВВАА)-1з) ВВВЛА )-<е) ССВВА ф В7) 66ВВА)Ь66 А)-т 66 ВВВ5) 66 ааа Б По шагам этого вывода проследим процесс построения дерева вывода. Первому шагу соответствует дерево, изображенное на рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
