- •Домашняя работа № 7 Проектирование конечного автомата. Эквивалентные Автоматы
- •Задание 1
- •I. Неформальное описание работы автомата:
- •Множества X, q, y
- •2. Описание автоматных функций
- •3. Граф переходов автомата
- •4 Закодированная таблица реализации ка
- •Кодированная таблица переходов и выходов
- •Задание 2
- •Построим прямое произведение автоматов.
- •4. 3. Построим для произведения функции переходов состояний и выхода.
- •4.4. Построим граф переходов автомата Ax b.
- •4.5. Исключим недостижимые состояния.
3. Граф переходов автомата
Граф переходов автомата – более наглядная форма представления конечного автомата.
Возможных состояний автомата 4, следовательно у графа 4 вершины
Входных сигналов 5, следовательно у каждой вершины максимум 5 исходящих ребер (по одному на каждый входной сигнал).
Для каждого ребра:
- Направления указаны в таблице для функции переходов состояний.
- Входные сигналы - в таблице для функции переходов состояний
- Выходные сигналы - в таблице для функции выходов
4 Закодированная таблица реализации ка
Для аппаратной реализации предварительно осуществляют двоичное кодирование автомата. Для составления кодированной таблицы примем следующие обозначения:
Входные сигналы X (всего 5 сигналов, следовательно, понадобятся 3-значные коды, X-бит входного сигнала).
|
Х1 |
Х2 |
Х3 |
х0 – положили 2 рубля |
0 |
0 |
0 |
х1 – положили 5 рублей |
0 |
0 |
1 |
х2 – положили иную монету |
0 |
1 |
0 |
x3 – положили гнутую монету |
0 |
1 |
1 |
х4 – сигнал «напиток готов» |
1 |
0 |
0 |
|
|
|
|
Предыдущие состояния q (всего 4 состояния, следовательно, понадобятся 2х-значные коды b1,b2-биты предыдущего состояния).
|
b1 |
b2 |
q0 – ожидание монеты |
0 |
0 |
q1 – приготовление чая |
0 |
1 |
q2 – приготовление кофе |
1 |
0 |
q3 – состояние неисправности |
1 |
1 |
Следующие состояния q (всего 4 состояния, следовательно, понадобятся 2х-значные коды B1,B2-биты предыдущего состояния).
|
B1 |
B2 |
q0 – ожидание монеты |
0 |
0 |
q1 – приготовление чая |
0 |
1 |
q2 – приготовление кофе |
1 |
0 |
q3 – состояние неисправности |
1 |
1 |
Выходные сигналы Y (всего 5 сигналов, следовательно, понадобятся 3х-значные коды Z1, Z2 Z3- биты выходных сигналов).
|
Z1 |
Z2 |
Z3 |
y0 – готовит чай |
0 |
0 |
0 |
y1 – готовит кофе |
0 |
0 |
1 |
у2 – выбрасывает монету в лоток |
0 |
1 |
0 |
y3 – сигнал «автомат неисправен» |
0 |
1 |
1 |
y4 - сигнал «положите монету» |
1 |
0 |
0 |
Кодированная таблица переходов и выходов
|
Входной сигнал |
Текущее состояние |
Следующее состояние |
Выходной сигнал |
||||||
|
X1
|
X2 |
X3 |
b1 |
b2 |
B1 |
B2 |
Z1 |
Z2 |
Z3 |
x0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
- |
- |
- |
- |
- |
|
0 |
0 |
0 |
1 |
0 |
- |
- |
- |
- |
- |
|
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
|
x1 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
- |
- |
- |
- |
- |
|
0 |
0 |
1 |
1 |
0 |
- |
- |
- |
- |
- |
|
0 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
|
x2 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
- |
- |
- |
- |
- |
|
0 |
1 |
0 |
1 |
0 |
- |
- |
- |
- |
- |
|
0 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
|
x3 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
- |
- |
- |
- |
- |
|
0 |
1 |
1 |
1 |
0 |
- |
- |
- |
- |
- |
|
0 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
|
x4 |
1 |
0 |
0 |
0 |
0 |
- |
- |
- |
- |
- |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
|
1 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
|
1 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |