Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Конечный автомат

Читайте также:
  1. Автомат разгрузки золотникового типа
  2. Автоматизация бюджетирования на предприятии
  3. Автоматизация графических работ средствами AutoCAD
  4. Автоматизированное заполнение
  5. Автоматизированные банковские системы, их эволюция и структура
  6. Автоматизированные информац. технологии в биржевом деле
  7. Автоматизирующий конформизм

Конечный автомат может быть задан таблично или с помощью графа.

1) X={x1,x2,x3,…} – входной алфавит.

2) Y={Y1,Y2,…} – выходной алфавит.

3) Q={q1,q2,q3,q4} – алфавит состояния.

4) φ:

 

  q1 q2 q3 q4
x1 q3 q1 q4 q3
x2 q4 q3 q1 q2
x3 q2 q2 q2 q1

 

5) ψ:

 

  q1 q2 q3 q4
x1 Y1 Y2 Y1 Y1
x2 Y1 Y1 Y2 Y1
x3 Y2 Y2 Y1 Y2

 

 

Минимизация памяти автомата Мили.

В автомате Мили выход зависит от состояния и входа.

1) x={x1,x2}

2) y={y1,y2}

3)Q={q0,q1,q2,…q11}

4) φ:

 

  q0 q1 q2 q3 q4 q5 q6 q7 q8 q9 q10 q11
x1 q5 q11 q11 q6 q2 q6 q2 q9 q6 q0 q4 q1
x2 q4 q4 q5 q10 q8 q10 q5 q3 q5 q7 q8 q7

 

5) ψ:

 

  q0 q1 q2 q3 q4 q5 q6 q7 q8 q9 q10 q11
x1 Y1 Y1 Y2 Y2 Y1 Y2 Y1 Y1 Y2 Y2 Y2 Y2
x2 Y2 Y2 Y1 Y1 Y2 Y1 Y2 Y2 Y1 Y1 Y1 Y1

 

 

По таблице выходов разобьём состояние системы на одно эквивалентное.

Эквивалентное состояние {q0,q1,q4,q6,q7}=B1

Эквивалентное состояние {q2,q3,q5,q8,q9,q10,q11}=B2

 

Перестроим таблицу φ с учётом этих одноэквивалентных состояний.

 

 

  B1 B2
  q0 q1 q4 q6 q7 q2 q3 q5 q8 q9 q10 q11
x1 B2 B2 B2 B2 B2 B1 B1 B1 B1 B1 B1 B1
x2 B1 B1 B2 B2 B2 B2 B2 B2 B2 B1 B2 B1

 

 

Разбиваем таблицу на двухэквивалентное состояние.

В1 разбилось на 2 класса: С1, С2.

 

  С1 С2 С3 С4
  q0 q1 q4 q6 q7 q2 q3 q5 q8 q10 q9 q11
x1 C4 C4 C3 C3 C4 C2 C2 C2 C2 C2 C1 C1
x2 C2 C2 C3 C3 C3 C3 C3 C3 C3 C3 C2 C2

 

 

Разбиваем на трёхэквивалентное состояние.

 

  D1 D2 D3 D4 D5
  q0 q1 q4 q6 q7 q2 q3 q5 q8 q10 q9 q11
x1 D5 D5 D4 D4 D5 D2 D2 D2 D2 D2 D1 D1
x2 D2 D2 D4 D4 D4 D4 D4 D4 D4 D4 D3 D3

 

2этап:

 

Выберем произвольно из каждого класса D1,D2,D3,D4,D5 по одному состоянию.

Это будут состояния минимального автомата.

 

QM={q0,q4,q7q2,q9}

 

q1 q4 q2 q9

q0 q4 q7 > q7 q3 q2 q9

q0 q6 q5 q11

 

3 этап:

 

Удаляем из таблиц φ и ψ лишние состояния:

q1;q6;q3;q5;q8;q10;q11.

 

φM:

 

  q0 q4 q7 q2 q9
x1 q9 q2 q9 q4 q0
x2 q4 q8 q3 q5 q7

 

 

  q0 q2 q4 q7 q7
x1 Y1 Y2 Y1 Y1 Y2
x2 Y2 Y1 Y2 Y2 Y1

 

 

Минимизация памяти автомата Мура.

В автомате Мура выход не зависит от входа. Это всевозможные генераторы. Пятая составляющая отсутствует.

5.

                         
                         
                         

 

В остальном вся методика минимизации сохраняется.

Последовательность разбиения

D0={B1,B2}

B1={q0,q1,q4,q6,q7}

B2={q2,q3,q5,q8,q9,q10,q11}.

Заполняем таблицу φ:

 

  B1 B2
  q0 q1 q4 q6 q7 q2 q3 q5 q8 q9 q10 q11
x1 B2 B2 B2 B2 B2 B1 B1 B1 B1 B1 B1 B1
x2 B1 B1 B2 B2 B2 B2 B2 B2 B2 B1 B2 B1

 

C1={q0,q1}; C2={q4,q6};

C3={q7}; C4={q2,q3,q5,q8,q10};

C5={q9,q11}.

 

  C1 C2 C3 C4 C5
  q0 q1 q4 q6 q7 q2 q3 q5 q8 q10 q9 q11
x1 C5 C5 C4 C4 C5 C2 C2 C2 C2 C2 C1 C1
x2 C2 C2 C4 C4 C4 C4 C4 C4 C4 C4 C3 C3

 

 

q0 q4

q1 q4 q7 q7

q1 q6

 

 

q2

q3 q9

q5 q2 q9

q8 q11

q10

 

 

1) X={x1,x2};

2) Y={Y1,Y2};

3) QM={q0,q4,q7,q2,q9};

4) φM:

 

  q0 q4 q7 q2 q9
x1 q9 q4 q2 q9 q0
x2 q4 q2 q2 q2 q7

 

Дата добавления: 2015-08-21; просмотров: 80 | Нарушение авторских прав

Читайте в этой же книге: Принятие решения о работоспособности объекта | Получение уравнения гиперплоскости, проходящей через n заданных точек. | Сетевой график | Решение задачи о кратчайшем пути в графе на основе ЛП | Алгоритм построения всех остовных деревьев графа на основе полного перебора последовательности ребер или дуг | Алгоритм Прима определение минимального остовного дерева(случай многоуровнего графа) | Расчет сетевого графа на основе линейного программирования | Решение задачи коммивояжера | Алгоритм метода ветвей и границ |
<== предыдущая страница | следующая страница ==>
Минимизация булевых функций в классе КНФ (Конъюнктивная нормальная форма).| Алгоритм венгерского метода
mybiblioteka.su - 2015-2024 год. (0.014 сек.)