Рубрики

Машины Мили и Мура в ТОС

Машины Мура: Машины Мура — это конечные автоматы с выходным значением, и их производительность зависит только от текущего состояния. Его можно определить как (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)

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

Давайте возьмем таблицу переходов мучного станка, показанного на рисунке 2.

Input=0Input=1
Present StateNext StateOutputNext StateOutput
q0q10q20
q1q10q21
q2q11q20

Таблица 1

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

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

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

Input=0Input=1
Present StateNext StateNext StateOutput
q0
q10
q11
q20
q21

Таблица 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. Аналогично, другие записи могут быть заполнены.

Input=0Input=1
Present StateNext StateNext StateOutput
q0q10q200
q10q10q210
q11q10q211
q20q11q200
q21q11q201

Таблица 3

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

Переход от машины Мура к машине Мили

Давайте возьмем машину Мура, показанную на рисунке 1, и ее таблица переходов показана в таблице 3.

Шаг 1. Построить пустую мучную машину, используя все состояния машины Мура, как показано в таблице 4.

 Input=0Input=1
Present StateNext StateOutputNext StateOutput
q0
q10
q11
q20
q21

Таблица 4

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

Input=0Input=1
Present StateNext StateOutputNext StateOutput
q0q10q20
q10q10q21
q11q10q21
q20q11q20
q21q11q20

Таблица 5

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

Input=0Input=1
Present StateNext StateOutputNext StateOutput
q0q100q200
q10q100q211
q11q100q211
q20q111q200
q21q111q200

Таблица 6

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

Input=0Input=1
Present StateNext StateOutputNext StateOutput
q0q100q200
q10q100q211
q20q111q200

Таблица 7

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

Примечание. Число состояний в машине Мили не может превышать количество состояний в машине Мура.

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

Выводит сумму текущего и предыдущего битов ввода.  

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

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

Рекомендуемые посты:

Машины Мили и Мура в ТОС

0.00 (0%) 0 votes