Гаврилов Г.П., Сапоженко А.А. - Задачи и упражнения по дискретной математике (1048833), страница 28
Текст из файла (страница 28)
в. вершины ш1 и шз, имеют одинаковые номера. Опсрация склеивания (эквивалентных) сошлояний состоит в следующем: вершины с одинаковыми номерами «стягиваются» в одну вершину, а появляющиеся при этом параллельныс*) одинаково помеченные дуги заменяются одной дугой (с твм жо направлением), несущей ту же пометку. Вершина и диаграммы Мура называется достижимой иэ (начальной) вершины и, если существует ориентированная цепь, выходящая из вершины и и заходящая в вершину и. Начальная вершина считается по определению достижимой. *) Дуги в ориентированном графе называются параллельными, если они соединяют одни и те же вершины и нх направления совпадают. »" г, »»иаграммьь тпаблицы, канонические уравнения, схемы 127 Операция исключения (удаления) недостижимых вершин состоит в удалении из диаграммы всех вершин, не являющихся достижимыми.
Диаграмма, в которой нет ни одной пары эквивалентных вершин и все вершины достижимые, называется приведенной диаграммой. Недостижимые вершины можно найти, просматривая в диаграмме все ориентированные цепи, выходящие из начальной вершины. Эквивалентность вершин можно устанавливать, используя непосредственно определение эквивалентных вершин или строя по диаграмме информативное дерево, соответствующее ей (и той о.-д. функпии, которую эта диаграмма описывает).
С помощью информативных деревьев легко устанавливается справедливость следующих утверждений. а) Операция исклкьчения недостижимых вершин в диаграмме Мура о.-д. функции приводит к диаграмме, роализующей ту же функцию. б) Операция склеивания эквивалентных вершин, примененная к диаграмме Мура о.-д. функции, приводит к диаграмме, реализующей ту же функцию. в) Число вершин в приведенной диаграмме Мура о.-д. функции равно весу этой функции. С диаграммой Г» функции» можно связать две функции: а) Р: А х Π— э В (функция выходов); б) О: А х Я вЂ” э 1„1 (функция переходов). Функции Р и С по орграфу Г» определяются так: по паре (а, ») находим вершину» и такую дугу, исходящую из», которой приписан входной символ а (пусть эта дуга есть (», 1)): значением функции Г на паре (а, ») является выходной символ, приписанный дуге (», 1) и стоящий в скобках за символом а; значение функции 1» на паре (а, ») совпадает с 1, т.
е. равно «номеру» того состояния, которое «является концом» дуги (», 1). Система уравнений у(И = Е(х(г), й(~ — 1)), й(1) = О(х(1), И1 — 1)), (1) й(о) = ц., где х(1) е А, у(1) е В, ц(1) е О (1 = 1, 2, ... ) и оо е ьг, называется каноническими уравнениями функции (оператора)» с начальным условием йо С помощью диаграмм Мура и канонических уравнений можно задавать и такие детерминированные функции, которые не являются ограниченно-детерминированными. Множество вершин орграфа Г», соответствующего такой д.функции, совпадает с расширенным натуральным рядом Ж = 10, 1, 2,... ). («Орграф» определен в гл.
Ч1.) Если»" —.- о.— д. функция, то функции Е(х(1), у(1 — Ц) и С(х(1)., в(1 — 1)) (см. систему (1)) и аргументы, от которых они зависят, принимают конечное число значений. Поэтому возможно табличное задание о.-д. функции» с помощью так называемой канонической глаблицы (табл. 4.1). 128 Гл. 17. Ограниченно-дегоерминированные функции т аблица 4.1 Вместо канонических уравнений (1) бывает удобно рассматривать такие канонические уравнения, в которых функции выходов и переходов являются функциями й-значной логики Ря (й > 2). Лля получения соответствующего представления функдии 1 алфавиты А, В и С кодируются векторами (наборами), координаты (компоненты) которых принадлежат множеству Еь = (О, 1, ..., й — 1) (й > 2).
Если 1 о.-д. фУнкциЯ и и =) 1ойь )А((, т, =) 1ойь )В([, г =]1ойя )11((, то длЯ кодирования букв из алфавитов А, В и Ц достаточно взять векторы (с координатами, принадлежагцими Еь), имеющие длины и, т н г соответственно*) . Система (1) преобразуется тогда в следующую: уз(1) = Рз(т (1), ", Я, Ч (1 — 1), ", Ч.(1 — 1)): у-(1)=В (' (1) " т Я, Ч1(1 — 1):"., Ч.(1 — 1И; Чз(1) = Сз(тз(1), ..., тлЯ, .Ч1(1 — 1), ..., Ч;(1 — 1И, (2) Че(1) =С„(Х1(1), ..., хиЯ, Ч1(1 — 1), ..., Ч,(1 — 1И, Ч (О) = Ч , " ., Ч.(О) = Чв, Используется также векторная запись систем, аналогичных системе (2).
При такой записи система (2) примет вид у1 д(1) = Г1 1(хоо(1), ц1"1(1 — 1И, с1 (1) = С (х (1) с1 (г 1 И (3) 1~1(О) 1г1 Функции Р, н С, в системе (2) являются, вообще говоря, часптчными, т.е. не всюду определенными. Обычно их доопределяют так, чтобы правые части уравнений в (2) имели по возможности более простой вид. Каноническая таблица, задаю|цел о.-д. функцию у, соответствующую системе (2), имеет го + и+ 2г столбцов и йлл г строк. Уравнения системы (2) называются кононически,ми уравнениями в скалярной форме, а уравнения из системы (1) .-- каноническими уравнениями в векьоорной форме.
л) Если д. функция 1 не является ограниченно-детерминированной, то с=со. у 2. 27иаграммвь гпабяиивь канонические уравнения, схемы 129 М ожно считать, что система (2) определяет функцию из множества Р„'„. Пример 1. Построить диаграмму Мура, каноническую таблицу и канонические уравнения для функции Дх)ы = у(1) у(2)... у(1)... (из Рцз ): 0 при 1= 1, ) 1 при 1= 1, 1 при 1>2; ' 11(1) при 1>2; (х(1) при 1 нечетном, в) у(1) = г (У(1 — 1) при 1 четном.
Решение. а) Построив три яруса информативного дерева заданной функции (рис. 4.5), видим, что все вершины дерева разбиваются О 1) , О(О),10 0 1 Рис. 4.7 Рис. 4.6 Рис. 4.5 на два класса эквивалентности: первый класс содержит только вершину О, а второй все остальные вершины. Следовательно, вес рассматриваемой функции равен 2, и диаграмму Мура для нее можно построить, отождествляя в «усеченном» дереве, изображенном на рис. 4.6, вершины 1, 2, 3, 4 и «восстанавливая» входные символы, соответствующие ребрам этого дерева.
Пиаграмма Мура заданной функции приведена на рис. 4.7. (Вместо двух дуг, идувцих из вершины 0 в вершину 1, мы изобразили на рисунке только одну, приписав ей два выражения; 0(0) и 1(0). Аналогично мы поступили и с дугами-петлями, исходящими из вершины 1. Начальное состояние помечено звездочкой.) Используя диаграмму Мура, строим таблицу. В качестве «входной» и «выходной» переменных возьмем хз (1) и да(1) (а не х(1) и у(1), Таблица 4.2 чтобы явно подчеркнуть содержательное отличие переменных из первоначального задания рассматриваемой функции от переменных, входящих в ее канонические уравнения). В качестве переменной 9 Г. П.
Гаврилов, А. А. Сапожонка 130 Гл. 17. Ограниченно-детерминированные функции для описания состояний берем О(1 — 1) (на «входс») и О(1) (на «выходе»). Каноническая таблица функции -- табл. 4.2. Из таблицы следует, что уз(1) = О(1 — 1) и д(1) = 1. Значит, канонические уравнения и начальное условие заданной функции таковы: у,® = О(1 — 1), Ч(1) =1 д(0) = О. б) Для нахождения веса функции и построения диаграммы Мура достаточно изобразить три яруса ее информативного дерева (рис. 4.8).
0(0) ЦО) 0(Ц 0 0 ЦЦ Рис. 4.8 Рис. 4.9 Рис. 4.10 Вес функции равен 3. Вершина 0 образует один класс эквивалентности. Второй класс образуют вершины 1, 3, 4, ... Третий класс вершины 2, 5, 6,.... «Усеченное» дерево и диаграмма Мура приведены на рис. 4.9 и рис. 4.10.
Построим таблицу. В качестве «входной»переменной возьмем х11), а в качестве «выходной» у11). Для описания состояний берем переменные О~(1 — Ц, дз(1 — 1) (на «входе») и Оз(1), дз(1) (на «выходе»). Состояние 0 кодируем парой (О, 0), т.е. Оз — — пз = О., состояние 1 ко- Таблица 4.3 дируем парой (О, 1), т. е. д~ — — О, оз — — 1, и состояние 2 . парой (1, 0), т.
е. оз = 1, оз = О. Каноническая таблица функции табл. 4.3. В таблице выписаны все наборы значений поременных и1г), а(1 — Ц, дз(1 — 1). Для дз = дз = 1 соответствующего состояния в рассматриваемой диаграмме нет. Из-за етого функции, «описывающие» у11), дз(1) и пз11), являются частичными (не всюду определенными) булевыми функциями.
Мы их доопределим каким-либо образом; например, как в табл. 4.4. 12. Лиаераммвь нгабвииьь канонические уравнения, схемы 131 Таблица 4.4 д (1) у(г) В(1) Чг(г — 1) х(1) де(е — 1) Указанное доопределение дает достаточно простые представления переменных у(1), уг(1) н аг(1) (как булевых функций от переменных х(1), дг(1 — 1) н уг(1 — 1)): у(1) = дг(1 — 1), дг(1) = х(1). уг(1 — 1) и' х(1) е1г(1 — 1), дг(1) = х(1) .е1г(1 — 1) Ч х(1) уг(1 — 1). Тем самым канонические уравнения нами получены. Остается выписать начальное условие.
Оно имеет вид Ог(0) = Ог(0) = О. в) Достаточно построить четыре яруса информативного дерева (рис. 4.11). Все верпгины дерева разбиваются на три класса эквивалентности: первый класс содержит вершины О, 3, 4, 5, 6, ..., второй Рис. 4.11 класс вершины 1, 7, 9, 11, 13, ..., третий класс вершины 2, Я, 10, 12, 14,... Вес рассматриваемой функции равен 3.
«Усеченное» дерево и диаграмма Мура изображены на рис. 4.12 ~ф 1 О Рис. 4.13 Рис. 4.12 и рнс. 4.13. Каноническая таблица (с доопределенными значениями соответствующих функций) — - табл. 4.5. Состояния закодированы нами трациционным образом; состоянию 0 сопоставлена пара (О, 0), т.е. аг = аг — — О, состоянию 1 сопоставленапара (О, 1), т.е. Ог =0 и дг =1, состоянию 2 пара (1, 0), т.е.
Ох=1 и аз=О. 132 Гж 1'г'. Ограниченно-дегнерминированные функции Таблица 4.5 Канонические уравнения и начальное условие имеют следующий 'ид УЮ = У11) .0211 — 1) '7х(1) .Ч111 — 1), Ч (1) = Ф) Ч,(~ — 1) Ч,(~ — 1), Чг'1) т(1) Ч1(1 1) Чз(1 Ц Ч, 1О) = Ч, 10) = О. Пример 2. Лля каждой диаграммы, изображенной на рис. 4.14, построить приведенную диаграмму.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
