Синтез комбинацонных схем и конечных автоматов, сети Петри
Рефераты >> Программирование и компьютеры >> Синтез комбинацонных схем и конечных автоматов, сети Петри

Существуют два основных положения определения понятия эквивалентности состояний:

а) состояния si и sj явно различны, если соответствующие им строки в таблице выходов разные;

б) состояния si и sj явно эквивалентны, если соответствующие им строки в общей таблице переходов автомата одинаковы или становятся таковыми при замене si на sj или наоборот.

Минимизация (упрощение) автоматов основано на понятии эквивалентных автоматов. Под минимизацией автомата будем понимать сокращение числа его состояний.

2.3 Расчёты и полученные результаты.

Построение таблиц переходов, выходов и общей таблицы переходов и выходов на основе заданных уравнений автомата Мили очевидно:

x(j)

s(j)

0

1

2

3

0

1

0

1

0

1

0

1

0

1

2

1

0

1

0

3

0

1

0

1

4

1

0

1

0

5

0

1

0

1

6

1

0

1

0

7

0

1

0

1

Таблица 2.3.1 – Таблица выходов автомата

x(j)

s(j)

0

1

2

3

0

0

1

2

3

1

2

3

4

5

2

4

5

6

7

3

6

7

0

1

4

0

1

2

3

5

2

3

4

5

6

4

5

6

7

7

6

7

0

1

Таблица 2.3.2 – Таблица переходов автомата

x(j)

s(j)

0

1

2

3

0

0/1

1/0

2/1

3/0

1

2/0

3/1

4/0

5/1

2

4/1

5/0

6/1

7/0

3

6/0

7/1

0/0

1/1

4

0/1

1/0

2/1

3/0

5

2/0

3/1

4/0

5/1

6

4/1

5/0

6/1

7/0

7

6/0

7/1

0/0

1/1

Таблица 2.3.3 – Общая таблица переходов и выходов автомата

Перейдём непосредственно к минимизации полученного автомата по числу состояний. Для этого воспользуемся алгоритмом, известным в литературе как метод Гриса - Хопкрофта. Его достоинство в том, что он даёт гарантированно минимальную форму автомата. Однако в общем случае он является довольно трудоёмким и применяется, как правило, для автоматов с небольшим количеством состояний. Он основан на свойстве транзитивности эквивалентности


Страница: