Предыдущая страница реферата | 4  5  6  7  8  9  10  11  12  13  14 | Следующая страница реферата

Во - вторых, уравнения (2.2.3) и (2.2.4) могут быть представлены в табличной форме. Табличный аналог первого уравнения в (2.2.3) называется таблицей переходов, второго – таблицей выходов.

В - третьих, таблицы переходов и выходов можно объединить в одну.
Содержимое каждой клетки представляет собой дробь: над косой чертой вписывается соответствующее значение из таблицы переходов, под косой чертой
– значение из таблицы выходов. Полученная таким образом таблица называется общей таблицей переходов и выходов конечного автомата.

Граф автомата – это сигнальный граф, вершины которого обозначают состояния автомата, на дугах отражены условия перехода из состояния в состояние и значения выходных сигналов в виде дроби: над косой чертой – x(j), под ней – y(j).

Конечный автомат можно также описать с помощью матрицы переходов. Это аналог графа в табличной форме. Она представляет собой квадратную матрицу размерности число состояний [pic] число состояний, в которой отражены условия перехода из состояния в состояние аналогично изображённым на графе.

Общее определение конечного автомата:

M = (X, Y, S, ?, ?),

(2.2.5)

где X – входной алфавит, Y – выходной алфавит, S – множество состояний, ? – функция переходов, ? – функция выходов.

Пусть имеется два автомата: M и M’.

Если для любого [pic] существует по крайней мере одно [pic], эквивалентное ему, то говорят, что M’ покрывает M: M’ ? M.

Если одновременно M’ ? M и M ? M’, то M ~ M’ . Получаем эквивалентные автоматы. В этом случае невозможно различить M и M’ по их реакции на входные сигналы.

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

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

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

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

| |0 |1 |2 |3 |
|x(j) | | | | |
|s(j) | | | | |
|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 – Таблица выходов автомата

| |0 |1 |2 |3 |
|x(j) | | | | |
|s(j) | | | | |
|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 – Таблица переходов автомата

| |0 |1 |2 |3 |
|x(j) | | | | |
|s(j) | | | | |
|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 – Общая таблица переходов и выходов автомата

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

(si ~ sj) ? (sj ~ sk) [pic] (si ~ sk) (2.3.1)

Пара эквивалентных состояний переходит при всех возможных значениях входа в пары также эквивалентных состояний.

Алгоритм состоит из следующих шагов.

Рекомендуем скачать другие рефераты по теме: курсовая работа 2011, современные рефераты.



Предыдущая страница реферата | 4  5  6  7  8  9  10  11  12  13  14 | Следующая страница реферата

Поделитесь этой записью или добавьте в закладки