Решение
Построим сам граф. Столбцы – вершины графа, строки – его рёбра. Если ребро инцидентно вершине, то клетка будет закрашена. Получим:
Составим остовное дерево для данного графа. Остовное дерево графа – это подграф графа, состоящий из всех вершин графа и минимального числа рёбер так, чтобы из любой вершины можно добраться в любую. Сначал включаем в оствное дерево ребро 
Ребро 
добавляет к остовному дереву вершину 
, его также включаем. Ребро 
добавляет к остовному дереву вершину 
, его также включаем. Ребро 
добавляет к остовному дереву вершину 
, его также включаем. Ребро 
добавляет к остовному дереву вершину 
, его также оставляем. Ребро 
добавляет к остовному дереву вершину 
, его также оставляем. Ребро 
не добавляет к остовному дереву новых вершин, поэтому его в остовное дерево не включаем. Ребро 
добавляет к остовному дереву вершину 
, поэтому его также включаем. В остовное дерево включены все вершины графа, поэтому остовное дерево построено.
4. А) Написать таблицу состояний данного автомата.
б) Считая автомат неинициальным, построить эквивалентный автомат Мура. Проверить работу данного и построенного автоматов над одним и тем же словом.
Изобразим таблицу данного автомата
Определение реакции автомата на входное слово
Пусть на вход автомата Мили АА и эквивалентного ему автомата Мура АВ из примера 4.3 поступает входное слово . Рассмотрим реакцию автоматов на входное слово.
Для автомата Мили имеем: 
; 
, т.е. под действием символа х1 автомат переходит в состояние 
с выходом у1; при следующем символе 
получим: 
; 
и т. д. В результате получим последовательность состояний и выходное слово:
| входное слово x |  — |
= k * |
| cостояния S |  |
= k+1 |
| выходное слово h |  — |
= k |
Для автомата Мура АВ имеем: при вхождении символа х1 автомат находился в состоянии с выходом 
, 
; 
. Далее поступает следующий символ х1 в состоянии 
с выходом и т.д. Последовательность входных и выходных символов, а также символов состояний выглядит аналогично представленным выше для автомата Мили:
| входное слово x | — |
= k |
| cостояния S |  |
= k+1 |
| выходное слово h |  |
= k+1 |
Видно, что реакция автоматов АА и АВ на входное слово совпадают с точностью до сдвига на один такт; это получилось потому, что реакция автомата Мура на входную букву наступает в следующем такте. Так будет и в общем случае, если автоматы эквивалентны и разных типов. Проверка этого утверждения предоставляется студентам.
4.4. Определение реакции автомата на входное слово
Пусть на вход автомата Мили АА и эквивалентного ему автомата Мура АВ из примера 4.3 поступает входное слово . Рассмотрим реакцию автоматов на входное слово.
Для автомата Мили имеем: 
;
, т.е. под действием символа х1 автомат переходит в состояние 
с выходом у1; при следующем символе 
получим:
;
и т. д. В результате получим последовательность состояний и выходное слово:
входное слово
выходное слово
Для автомата Мура АВ имеем: при вхождении символа х1 автомат находился в состоянии 
с выходом
,
;
. Далее поступает следующий символ х1 в состоянии 
с выходом
и т.д. Последовательность входных и выходных символов, а также символов состояний выглядит аналогично представленным выше для автомата Мили:
входное слово
выходное слово
Видно, что реакция автоматов АА и АВ на входное слово совпадают с точностью до сдвига на один такт; это получилось потому, что реакция автомата Мура на входную букву наступает в следующем такте. Так будет и в общем случае, если автоматы эквивалентны и разных типов. Проверка этого утверждения предоставляется студентам.
4.5. Задания для самостоятельной работы
1. Преобразовать заданный автомат Мили в автомат Мура, а затем последний — в автомат Мили (в табличном и графическом виде).
2. Для всех трёх автоматов из п. 1 определить реакцию на входное слово . Сравнить реакции автоматов и определить, являются ли они эквивалентными
5. Машины тьюринга
5.1. Общие положения
Машина Тьюринга это конечный автомат, снабжённый бесконечной лентой и читающей/записывающей головкой (просто головкой). Как и автомат, машина Тьюринга (МТ) описывается пятеркой (X, Y, Q, , ). Здесь:
Q=0, q1, q2, …, qm> множество внутренних состояний, причем q0 СТОП-состояние (в этом состоянии МТ не работает);
: QX Q функция переходов в следующее состояние;
: QX Y функция выходов.
В свою очередь, Y=XU, где U= команда на перемещение головки: R сдвинуться вправо, L влево, S стоять на месте.
Задавая МТ [5], вместо двух функций можно пользоваться одной (совме-щающей работу входа и выхода): : QX QXU, сопоставляющей каждой паре (qi, xj) выходную тройку (qk, u, xl), uU. Функция полностью описывает работу МТ и называется логической функцией машины Тьюринга. Таблица этой функции называется функциональной схемой, или программой машины Тьюринга. На каждом такте работы МТ головка обозревает в некоторой ячейке символ xj, а сама МТ находится в некотором состоянии qi, что описывается входной парой (qi, xj). В зависимости от входной пары МТ выполняет команду (qk, u, xl), uU, т.е. записывает в обозреваемую ячейку символ xl, передвигает головку в зависимости от значения u и переходит в новое состояние qk. Если на некотором этапе работы МТ переходит в СТОП-состояние, то дальнейших изменений в машине не происходит машина останавливается.
Последовательность входных символов, записанных в ячейках ленты, будем называть входным словом. Совокупность на ленте слова и состояния МТ для обозреваемой в данный момент ячейки ленты называется конфигурацией в МТ. Конфигурация указывает входную пару и определяет дальнейшую работу МТ. Если из некоторой начальной конфигурации через некоторое число тактов МТ приходит к СТОП-состоянию, то будем говорить, что МТ применима к входному слову; последовательность символов на ленте в момент остановки будем называть результатом преобразования входного слова МТ при данной начальной конфигурации, или просто выходным словом. Если же СТОП-состояние МТ не наступает, то будем говорить, что МТ не применима к входному слову при данной конфигурации.
Поскольку МТ преобразует допустимые входные слова в некотором алфавите в выходные слова в том же алфавите, то с математической точки зрения МТ это просто определённый алгоритм для преобразования машинных слов. Тем самым при помощи машины Тьюринга уточняется интуитивное понятие алгоритма.
Пример 5.1. МТ А, описываемая пятеркой (X, Y, A, , ), задана своей функциональной схемой (табл. 5.1) и имеет следующие алфавиты :
тюмгу / Тишин В.В. Дискретная математика в примерах
комбинации, а при получении одного символа кода мы переходим во 2 состояние. Далее имеем: 8 (y,q3) = q4, 5(хд/3) = q2. т.к. в слове хух послед ний символ может служить началом кодовой комбинации, а при полу чении одного символа кода мы переходим во 2 состояние. Рис.6.1.1 Найдя, действуя аналогично, значения функции переходов на остальных наборах переменных, получим диаграмму состояний (рис. 6.1.1а): Теперь запишем таблицу состояний дешифратора: Таблица 6 .1.1а
| A \Q | 02 | 03 | 04 | 05 | 06 | 07 | 08 | |
| X | q 2 , 0 | 02’° | 02,О | 05>° | 02,О | 02,0 | 08,° | 02 ’1 |
| У | 01.0 | 0 з.° | 04,0 | 01.0 | 06.° | 07,0 | 01,0 | 06,0 |
Задание полностью выполнено. Задание 6.1.2
Для данного конечного автомата, заданного таблично, со множеством внутренних состояний <1,2,3,4,5,6,7,8,9>, входным алфавитом и выходным алфавитом . 1. Выяснить, является ли автомат сильно связным. 2. Построить эквивалентный минимальный автомат. 3. Проверить работу исходного и минимального автоматов над словом » abbabaab».
| Таблица 6.1.2 | |||||||||
| № 1 | |||||||||
| 1 | 2 | 3 | 4 | 5 | 6 | 1 | 8 | 9 | |
| а | 4,х | 3 ,У | 7,х 5,х 8,х | 7,х | 2 ,У | 5,х | 2 ,У | ||
| Ъ | 7,у | 4 ,У | 9,х | 9 ,У | Ъу | 9,У | 8,х | 9, У | 5,х |
| №2 | |||||||||
| а Ч | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 2,х | 6 ,у | 3,х | 4,х | 2,х | |||||
| а | %>У | 7,У | 4,У | з,.у | |||||
| Ъ | 5>У | 9,х | 9,х | 5,х | 6,х | 7,У | 8 ,У | 6, .У | 8,х |
| № 3 | |||||||||
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
| а | 2,х | 1,х | з,.у | 5,х | 4,х | 8,х | з,.у | 6,х | з,.у |
| Ъ | 3,х | 4,х | 1,х | 2,х | 3,х | 3,х | 8,.У | 8,х | 4,.У |
| № 4 | |||||||||
| а Ч | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 5,х | 7,х | 8,х | 9,х | ||||||
| а | з,.у | 4,У | з,.у | 4. У | |||||
| Ъ | 8,.У | 6,х | 5,.У | 7, У | 7, У | ЪУ | ЬУ | 5,.У | 6,х |
| № 5 | |||||||||
| а Ч | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| а | 3,х | 8,х | 4,х | 1,х | 8,х | 7, У | у | 9. У | 9. У |
| Ъ | 2,х | 5,х | 5,х | 5,х | 2,х | ЬУ | 8 ’У | 8,х | 8,.У |
| А4 ? | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 9,У з,у | 8 ,х | ||||||||
| а | 2, У 4,У 9,У 5 ,У 4, У 7,У | ||||||||
| Ъ | Ъу 3 ,У 2 ,У з,у 7,У | 9,х | 4,У | 9,х | 9,У | ||||
| № 7 | |||||||||
| а Ч | 1 | 2 | 3 | 4 | 5 | 6 | 1 | 8 | 9 |
| 2 ,х | 4,х | 2 ,х | 2 ,х | 9,х | 8,х | 7,х | 7,х | ||
| а | 9,У | ||||||||
| Ъ | 3,х | 6 ,х | \,х | 3 ,У | з ,у | 7,х | 1 ,У | 6 ,х 6 ,х | |
| Таблица б.1.2(продолжение) | |||||||||
| №8 | |||||||||
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
| а | 2,х | 4,х | 4,х | 3,х | 6,У> | 7,х | 6,х | 7,х | 7,х |
| Ъ | 5,х | 3,х | 2,х | 5,У> | 6,У> | 5,У> | 7,х | 5,х | 5,х |
| № 9 | |||||||||
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
| а | 2,х | 3,х | 4,х | 5,х | 4,х | 4,х | 8,х | 5,х | 8,х |
| Ъ | 7, У | з,у> | 7, У | 5,У> | 7,х | 6,х | 9,У> | 9,х | |
| № 10 | |||||||||
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
| а | 2,х | 1,х | 4,х | 5,х | 4,У> | 7,х | 6,У> | 6,х | 6,х |
| Ъ | 3,х | 3,х | 5,х | 6,У> | 9,У> | 4,У> | 8,У> | 7,х | 5,х |
| № 11 | |||||||||
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
| а | 2,х | 7,х | 7,х | 3,х | 3,х | 5,х | у | 4,х | 1,х |
| Ъ | 1,х | 3,х | 2,х | 5,х | 4,х | 7, У | 7,У | 7,У | 7,У |
| № 12 | |||||||||
| £ 4 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 4,х | 8,х | 8,х | |||||||
| а | 2, .У | 6,У> | 5,.У | 6, У1 | 8. У1 | 9. У1 | |||
| Ъ 9. У з,у> 6, У1 3,х | 3,У> 4. У1 6, У’ 7, У | 4,х | |||||||
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
| а | 2 ,х | 4,х | 2 ,х | 2 ,х | 9,х | 9,У | 8 ,х | 7,х | 7,х |
| Ъ | 3,х | 6 ,х | \,х | з,у | з,у | 7,х | 1 ,У | 6 ,х 6 ,х | |
| № 14 | |||||||||
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
| а | з,у | 2 ,У | 1,У | 5,х | 5,У | 7,У | 7,У | 8,У | 5, У |
| Ъ | Ъу | 3,х | 7>У | 4,х | б, у 5, У 3 ,У 9, У | У | |||
| Таблица б.1.2(продолжение) | |||||||||
| № 15 | |||||||||
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
| а | 2 ,х | 4,х | 4,х 3,х | У | 7,х | 6 ,х | 7,х | 7,х | |
| Ъ | \,х 5,х 5,х | 5 ,У | У 5 ,У | 5,х 9,х 8,х | |||||
| № 16 | |||||||||
| А4 ? | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 6 ,х | 7,х | ||||||||
| а | 1 ,У | ЪУ | 4 ,У | 3 ,У | 5,У | 8,.У | 4. У | ||
| Ъ | 2 ,х | 5,х | 2 ,х | 9,х | 8,х | 2, У | 9,У | 5,х | 8,х |
| № 17 | |||||||||
| а Ч | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 4,х | 5,х | 3,х | 9,х | 6,х | 6, у | 7,х | 9,х | ||
| а | з,у | ||||||||
| Ъ | 2,х | 2,х | 5,.У | 2,х | 8,У | 7, У | 8,У | 2,х | 8,х |
| № 18 | |||||||||
| а Ч | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 5,х | 6,х | ||||||||
| а | 2, .У | 1,У | 2, У | з,у | 8,У | 7,У | 5,У | ||
| Ъ | 1>У | 4. У | з,у | 4,У | 4,У | 9,х | 4,У | 9,У | 8,У |
| № 19 | |||||||||
| А4 ? | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 1,х | 3,х | 2,х | 6,х | 5,х | 7,х | 9,х | |||
| а | 4,У | 8,У | |||||||
| ъ | 2 ,х | 9,х | 6 ,х | 5 ,У | 6 ,х | 5,х | 5,х | з,у | 3,х |
| №20 | 3 | 8 | |||||||
| а Ч | 1 | 2 | 4 | 5 | 6 | 1 | 9 | ||
| а | 2, У 1у 6 ,у 4 ,У Ъ у 3 ,У | 7,х | Ъу 7,У | ||||||
| Ъ | 3 ,У з ,У | 2 ,х | у 5, у | 4,х 8,х | 9 ,У 8 ,У | ||||
| №21 | 1 | 6 | 8 | ||||||
| А4 ? | 2 | 3 | 4 | 5 | 7 | 9 | |||
| 1,х | 3,х | 2,х | з,у | 6,х | 5,х | 7,х | 9,х | 8,х | |
| а | |||||||||
| Ъ | 2, У | 7,х | 5,х | 4,х | 4,х | 4,х | 4,х | 7,х | 6,х |
| Таблица б.1.2(продолжение) | |||||||||
| №22 | 1 | ||||||||
| 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | ||
| а | 1,х | з,у | 4. У | з,у | 2. У | 9. У | 7,У | 9. У | 7,У |
| Ъ | 2,х | 5,.У | 5,х | 5,х | 4,х | 4,х | 8,х | 7,х | 8,У |
| №23 | |||||||||
| а Ч | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 2,х | 1,х | 4,х | 4,х | 5,х | 7,х | 6,х | 7,х | ||
| а | 9. У | ||||||||
| Ъ | 4,х | 4,х | 2, У | 4,х | 6,х | 6,х | 6,х | 5,У | 8. У |
| №24 | |||||||||
| а Ч | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 2,х | 5,х | 2,х | 6,х | 5,х | 9,х | 9,х | |||
| а | 1,У | 8. У | |||||||
| Ъ | 1>У | 3,х | 4,х | 2,х | 4,х | 7,х | 6,х | 8. У | 6,х |
| №25 | |||||||||
| а Ч | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 2,х | 2,х | 9,х | 4,х | 6,х | 4,х | 3,х | |||
| а | 5,.У | 8,У | |||||||
| Ъ | 8. У | 6, У1 | 5,У | 5,У | 7, У | 1>У | 8. У | 7,У | 6, у |
| №26 | |||||||||
| а Ч | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| а | 3,х | 3 ,У | \,х | 4,х | 1 у | 9 ,у | 4 ,У 3 ,У 4,У | ||
| Ъ | 8 ,У | 6 ,х | 5 ,У Ъу 7,У ЪУ | 8 ,У 5 ,У | 6 ,х | ||||
| № 27 | |||||||||
| а Ч | 1 | 2 | 3 | 4 | 5 | 6 | 1 | 8 | 9 |
| 2,х 5,х 7,х 9,х | 4,х | ||||||||
| а | 6 ,у | 6 , у з, у ЪУ | |||||||
| Ъ 8 ,У 7,У 9 ,У 5 ,У Ъу 8 ,У 6 , у | 9,х | 6 ,у | |||||||
| №28 | |||||||||
| 1 | 2 | 3 | 4 | 5 | 6 | 1 | 8 | 9 | |
| а | 2, У | 6 ,у | 7,У | 3,х | 2,х | 5,х | 4,х | 5,х | 3 ,У |
| Ъ | 9,У | 5,х | 4,х | Ъу | 9,У | 7,У | 8 ,У ъ>,у Ъу | ||
| Таблица б.1.2(окончание) | |||||||||
| №29 | |||||||||
| > 4 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 4,х | 7,х | 1,х | 2, У | 2,х | 7,х | 9,х | |||
| а | 8,Д | ||||||||
| Ъ | 2,х | \,х | 5,х | 7,У | 3,х | 6,х | 9,Д | 8,х | |
| №30 | |||||||||
| а Ч | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 2,х | 1,х | 5,х | 7,х | 3,х | 5,х | 8,х | 9,х | 4,х | |
| а | |||||||||
| Ъ | 3,х | 5,Д | 9,х | 2,х | 4,Д | 7,х | 8,Д | ||
Пример решения задания 6.1.2 Решим задание 6.1.2 для автомата, заданного таблицей состояний: Таблица 6 .1.2а
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
| а | 5,х | з,д | 7,х | 5,х | 9,х | 4,Д | |||
| Ъ | 2,Д | 1,Х | 9,У | *,У | 7,х | 5,Д | 5,х | 3,х | 4,х |
1. Выясним, является ли автомат сильно связным. Для этого изобразим диаграмму состояний данного автомата, опуская пометки дуг и объеди-
няя пары противоположно направленных дуг, соединяющих одинако вые вершины графа. Получим: Рис.6.1.2 Построим в полученном графе циклический маршрут: Из возможности построения такого маршрута следует, что из любого состояния автомата достижимо любое состояние этого же автомата, то есть автомат является сильно связным. 2. Для построения минимального эквивалентного автомата выявим все пары эквивалентных состояний данного автомата. Для этого построим треугольную таблицу, где каждой паре различных состояний соответст вует одна клетка. Ели для какой-нибудь пары состояний одному значе нию входного сигнала соответствуют различные выходные символы, следовательно, эта пара состояний не является эквивалентной, и в соот ветствующую клетку мы ставим крест. Получим (табл.6.1.2Ь): Таблица б.1.2Ь 2 3 4 5 6
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
Далее, в незачеркнутые клетки выписываем пары состояний, в которые переходит автомат из состояний, соответствующих этой клетке, при подаче на вход одинаковых входных символов. Из этого правила записи есть два исключения: 1) не выписываем пары одинаковых состояний; 2) не выписываем пару, соответствующую заполняемой клетке. Будем иметь (табл. 6.1.2с): Таблица б.1.2с 2 5 6 7 8 9
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| Затем, | если внутри какой-нибудь клетки выписана пара, | соот | |||||
ветствующая зачёркнутой ранее клетке, то клетка с этой парой также зачёркивается. Окончательно имеем (табл. 6.1.2.d): Таблица 6.1.2d
| 2 | |||||||
| 3 | |||||||
| 4 | |||||||
| 5 | |||||||
| 6 | |||||||
| 7 | |||||||
| 8 | |||||||
| 9 | |||||||
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
Здесь каждой незачёркнутой клетке соответствует пара эквивалентных состояний, которые мы объединяем в классы эквивалентности: 1’= <1,3,4>; 2’= ; З’= ; 4’=. Строим минимальный автомат с четырьмя внутренними состояниями 1′ 2′, 3′, 4′. Для построения таблицы состояний минимального автомата поступаем следующим образом: чтобы найти значение функций перехода и выхо да, например, на наборе (а,Г), выбираем из класса эквивалентности I1 любого представителя. Пусть это будет состояние 3. Из таблицы со стояний исходного автомата мы имеем, что Х(а, 3) = х, значит, опреде
| лим также функцию выхода минимального автомата: | ЫаУ ) = х. | Из |
| таблицы состояний исходного автомата имеем, что | 5(а,3) = 7. | Но |
| 7е=3′, значит, будем считать, что 8(а,3) = 3′. |
Найдя значения функций перехода и выхода на всех наборах переме ненных, заполним таблицу состояний минимального автомата (табл. 6.1.2е):
| Таблица б.1.2е | |||
| i | i | з’ | 4′ |
| а | У ,х | 1 ‘,У | 4 ‘,у | 2 ‘,х | |||||
| Ъ | 2 ‘,У | \’,х | У ,х | У,У | |||||
| 3. Проверим работу исходного автомата над словом | |||||||||
| abbabaab. Пусть исходный автомат начинает свою работу, например, из | |||||||||
| 1 состояния: | |||||||||
| Входное слово | а | Ъ | Ъ | а | ъ | а | а | Ъ | |
| Состояния | 1 | 5 | 1 | 5 | 6 | 5 | 6 | 9 | 4 |
| Выходное слово | X | X | X | У | У | У | X | X | |
Так как 1е<1,3,4>=1′, то минимальный автомат запускаем из состояния l’. Получим:
| а | Ъ | Ъ | а | ъ | а | а | ъ | |
| 1 ‘ | У | У | У | 4′ | У | 4′ | У | 1′ |
| X | X | X | У | У | У | X | X |
Как мы видим, результатом работы исходного и минимального автома тов над словом abbabaab является одно и то же слово хххууухх 6.2. Частичные автоматы Автомат Мили называется частичным автоматом, если хотя бы одна из функций перехода или выхода не является всюду определённой. Говорят, что слово а применимо к состоянию q , неинициального авто мата, если функция переходов автомата, начавшего работу в состоянии q , над словом а, может быть неопределена лишь после считывания последнего символа слова а.