2014-02-02
2081
Способы описания и задания автоматов (лекция№10)
Для того, чтобы задать автомат, необходимо описать все компоненты кортежа S=(A, X, Y, d, l, а1 ). Множества А, X, Y описываются и задаются простым перечислением своих элементов. Среди многообразия различных способов заданий функций d и l (следовательно и всего автомата в целом) наибольшее распространение получили табличный и графический.
При табличном способе описания цифровых автоматов применяется два вида таблиц – таблица переходов и таблица выходов.
Таблица переходов отображает функцию переходов. Строкам таблицы соответствуют состояния автомата, т.е. в таблице столько строк, сколько состояний у автомата. Столбцам таблицы соответствуют входные значения, которые могут поступать на входы ЦА, т.е. столбцом столько – сколько элементов во входном алфавите. На пересечении i-столбца и j-строки в ячейке таблицы указывается состояние в которое перейдет ЦА под воздействием входного сигнала xi (которому соответствует i-й столбец) из состояния aj (которому соответствует j-я строка). Таблица переходов приведена на рисунке 6.2
|
|
|
| x1 | x2 | … | xm | |
| a1 | a2 | a1 | … | a2 |
| a2 | an-1 | a3 | … | a1 |
| … | … | |||
| an | - | an | … | a2 |
Рисунок 6.2 – Таблица переходов ЦА
Таблица переходов имеет одинаковый вид как для автомата Мура, так и для автомата Мили. Для частичных автоматов Мили и Мура в рассмотренных таблицах на месте не определенных состояний и выходных сигналов ставится прочерк. В таких автоматах выходной сигнал на каком-либо переходе всегда не определен, если неопределенным является состояние перехода
Таблица выходов для автомата Мили имеет такой же вид как и таблица переходов, только на пересечении i-столбца и j-строки в ячейке таблицы указывается выходное значение, которое сформирует ЦА под воздействием входного сигнала xi (которому соответствует i-й столбец) в состоянии aj (которому соответствует j-я строка). Таблица выходов автомата Мили приведена на рисунке 6.3
| x1 | x2 | … | xm | |
| a1 | y1 | y3 | … | y1 |
| a2 | yn-1 | y2 | … | yn-1 |
| … | … | |||
| an | - | y1 | … | y2 |
Рисунок 6.3 – Таблица выходов автомата Мили
Таблица выходов для автомата Мура состоит из одного столбца. Строкам таблицы соответствуют состояния автомата, т.е. в таблице столько строк, сколько состояний у автомата. Пример таблицы приведен на рисунке 6.4
| x1 | |
| a1 | y1 |
| a2 | yn-1 |
| … | |
| an | y2 |
Рисунок 6.4 – Таблица выходов автомата Мура
В некоторых случаях вместо двух таблиц определяющих ЦА удобно применять совмещенную таблицу переходов и выходов. На рисунке 6.5 приведена совмещенная таблица для автомата Мили. На рисунке 6.6 приведена совмещенная таблица переходов для автомата Мура.
|
|
|
| x1 | x2 | … | xm | |
| a1 | a2/y1 | a1/y3 | … | a2/y1 |
| a2 | an-1/yn-1 | a3/y2 | … | a1/yn-1 |
| … | … | |||
| an | - | an /y1 | … | a2/y2 |
Рисунок 6.5 – Совмещенная таблица переходов и выходов автомата Мили
| x1 | x2 | … | xm | Y | |
| a1 | a2 | a1 | … | a2 | y2 |
| a2 | an-1 | a3 | … | a1 | y1 |
| … | … | ||||
| an | - | an | … | a2 | y2 |
Рисунок 6.6 – Совмещенная таблица переходов автомата Мура
