Ремонт принтеров, сканнеров, факсов и остальной офисной техники


назад Оглавление вперед




[15]

Пример 4.4. Необходимо минимизировать первоначальную таблицу переходов, полученную в примере 3.3 (см. табл. 3.9).

Решение. Вначале попытаемся выявить эквивалентные или псесдоэкннвалентные состояния. Ими могли бы быть только устойчивые состояния (2) и (4), так как они находятся в одном и том же столбце. Однако этим состояниям соответствуют различные состояния выхода. Поэтому в табл. 3.9 эквивалентных и псевдоэквпвалентных состояний нет. Попытаемся теперь найти совместные внутренние состояния, используя метод, изложенный в [1, З]. Для этого составим треугольную таблицу (табл. 4.4).

Pl

р2

Таблица 4.3 Рз Р4

I

<1), о

(4К о

<2)2, 0

(6),0 (3), 1

Таблица 4.4

Таблица 4.5

х2

V

X

X

*4

X

X

V

*i

х2

XiX2l z

0 0

1 0

1 1

(1), о

(2),0

3, 1

х2

1, о

(4), 1

(3), 1

Исходя яз этой таблицы найдем максимальные группы совместных внутренних состояний: 1, 2; 3 4.

Таким образом, можно объединить внутренние состояния xi и ms, а также у.з и Я4. После объединения этих внутренних состоянии получим минимизированную таблицу переходов (табл. 4.5) с двумя внутренними состояниями, т. е. требуется один элемент памяти.

Пример 4.5. Необходимо минимизировать первоначальную таблицу переходов, полученную в примере 3.4 (см. табл. 3.13).

Решение. Анализ табл. 3.13 показывает, что эквивалентных состояний в ней иет. Однако имеются псевдоэквивалентные состояния (2) и (7). После их объединения и замены состояния (7) на состояние (2) получим табл. 4.6.

12 3 4 5


Выявим теперь совместимые внутренние состояния, для чего построим треугольную таблицу (табл. 4.7).

В табл. 4.7 в клетках* (2, 5), (2, 6) и (3, 5) указана пара внутренних состояний яз и Хб. Это означает, что внутренние состояния ха и x.s; v.i и Хо; xs ii у.5 могут быть объединены (т. е. будут совместимыми), если совместимы внутренние состояния Хз и хв. Однако внутренние состояния Хз и лл несовместимы-крест в клетке (3, 6). Значит, пары внутренних состояний Хг и у.ъ, у--!, и -х.з; у.з .ii X5 несовместимы. Поэтому в клетках (2,5), С2, 6) и (3,5) треугольной таблицы указаны кресты.

Найдем теперь группы совместимых внутренних состояний:

1 23456

1, 2 3,44,55,6

1, 5 1, 6

1,5 ,6

Из них максимальными группами совместимых внутренних состоянии будут следующие: а=1,2; 6=1, 5, 6; с=3, 4; d=4, 5, три пары из которых (группы а и &, Ь и d) являются .пересекающимися. Остальные группы

5, 1, 6 5, 6, 1, 2, 3, 4, 5, 6) входят в максимальные группы и поэтому не являются максимальными. Теперь, строя таблицу покрытий (табл. 4.8), необходимо найти минимальное число максимальных групп совместимых внутренних состояний.

По табл. 4.8 составим функцию Петрика [3]: F = (a\J b) ас (с V d) (b V d) b.

Преобразуем ее в дизъюнктивную нормальную форму (ДНФ): F= (а у ab) (с \Jcd) (b V bd) = acb.

* В клетке (i, j) номер I соответствует столбцу, а

строке треугольной таблицы.

i

Таким образом, все максим ал ь;;ые группы, кроме d, должны быть использованы при построении минимальчои таблицы переходов (табл. 4.9) с тремя внутренними состояниями. При этом состояние автомата обозначаем буквой (номером) того внутреннего состояния, в котором оно устойчиво.

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

Пример 4.6. Необходимо минимизировать таблицу переходов (см. табл. 3.16), полученную в примере

3.5.


Таблица 4.10

2

X

3

X

2,4*

4

X

X

X

5

X

X

X

4,6х

6

X

X

X

X

i

7.

X

X

X

X

X

6,8х

!

j

8

X

X

X

X

X

X

X

9

X

X

X

X

X

X

X

8,10х

1

10

X

X

X

X

X

X

X

X

X

11

X

Х

X

X

X

X

X

X

X

10,12х

12

2,12х

X

X

X

X

X

х

X

1 *

X

X

13

X

V

13,14х

X

X

X

X

X

X

X

X

X

14

X

X

X

X

X

X

X

X

X

X

X

V

X

15

X

X

X

V

13,15х

X

X

X

X

X

X

X

X

X

16

X

X

X

X

X

V

15,16х

"1

х 1

X

X

X

X

X

X

17

X

X

X

X

X

X

х 1

V

16,17х

X

X

X

X

X

X

X

1

2

3

4

5

6

7

8

9

10

11

12

13

14 15

16



[стр.Начало] [стр.1] [стр.2] [стр.3] [стр.4] [стр.5] [стр.6] [стр.7] [стр.8] [стр.9] [стр.10] [стр.11] [стр.12] [стр.13] [стр.14] [стр.15] [стр.16] [стр.17] [стр.18] [стр.19] [стр.20] [стр.21] [стр.22] [стр.23] [стр.24] [стр.25] [стр.26] [стр.27] [стр.28] [стр.29] [стр.30] [стр.31] [стр.32] [стр.33] [стр.34] [стр.35] [стр.36]