Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 11
Текст из файла (страница 11)
Указание: См. упр. 0.3.2 и О.З.З. 0.4.18. Покажите, что проблема выяснения, входит ли цепочка в данное рекурсивное множество, разрешима. 0.4.19. Существуют ли решающие последовательности для следующих частных случаев проблемы соответствий Поста: (а) (О[, 011), (10,000), (00,0); (б) (1,11), (!1,!0[), (!01,0!!), (0[1, !0!!)? Как согласовать возможносгь ответа в этом упражнении с фактом неразрешимости проблемы соответствий Поста? ЗАМЕЧАНИЯ ПО ЛИТЕРАТУРЕ 0.4.20. Покажите, что проблема соответствий Поста иад алавитом (а) разрешима. Как согласовать этот результат с неразрешимостью проблемы соответствий Поста над алфавитом, содержащим больше символов? "0.4.21. Пусть Р„Рю ...
— перечень (нумерация) всех частичных алгоритмов в некотором формализме. Определим новый перечень Р;, Р;, ... следующим образом: (1) П сть Р;г — гьй ие всюду определенный алгоритм из списка ЄЄ.... (2) Пусть Р;, — !'-й (всюду определенный) алгоритм из списка ЄЄ.... Тогда существует простой алгоритм определения по данному 1, является ли Р;. алгоритмом: достаточно посмотреть, четно или нечетно число 1. Более того, каждый Р; совпадает с некоторым Р!. Как согласовать существование такого взаимно однозна начного соответствия между натуральными числами и частичными алгоритмами с результатом примера 0.1 19о "«0.4.22, Докажите неразрешимость проблемы соответствий Поста. Указание: Для данной машины Тьюринга постройте такой частный случай проблемы Поста, что решающая последовательность для него существует тогда и только тогда, когда эта машина Тьюринга останавливается, начав работу на пустой ленте, «0.4.23.
Покажите, что алгоритм Евклида из примера 0.1, . 5 останавливается не более, чем через 4 [ойя![ шагов, если начинает работу с такими входами Р и а, что д > 1. Оп еделеиие. Вариантом проблемы соответствий Поста является проблема часагичного соответствия над алфавитом Х. Эт р Р лема состоит в том, чтобы для любого данного конечного множества пар из Х+ х Х" определить, существует лн для каждого т > 0 такая последовательность не обязательно различных паР (хи У,), (х„дя), ..., (х«, 9«), что пеРвые аг символов цепочки х х ... х совпадают с первыми аг символами цепочки у,уя...
у . '*«0.4.24. Докажите, что проблема частичного соответствия неразрешима. Замечания по литературе Йяяяс [!965! собрал хорошую янталогню мнагнх ранних работ по теории ялгорнпяон. Работа Тьюрингя [[936[, в которой впервые появились машины Тьюрянгя, читается с особым интересом, если Вмять яянду, что оня написаня до того, кян были придуманы современные электронные яычнолитьчьные к нй составляет Исследояяяне рекурсивных н чястнчно-рекурсняпых функций состав. часть теперь уже очень развитой области мятемятнкн, няяыяяемой тоорней 5! ГЛ. О. ПРРЛПЛРИТЕЛЬНЫЕ МЛТЕМЛТИЧЕСКИЕ СВЕДЕНИЯ О Э НнкОТОРЫЕ ПОНЯТИЯ ТЕОРИИ ГРЛФОВ 53 рекурсивных функций.
Хорошие источники я эпзй области — кп [!9071„Клики (!952] и Дэеися (!958] '). Проблеме гоотэетстяий Постя впервые появизэсь и (Пост, Р947, '1 Прб [Кнут, !9551. оэаиияя перед упр. 0.4.24, пзятл иэ з Игследоээяие „еложиости вычислений— репин изл1ереяия числа элементарных оперш!ий я ем и — это изучение Олго итмоэ с объеме эспомогетельиой пэмятн [ем слепня !ликой функции Бородин [!9701 и Хертмэпяс писэли хорошие обзоры по эшй теме э Э лен ын рляяд и Фишер [!970] состав ли Р ешепяя многих уппежпекий дэяпого аз~еле, ! РЭЗДЕЛЭ, ОТМЕЧЕПН Х ЭЯЕЗДОЧклия, ех !Йииского [!9071 и Хопкрофтэ и Ульмепл 1!959]. 0.5. НЕКОТОРЫЕ ПОНЯТИЯ ТЕОРИИ ГРАФОВ Многие структуры, полезные при выполнении вычислений, м ы рассмотрим ряд понятий теории графов кото ь добятся в дальнейшем.
0.5А. Ориентмреванные графы Графы могут быть ориентированные н не упорядоченные и неупорядоченные. Н б геориентированные, главным образом упорядоченные и не 'по я ас удут инте есовать ванные графы. неупорядоченные ориентнропа а А, , г Определение.
1(еупврядоченный ориентирова ф 6— р (, ]7), где А — множес!во элементов, называемых ве шинами (илн узлама), а ]1 — отношение на оговорено противяос, термин граф б . ет обоз ванный граф. уд т о означать ориентироПример 0.21. Пусть 6 = (А, )с), где А = (1, 2, 3, 4! (1, 2), (2, 3), (2, 4), 3, 4, 4, 1,, ' вить этот , (, ), (, 1), (4, 3)). Можно изобразить этот граф, заиумеровав четыре точки числами 1, 2, 3, 4 и и ове я стрелку из точки а в точку Ь, если ( Ь) Е й Рис.
0.5, .. Пример ориеитяроялияого графя, 1с. »у ь ~ьн!.— г . ю. 52 П а (а Ь) и)7 называется дугой (или Ребром) графа варят, что дуга выходит из вершины а и входигп в вершину Ь. Например, (1, 2) — дуга приведенного выше графа. Если (а, Ь)— дуга, то говорят, что вершина а предшествует вершине Ь, а вершина Ь сеедует за вершиной а. Не вполне точно можно сказать, что два графа равны, если их можно изобразить одинаково, пренебрегая именами (обозначениями) вершин. Формально равенство неупорядоченных ориентированных графов определяется следующим образом. Определение. Пусть 6, — (А,, ]4,) и 6,=(Л„)сь) — графы. Будем говорить, что 6, и 6, равны (или изоморфны), если существует такое бисктивное отображение 7: А, — А„что а[гтЬ тогда и только тогда, когда 1(а) )г',1(Ь). Иначе говоря, в графе 6, из вершины а в вершину Ь ведет дуга тогда и только тогда, когда в графе Оя из вершины, соответствующей а, ведет дуга в вершину, соответствующую Ь.
Часто вершинам и(или дугам графа приписывают некоторую информацию. Мы будем называть такую информацию разметкой, а соответствующий граф — помеченным графом. Определение. Пусть (А, ]1) — граф. Разметкой графа называется пара функций Г и Е, где [ (разметка вершин) отображает А в некоторое множество, а и (разметка дуг) отображает )1 в некоторое (возможно, отличное с г первого) множество.
Пусть 6,=(А„Рл) и 6х=(А„йх) — помеченньге графы' ) с разметками ()н Е,) и (1!л, Е,) соответственно. Тогда 6, и 6,— равные помеченные графы, если существует такое биективное отображение й: А, — А„что (1) айгЬ тогда и только тогда, когда й(а) )сей(Ь) (т. е. 6, и 6, равны как непомеченные графы); (2) Гл [а) = )х (й (и)) (т. е. соответствУющие веРшины имеют одинаковые метки); (3) а, ((а, Ь)) == иь ((й (а), й (Ь))) (т. е. соответствующие дуги имеют одинаковые метки). Во мно!их случаях метками спабжаютсн только вершины или только дуги. В такой ситуации считается, что множество значений функции 7' или соответственно Е состоит из единственного элемента. Тогда условие (2) или соответственно (3) выполняется тривиальным образом. Пример 0.22.
Пусть 6, — ((а, Ь, с), ((а, Ь), (Ь, с), (с, а))) и 6,=((0,!,2), ((1, 0), (2,!), (0,2))). Разметка графа 6, определ] Гоэорят еще: нагрухггннмг графи.— Лрил. перев. ГЛ. О. ПРЕДВАРИТЕЛЬНЫЕ МАТЕМАТИЧЕСКИЕ СВЕДЕНИЯ ляется формулами 1,(а) =-=)',(Ь) = Х, 1,(с) = г', д,((а, Ь)) = = у,((Ь, с))=-а, у,((с,а)) — р. Разметка графа 6, определяется фоРмУлами (е (0) = 1, (2) = Х, ), (! ) = 1', де ((О, 2)) = де ((2, 1)) = а, де((1, 0))=р. Графы 6, и 6, показаны на рис, 0 7. О.е.
НЕКОТОРЫЕ ПОНЯТИЯ ТЕОРИИ ГРАФОВ Если (а, Ь) — дуга ациклического графа, то а называется прямым предком Ь, а Ь вЂ” прямым потомком а, Если в ациклическом графе существует путь из а в Ь, то говорят, что а — предок Ь, а Ь--потомок а. На рис. 0.8 вершина 9 — потомок вершины 1, вершина 1 — предок вершины 9. а 6, Ю Оя Рпс.
0.7. Равные помеченные графы. 6, и 6, равны. Соответствующее биективное отображение Ь определяется формулами Ь(а) =О, Ь(Ь)- 2, Ь(с)- 1. (:) Определение. Последовательность вершин (а„а„...,а„), и)!, называется путем (или маршрутом) длины и из вершины а, в вершину а„, если для каждого 1 (1(и существует дуга, выходящая из вершины ат, н входящая в вершину аь Например, (1, 2, 4, 3) — путь в графе 6„изображенном на рис. 0,8.
Если существует путь из вершины а, в вершину а„, то говорят, что а„достижима из а,. Циклом называется путь (а„а,, ..., а„), в котором а,=-а,. В графе на рис. 0.6 есть цикл (1, 1) длины 1 и цикл (1, 2, 4, 1) длины 3. Граф называется сильно связным, если для любых двух разных вершин а и Ь существует путь из а в Ь. Введем, наконец, понятие степени вершины.
Степенью по входу вершины а назовем число входящих в нее дуг, а степенью по выходу — число выходящих из нее дуг. 9.$.2. Ориаитироваиныа ациияичасииа графье Определение. Ациклическим гра4юм называется (ориентированный) граф, не имеющий циклов. На рис. 0.8 показан пример ацнклического графа. Вершину, степень по входу которой равна О, назовем базовой. Вершину, степень по выходу которой равна О, назовем листом (нли концевой вершиной). На рис, 0.8 вершины 1, 2, 3 и 4— базовые, а вершины 2, 4, 7, 8 и 9 — листья.
Рнс. 0.8. Пример ацннлнчеекого графа. Заметим, что если Л вЂ” частичный порядок на множестве А, то (А, )7) — ациклический граф, Более того, если (А, )7) — ациклический граф и )т' †отношен „являться потомком", определенное на А, то )т' †частичн порядок иа А. 9,$З, Деревья Дерево — это ациклический граф специального типа, имеющий много приложений в теории компиляторов, Определение.
(Ориентированным) деревом Т называется (ориентированный) 'граф 6=(А, )7) со специальной вершиной гЕА„ называемый корнем, у которого (1) степень по входу вершины г равна О, (2) степень по входу всех остальных вершин дерева Т равна 1, (3) каждая вершина аЕА достижима из г, На рис. 0.9, а изображено дерево с шестью вершинами. Корень ,.фбозначен числом 1. Рисуя деревья, мы будем помещать корень 4верху и направлять все дуги вниз. Приняв это соглашение, мы .;:Не будем указывать стрелки, Теорема 0.3. Дерево Т Обладает следующими свойствами: (1) Т вЂ” ациклический граф, (2) для каждой вершины дерева Т существует единственный ''путь, ведущий из корня в зту вершину. Доказательство.
Упражнение. Д Определение. Поддеревом дерева Т=(А, )7) называется л любое дерево Т'=(А', )т'), у которого гл. е. првдвдгитвльныв мдтамхтичнские сведения 0.5. НВКОТОРЫВ ПОНЯТИЯ ТВОРИИ ГРАФОВ Ж, а »т Рис. 0.9. Пример дерева. (1) А' непусто н содержится в А, (2) )е'=(А'»с А') П)е, (3) ии одна вершина из множества А — А' не является потомком вершины из множества А'. Например, б на рис. 0.9 — поддерево дерева а. Мы будем говорить, что корень поддерева доминирует над эгим поддеревом.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
