тюмгу / Тишин В.В. Дискретная математика в примерах

комбинации, а при получении одного символа кода мы переходим во 2 состояние.

Далее имеем: 8 (y,q3) = q4, 5(хд/3) = q2. т.к. в слове хух послед­

ний символ может служить началом кодовой комбинации, а при полу­ чении одного символа кода мы переходим во 2 состояние.

Рис.6.1.1

Найдя, действуя аналогично, значения функции переходов на остальных наборах переменных, получим диаграмму состояний (рис. 6.1.1а):

Теперь запишем таблицу состояний дешифратора:

Таблица 6 .1.1а

Задание полностью выполнено.

Задание 6.1.2

Для данного конечного автомата, заданного таблично, со множеством внутренних состояний {1,2,3,4,5,6,7,8,9}, входным алфавитом {а,Ь} и

выходным алфавитом {х, у } .

1.Выяснить, является ли автомат сильно связным.

2.Построить эквивалентный минимальный автомат.

3.Проверить работу исходного и минимального автоматов над словом

"abbabaab".

№6

№ 13

Пример решения задания 6.1.2

Решим задание 6.1.2 для автомата, заданного таблицей состояний:

Таблица 6 .1.2а

1. Выясним, является ли автомат сильно связным. Для этого изобразим диаграмму состояний данного автомата, опуская пометки дуг и объеди-

няя пары противоположно направленных дуг, соединяющих одинако­ вые вершины графа. Получим:

Рис.6.1.2

Построим в полученном графе циклический маршрут:

Из возможности построения такого маршрута следует, что из любого состояния автомата достижимо любое состояние этого же автомата, то есть автомат является сильно связным.

2. Для построения минимального эквивалентного автомата выявим все пары эквивалентных состояний данного автомата. Для этого построим треугольную таблицу, где каждой паре различных состояний соответст­ вует одна клетка. Ели для какой-нибудь пары состояний одному значе­ нию входного сигнала соответствуют различные выходные символы, следовательно, эта пара состояний не является эквивалентной, и в соот­ ветствующую клетку мы ставим крест. Получим (табл.6.1.2Ь):

Таблица б.1.2Ь

2

3

4

5

6

7

8

9

Далее, в незачеркнутые клетки выписываем пары состояний, в которые переходит автомат из состояний, соответствующих этой клетке, при подаче на вход одинаковых входных символов.

Из этого правила записи есть два исключения:

1)не выписываем пары одинаковых состояний;

2)не выписываем пару, соответствующую заполняемой клетке.

Будем иметь (табл. 6.1.2с):

Таблица б.1.2с

2

5

6

7

8

9

ветствующая зачёркнутой ранее клетке, то клетка с этой парой также зачёркивается. Окончательно имеем (табл. 6.1.2.d):

Таблица 6.1.2d

Здесь каждой незачёркнутой клетке соответствует пара эквивалентных состояний, которые мы объединяем в классы эквивалентности:

1'= {1,3,4}; 2'= {2,8,9}; З'= {5,7}; 4'={6}.

Строим минимальный автомат с четырьмя внутренними состояниями

1' 2', 3', 4'.

Для построения таблицы состояний минимального автомата поступаем следующим образом: чтобы найти значение функций перехода и выхо­

да, например, на наборе (а,Г), выбираем из класса эквивалентности I1

любого представителя. Пусть это будет состояние 3. Из таблицы со­ стояний исходного автомата мы имеем, что Х(а,3) = х, значит, опреде­

Найдя значения функций перехода и выхода на всех наборах переме­ ненных, заполним таблицу состояний минимального автомата (табл. 6.1.2е):

Так как 1е{1,3,4}=1', то минимальный автомат запускаем из состояния l'. Получим:

Как мы видим, результатом работы исходного и минимального автома­ тов над словом abbabaab является одно и то же слово хххууухх

6.2. Частичные автоматы

Автомат Мили называется частичным автоматом, если хотя бы одна

из функций перехода или выхода не является всюду определённой.

Говорят, что слово а применимо к состоянию q , неинициального авто­

мата, если функция переходов автомата, начавшего работу в состоянии q , над словом а, может быть неопределена лишь после считывания

последнего символа слова а.