Машины Мили и Мура в TOC

Машины Мура: машины Мура - это конечные автоматы с выходным значением, и его выход зависит только от текущего состояния. Его можно определить как (Q, q0, ∑, O, δ, λ), где:

• Q — конечное множество состояний.
• q0 — начальное состояние.
• ∑ — входной алфавит.
• O - выходной алфавит.
• δ - функция перехода, которая отображает Q × ∑ → Q.
• λ — выходная функция, отображающая Q → O.

фигура 1

В машине Мура, показанной на рисунке 1, выходные данные представлены каждым входным состоянием, разделенным символом /. Длина вывода для машины Мура больше, чем ввод на 1.

• Вход: 11
• Переход: δ (q0,11)=> δ(q2,1)=>q2
• Выход: 000 (0 для q0, 0 для q2 и снова 0 для q2)

Машины Мили: Машины Мили также являются конечными автоматами с выходным значением, и его выход зависит от текущего состояния и текущего входного символа. Его можно определить как (Q, q0, ∑, O, δ, λ'), где:

• Q — конечное множество состояний.
• q0 — начальное состояние.
• ∑ — входной алфавит.
• O - выходной алфавит.
• δ - функция перехода, которая отображает Q × ∑ → Q.
• «λ» — выходная функция, отображающая Q × ∑ → O.

фигура 2

В машине Мили, показанной на рис. 1, выходные данные представлены каждым входным символом для каждого состояния, разделенным символом /. Длина вывода для мучной машины равна длине ввода.

• Вход: 11
• Переход: δ (q0,11)=> δ(q2,1)=>q2
• Выход: 00 (переход с q0 на q2 имеет выход 0, а переход с q2 на q2 также имеет выход 0)

ПРИМЕЧАНИЕ :

Если в машине Мили есть n входов, то она генерирует n выходов, а если в машине Мура n входов, то она генерирует n + 1 выходов.

Преобразование из машины Мили в машину Мура

Возьмем переходную таблицу машины мучного, показанную на рисунке 2.

Таблица 1

Шаг 1. Сначала найдите те состояния, с которыми связано более 1 выхода. q1 и q2 — это состояния, с которыми связаны оба выхода 0 и 1.

Шаг 2. Создайте два состояния для этих состояний. Для q1 два состояния будут q10 (состояние с выходом 0) и q11 (состояние с выходом 1). Аналогично для q2 два состояния будут q20 и q21.

Шаг 3. Создайте пустую машину Мура с новым сгенерированным состоянием. Для машины Мура выход будет связан с каждым состоянием независимо от входных данных.

Таблица 2

Шаг 4. Заполните записи следующего состояния, используя таблицу переходов машины Мили, показанную в таблице 1. Для q0 на входе 0 следующим состоянием будет q10 (q1 с выходом 0). Точно так же для q0 на входе 1 следующим состоянием будет q20 (q2 с выходом 0). Для q1 (как q10, так и q11) на входе 0 следующим состоянием будет q10. Точно так же для q1 (как q10, так и q11) следующим состоянием является q21. Для q10 выход будет равен 0, а для q11 выход будет равен 1. Аналогичным образом можно заполнить и другие записи.

Таблица 3

Это переходная таблица машины Мура, показанная на рисунке 1.

Преобразование машины Мура в машину Мили

Возьмем машину Мура на Рисунке 1, а ее таблица переходов показана в Таблице 3. Шаг 1. Постройте пустую машину Мили, используя все состояния машины Мура, как показано в Таблице 4.

Таблица 4

Шаг 2: Следующее состояние для каждого состояния также можно найти непосредственно из таблицы переходов машины Мура как:

Таблица 5

Шаг 3: Как мы видим, вывод соответствует каждому входу в таблице переходов машины Мура. Используйте это, чтобы заполнить записи вывода. например; Выходные данные, соответствующие q10, q11, q20 и q21, равны 0, 1, 0 и 1 соответственно.

Таблица 6

Шаг 4: Как видно из таблицы 6, q10 и q11 похожи друг на друга (одинаковое значение следующего состояния и вывода для разных входных данных). Точно так же q20 и q21 также подобны. Итак, q11 и q21 можно исключить.

Таблица 7

Это та же машина для производства муки, которая показана в таблице 1. Таким образом, мы преобразовали машину для производства муки в машину Мура и обратно преобразовали Мур в машину для получения муки.

Примечание. Количество состояний в машине мучного не может быть больше, чем количество состояний в машине Мура.

Пример: Конечный автомат, описанный следующей диаграммой состояний с A в качестве начального состояния, где метка дуги — x / y, а x обозначает 1-битный ввод, а y обозначает 2-битный вывод? Выводит сумму текущего и предыдущего битов ввода.

1. Выводит 01 всякий раз, когда входная последовательность содержит 11.
2. Выводит 00 всякий раз, когда входная последовательность содержит 10.
3. Ни один из них.

Решение: возьмем разные входные и выходные данные и проверим, какой вариант работает:

Ввод: 01

Выход: 00 01 (для 0 выход равен 00, а состояние равно A. Затем для 1 выход равен 01, а состояние будет B)

Вход: 11

Выход: 01 10 (для 1 выход равен 01, а состояние — B. Затем для 1 выход равен 10, а состояние — C)

Как мы видим, это дает двоичную сумму текущего и предыдущего бита. Для первого бита предыдущий бит принимается равным 0.

Эта статья предоставлена Sonal Tuteja . Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсуждаемой выше.