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

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

Решим задание 6.4.1 для автомата, заданного своей диаграммой со­ стояний:

7FXJ

а А

Ъ.О

Изобразим таблицу данного автомата (табл.6.4.1а):

По данному неинициальному автомату Мили S строим эквивалентный ему автомат Мура S' следующим образом:

То есть, |д(а1) = Х(а,\) = 0,..., |д(й4) = к(Ь,4) —1.

Функция переходов §' на состояниях, содержащих в изображении сим­ вол определяется так: 8'(гл*/) = ui, и е {a,b}, 1 < / < 4.

В остальных случаях первый символ имени нового состояния совпадает со считываемым символом входного алфавита, а второй символ имени нового состояния определяется с помощью функции переходов 8 авто­

Запишем таблицу состояний полученного автомата Мура:

Таблица 6.4. lb

Проверим работу исходного автомата на словом ЪааЪа, запустив его

Построенный автомат Мура запускаем из состояния *2:

Как видим, результаты работы обоих автоматов совпали.

Задание 6.4.2

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

состояний.

2.Изобразить найденный автомат таблицей переходов, отметив в ней заключительные состояния.

3.Минимизировать построенный автомат или убедиться, что построен­ ный автомат - минимальный.

4.Проверить работу полученного автомата над словом из множества Е и над словом, не попавшим в Е.

Таблица 6.4.2а

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

Решим задание 6.4.2 для события Е —{aba,bbab, baa, аЪЪЩ.

1. Изобразим диаграмму состояний автомата без выхода (рис. 6.4.2) с начальным состоянием 1, изобразив заключительное состояние двой­ ным кружком так, чтобы каждому слову из множества Е соответство­ вал маршрут из начального состояния в заключительное, и такие мар­ шруты находились бы лишь для слов из множества Е.

Рис. 6.4.2

2. Запишем таблицу состояний, соответствующую полученной диа­ грамме:

Таблица б.4.2а

3. Проверим автомат на минимальность, считая, что заключительным состояниям соответствуют выходные символы одного типа, а всем ос­ тальным состояниям - выходные символы другого типа.

Составим таблицу, расставив кресты в клетках, соответствующих парам состояний разного вида:

Таблица 6.4.2Ь

2

3

4

5

6

7

8

9

10

Продолжим процедуру минимизации. Окончательно получим таблицу

(табл. 6.4.2с):

Таблица б.4.2с

2

3

4

5

6

7

8

9

10

1 2 3 4 5 6 7 8 9

Видим, что состояния 7 и 9 эквивалентны. Переходим к мини­ мальному автомату, состояния которого соответствуют классам эквива­ лентности данного автомата.

Получим: 1'={1}, 2' = {2}, 3' = {3}, 4' = {4}, 5' = {5}, б' = {6}, 7' = {7,9},

8'= {8}, 9' = {10}.

Изобразим таблицу состояний минимального автомата (табл. 6.4.2d):

4. Проверим работу автомата над словом, вошедшим в Е, например,

bbab:

В результате на последнем шаге произошёл переход в заключительное состояние 4'- Проверим работу автомата над словом, не вошедшим в Е, например, baab :

Ъ а Ъ Ъ

В результате работы автомата над словом baab автомат оказался в со­

стоянии 9', которое не является заключительным, чего и следовало ожи­ дать.

Задание 6.4.3

Изобразить недетерминированный источник, соответствующий неде­ терминированному автомату, заданному таблицей переходов, с вход­ ным алфавитом {а,Ь} и множеством внутренних состояний {1,2,3,4,5}.

При построении использовать возможно меньшее число дуг. В постро­ енном недетерминированном источнике желательно присутствие хотя бы одного пустого ребра. Если построить соответствующий недетерми­ нированный источник с пустым ребром невозможно, докажите это.

Таблица 6.4.3(продолжение)