2015-04-17
2046
Наиболее распространены табличный и графический способы задания абстрактных автоматов.
Задание автомата Мили
1. Табличный способ.
Автомат Мили задается таблицей переходов и выходов.
Пусть автомат иметь состояние A = {a1, a2, a3} при подаче входного алфавита Z = {z1, z2}; на выходе W = {w1, w2}.
Таблица переходов δ
| am zf | a1 | a2 | a3 |
| z1 | a2 | a3 | a3 |
| z2 | a3 | a2 | a1 |
Таблица выходов λ
| am zf | a1 | a2 | a3 |
| z1 | w2 | w1 | w2 |
| z2 | w2 | w1 | w1 |
Обе таблицы можно объединить в совмещенную таблицу переходов и выходов.
| am zf | a1 | a2 | a3 |
| z1 | a2 w2 | a3 w1 | a3 w2 |
| z2 | a3 w2 | a2 w1 | a1 w1 |
2. Графический способ
Основан на представлении абстрактного автомата в виде ориентированного графа, вершины которого соответствуют состояниям автомата, а дуги переходам между ними (рисунок 4).
Рисунок 4 – Представление абстрактного автомата в виде графа
Тогда автомат Мили согласно совмещенной таблице переходов и выходов имеет следующий вид.
Задание автомата Мура
1. Табличный способ
Составляется отмеченная таблица переходов и выходов.
|
|
|
A = {a1, a2, a3, a4}
Z = {z1, z2}
W = {w1, w2}
| wg | w1 | w2 | w1 | w1 |
| am zf | a1 | a2 | a3 | a4 |
| z1 | a2 | a3 | a4 | a4 |
| z2 | a4 | a1 | a1 | a1 |
2. Графический способ
Автомат Мура согласно отмеченной таблице имеет следующий вид.
