Конечные автоматы могут иметь выходные данные, соответствующие каждому переходу. Существует два типа конечных автоматов, которые генерируют вывод:
- Мили Машина
- Мур машина
Мили Машина
Мили-машина — это FSM, выход которого зависит от текущего состояния, а также от текущего ввода.
Он может быть описан набором 6 (Q, ∑, O, δ, X, q 0 ), где —
-
Q — конечное множество состояний.
-
∑ — это конечный набор символов, называемый входным алфавитом.
-
O — это конечный набор символов, называемый выходным алфавитом.
-
δ — функция входного перехода, где δ: Q × ∑ → Q
-
X — функция выходного перехода, где X: Q × ∑ → O
-
q 0 — начальное состояние, из которого обрабатывается любой вход (q 0 ∈ Q).
Q — конечное множество состояний.
∑ — это конечный набор символов, называемый входным алфавитом.
O — это конечный набор символов, называемый выходным алфавитом.
δ — функция входного перехода, где δ: Q × ∑ → Q
X — функция выходного перехода, где X: Q × ∑ → O
q 0 — начальное состояние, из которого обрабатывается любой вход (q 0 ∈ Q).
Таблица состояний Мили-машины показана ниже —
| Современное состояние | Следующее состояние | |||
|---|---|---|---|---|
| вход = 0 | вход = 1 | |||
| государственный | Выход | государственный | Выход | |
| → а | б | х 1 | с | х 1 |
| б | б | х 2 | d | х 3 |
| с | d | х 3 | с | х 1 |
| d | d | х 3 | d | х 2 |
Диаграмма состояния вышеупомянутого Мили Машины —
Мур машина
Машина Мура является автоматом, выход которого зависит только от текущего состояния.
Машина Мура может быть описана набором из 6 (Q, ∑, O, δ, X, q 0 ), где —
-
Q — конечное множество состояний.
-
∑ — это конечный набор символов, называемый входным алфавитом.
-
O — это конечный набор символов, называемый выходным алфавитом.
-
δ — функция входного перехода, где δ: Q × ∑ → Q
-
X — функция выходного перехода, где X: Q → O
-
q 0 — начальное состояние, из которого обрабатывается любой вход (q 0 ∈ Q).
Q — конечное множество состояний.
∑ — это конечный набор символов, называемый входным алфавитом.
O — это конечный набор символов, называемый выходным алфавитом.
δ — функция входного перехода, где δ: Q × ∑ → Q
X — функция выходного перехода, где X: Q → O
q 0 — начальное состояние, из которого обрабатывается любой вход (q 0 ∈ Q).
Таблица состояний машины Мура показана ниже —
| Современное состояние | Следующее состояние | Выход | |
|---|---|---|---|
| Вход = 0 | Вход = 1 | ||
| → а | б | с | х 2 |
| б | б | d | х 1 |
| с | с | d | х 2 |
| d | d | d | х 3 |
Диаграмма состояний вышеуказанной машины Мура —
Мили машина против Мура машины
В следующей таблице выделены точки, которые отличают машину Мили от машины Мура.
| Мили Машина | Мур машина |
|---|---|
| Выход зависит как от текущего состояния, так и от текущего ввода | Выход зависит только от текущего состояния. |
| Как правило, в нем меньше состояний, чем в Moore Machine. | Как правило, он имеет больше состояний, чем Мили Машина. |
| Значение функции выхода является функцией переходов и изменений, когда логика ввода в текущем состоянии выполнена. | Значение выходной функции является функцией текущего состояния и изменений по краям часов, когда бы ни происходили изменения состояния. |
| Мили машины реагируют быстрее на входы. Они обычно реагируют в одном и том же тактовом цикле. | В машинах Мура для декодирования выходов требуется больше логики, что приводит к большим задержкам в цепи. Обычно они реагируют на один такт позже. |
Мур машина в Мили машина
Алгоритм 4
Вход — машина Мура
Выход — Мили Машина
Шаг 1 — Возьмите пустой формат таблицы переходов Mealy Machine.
Шаг 2 — Скопируйте все переходные состояния машины Мура в этот формат таблицы.
Шаг 3 — Проверьте текущие состояния и их соответствующие выходы в таблице состояний машины Мура; если для состояния Q i вывод равен m, скопируйте его в выходные столбцы таблицы состояний Mealy Machine везде, где Q i появляется в следующем состоянии.
пример
Давайте рассмотрим следующую машину Мура —
| Современное состояние | Следующее состояние | Выход | |
|---|---|---|---|
| а = 0 | а = 1 | ||
| → а | d | б | 1 |
| б | d | 0 | |
| с | с | с | 0 |
| d | б | 1 | |
Теперь мы применяем алгоритм 4, чтобы преобразовать его в Mealy Machine.
Шаг 1 и 2 —
| Современное состояние | Следующее состояние | |||
|---|---|---|---|---|
| а = 0 | а = 1 | |||
| государственный | Выход | государственный | Выход | |
| → а | d | б | ||
| б | d | |||
| с | с | с | ||
| d | б | |||
Шаг 3 —
| Современное состояние | Следующее состояние | |||
|---|---|---|---|---|
| а = 0 | а = 1 | |||
| государственный | Выход | государственный | Выход | |
| => а | d | 1 | б | 0 |
| б | 1 | d | 1 | |
| с | с | 0 | с | 0 |
| d | б | 0 | 1 | |
Мили машина для машины Мура
Алгоритм 5
Ввод — Мили Машина
Выход — машина Мура
Шаг 1 — Рассчитайте количество различных выходов для каждого состояния (Q i ), которые доступны в таблице состояний машины Мили.
Шаг 2 — Если все выходы Qi одинаковы, скопируйте состояние Q i . Если он имеет n различных выходов, разбейте Q i на n состояний как Q, где n = 0, 1, 2 …….
Шаг 3 — Если выходные данные начального состояния равны 1, вставьте новое начальное состояние в начале, которое дает 0 выходных данных.
пример
Давайте рассмотрим следующую машину Мили —
| Современное состояние | Следующее состояние | |||
|---|---|---|---|---|
| а = 0 | а = 1 | |||
| Следующее состояние | Выход | Следующее состояние | Выход | |
| → а | d | 0 | б | 1 |
| б | 1 | d | 0 | |
| с | с | 1 | с | 0 |
| d | б | 0 | 1 | |
Здесь состояния «a» и «d» дают только 1 и 0 выходных сигналов соответственно, поэтому мы сохраняем состояния «a» и «d». Но состояния ‘b’ и ‘c’ дают разные результаты (1 и 0). Итак, мы разделим b на b 0 , b 1 и c на c 0 , c 1 .