Минимизация конечных автоматов
Государственное Образовательное Учреждение
Высшего Профессионального Образования
Московский Государственный Технологический
Университет «СТАНКИН»
Кафедра «Компьютерные системы управления»
Учебный курс «Теория дискретных систем
управления»
Контрольная работа
по теме: «Минимизация конечных автоматов»
Выполнила:
студентка Богачев Д.С.
Принял:
к.т.н., преп. Нежметдинов Р.А.
Москва, 2012 г.
Содержание
1.Исходные
данные
.
Составление треугольной таблицы
.
Нахождение списка максимальных классов совместимости
.
Составление списка простых классов совместимости
.
Нахождение минимального замкнутого покрытия
.
Таблица переходов и выходов минимального автомата
.
Синтез конечного автомата
.
Получение логических функций выходов конечного автомата
.
Минимизация логических функций
.
Синтез функциональной схемы
.
Принципиальная электрическая схема
Список
литературы
1. Исходные данные
Конечный автомат задан совмещенной таблицей
переходов и выходов
|
а1
|
a2
|
a3
|
a4
|
a5
|
a6
|
a7
|
a8
|
a9
|
z1
|
а5/-
|
-/-
|
а5/-
|
а5/w2
|
a2/-
|
a1/ w1
|
a6/-
|
-/-
|
а2/-
|
z2
|
a1/ w1
|
a6/-
|
-/ w1
|
-/-
|
a1/-
|
-/ w2
|
-/-
|
а8/-
|
а5/-
|
z3
|
-/-
|
-/-
|
-/-
|
-/-
|
-/-
|
a2/-
|
-/-
|
а7/-
|
a6/-
|
z4
|
-/-
|
-/-
|
a1/-
|
a2/-
|
а4/-
|
-/-
|
а1/-
|
-/-
|
a1/-
|
Тип элемента памяти - D-триггер.
2. Составление треугольной таблицы
2
|
х
|
|
|
|
|
|
|
|
3
|
V
|
V
|
|
|
|
|
|
|
4
|
V
|
V
|
х
|
|
|
|
|
|
5
|
х
|
х
|
х
|
х
|
|
|
|
|
6
|
х
|
V
|
х
|
х
|
х
|
|
|
|
7
|
х
|
V
|
х
|
х
|
2,6 1,4
|
х
|
|
|
8
|
1,8
|
6,8
|
V
|
V
|
1,8
|
2,7
|
V
|
|
9
|
х
|
х
|
х
|
х
|
х
|
х
|
2,6
|
х
|
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
|
|
|
|
|
|
|
|
|
3. Нахождение
списка максимальных классов совместимости
Используя треугольную таблицу, составляем список
максимальных классов совместимости:
) Ф=Х
) 7~8,9
Ф={7,8}{7,9}
3) 6~8
Ф={6,8}{7,8}{7,9}
4) 5~7,8
Ф={5,7,8}{6,8}{7,9}
5) 4~8
Ф={4,8}{5,7,8}{6,8}{7,9}
6) 3~8
Ф={3,8}{4,8}{5,7,8}{6,8}{7,9}
7) 2~8,7,6,4,3
Ф={2,3,8}{2,4,8}{5,7,8}{2,6,8}{7,9}{2,7}
8) 1~8,4,3
Ф={2,3,8}{2,4,8}{5,7,8}{2,6,8}{7,9}{2,7}{1,8,4}{1,8,3}
Ф={2,3,8}{2,4,8}{5,7,8}{2,6,8}{7,9}{2,7}{1,8,4}{1,8,3}
4. Составление списка простых
классов совместимости
{5,7,8}
|
2,6; 1,4; 1,8
|
{2,6,8}
|
2,7; 6,8
|
{2,4,6}
|
6,8
|
{2,3,8}
|
6,8
|
{1,3,8}
|
1,8
|
{1,4,8}
|
1,8
|
{2,7}
|
Ø
|
{7,9}
|
2,6
|
{5,7}
|
2,6; 1,4
|
{7,8}
|
Ø
|
{5,8}
|
1,8
|
{2,6}
|
Ø
|
{2,8}
|
6,8
|
{6,8}
|
2,7
|
{2,4}
|
Ø
|
{4,8}
|
Ø
|
{2,3}
|
Ø
|
{3,8}
|
Ø
|
{1,4}
|
Ø
|
{1,8}
|
1,8
|
{1,3}
|
Ø
|
{1}
|
Ø
|
{2}
|
Ø
|
{3}
|
Ø
|
{4}
|
Ø
|
{5}
|
Ø
|
{6}
|
Ø
|
{7}
|
Ø
|
{8}
|
Ø
|
{9}
|
Ø
|
. Нахождение минимального замкнутого
покрытия
Простые классы
|
Состояния
|
Порожденные множества
|
|
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
1,4
|
1,8
|
2,6
|
2,7
|
6,8
|
5,6
|
5,7,8
|
|
|
|
|
x
|
|
x
|
x
|
|
o
|
o
|
o
|
|
|
0
|
2,6,8
|
|
x
|
|
|
|
x
|
|
x
|
|
|
|
x
|
o
|
x
|
0
|
2,4,8
|
|
x
|
|
x
|
|
|
|
x
|
|
|
|
|
|
o
|
х
|
2,3,8
|
|
x
|
x
|
|
|
|
|
x
|
|
|
|
|
|
o
|
0
|
1,4,8
|
x
|
|
|
x
|
|
|
|
x
|
|
x
|
x
|
|
|
|
|
1,3,8
|
x
|
|
x
|
|
|
|
|
x
|
|
|
x
|
|
|
|
0
|
2,7
|
|
x
|
|
|
|
|
x
|
|
|
|
|
|
x
|
|
|
7,9
|
|
|
|
|
|
|
x
|
|
x
|
|
|
o
|
|
|
0
|
7,8
|
|
|
|
|
|
|
x
|
x
|
|
|
|
|
|
|
|
2,6
|
|
x
|
|
|
|
x
|
|
|
|
|
|
x
|
|
|
0
|
2,4
|
|
x
|
|
x
|
|
|
|
|
|
|
|
|
|
|
0
|
4,8
|
|
|
|
x
|
|
|
|
x
|
|
|
|
|
|
|
|
2,3
|
|
x
|
x
|
|
|
|
|
|
|
|
|
|
|
|
|
3,8
|
|
|
x
|
|
|
|
|
x
|
|
|
|
|
|
|
|
1,4
|
x
|
|
|
x
|
|
|
|
|
|
x
|
|
|
|
|
|
1,3
|
x
|
|
x
|
|
|
|
|
|
|
|
|
|
|
|
|
5
|
|
|
|
|
x
|
|
|
|
|
|
|
|
|
|
|
9
|
|
|
|
|
|
|
|
|
x
|
|
|
|
|
|
|
Выбираем новые
состояния:
{5,7,8} - b1
{1,4,8} - b2
{2,6} - b3
{1,3} - b4
{9} - b5
6. Таблица переходов и выходов
минимального автомата
Используя замену простых классов на новые
переменные из п.3, получаем следующую таблицу минимального автомата:
|
b1
|
b2
|
b3
|
b4
|
b5
|
Z1
|
b3/-
|
b1/w2
|
b2(b4)/w1
|
b1/-
|
b3/-
|
Z2
|
b2/-
|
b2/w1
|
b3/w2
|
b2(b4)/w1
|
b1/-
|
Z3
|
b1/-
|
b1/-
|
b3/-
|
-/-
|
b3/-
|
Z4
|
b2/-
|
b3/-
|
-/-
|
b2(b4)/-
|
b2/-
|
7. Синтез конечного
автомата
Производим кодирование входов,
выходов и состояний:
Входы:
|
Х1
|
Х2
|
Z1
|
0
|
0
|
Z2
|
0
|
1
|
Z3
|
1
|
0
|
1
|
1
|
Состояния:
|
t1
|
t2
|
t3
|
b1
|
0
|
0
|
0
|
b2
|
0
|
0
|
1
|
b3
|
0
|
1
|
0
|
b4
|
0
|
1
|
1
|
b5
|
1
|
0
|
0
|
Выходы:
Функции возбуждения памяти
D-триггера
Переходы:
|
000
|
001
|
010
|
011
|
100
|
00
|
010
|
000
|
011
|
000
|
010
|
01
|
001
|
001
|
010
|
001
|
000
|
10
|
000
|
000
|
010
|
-
|
010
|
11
|
001
|
010
|
-
|
011
|
001
|
Выходы:
|
000
|
001
|
010
|
011
|
100
|
00
|
-
|
1
|
0
|
-
|
-
|
01
|
-
|
0
|
1
|
0
|
-
|
10
|
-
|
-
|
-
|
-
|
-
|
11
|
-
|
-
|
-
|
-
|
-
|
Таблицу переходов автомата соответствует таблице
возбуждения памяти синтезируемого автомата для D-триггера:
|
000
|
001
|
010
|
011
|
100
|
00
|
010
|
000
|
011
|
000
|
010
|
01
|
001
|
001
|
010
|
001
|
000
|
10
|
000
|
000
|
010
|
-
|
010
|
11
|
001
|
010
|
-
|
011
|
001
|
8. Получение
логических функций выходов конечного автомата
0=
;
1=0
;
Используя таблицу функции возбуждения памяти D-триггера,
получим следующие логические функции переходов конечного автомата:
φ10=
---------- φ
20=
;
φ30=
;
φ
11=
φ10
;
φ
21
= φ
20
φ
31=
φ 30
Минимизация логических функций
Для минимизации логических функций будем
использовать карты Карно. Y1()
|
|
|
|
|
|
|
|
|
|
*
|
*
|
*
|
|
*
|
|
*
|
|
|
|
|
|
|
*
|
*
|
1
|
|
|
|
*
|
*
|
|
*
|
*
|
|
|
|
|
*
|
1
|
|
*
|
*
|
*
|
|
y=
;
φ
2 = ;
φ
3= ;
10. Синтез функциональной схемы
совместимость автомат логический
конечный
11. Принципиальная электрическая
схема
Список литературы
1.
Никишечкин А.П. Теория дискретных систем управления. Учебное пособие. - М.: ИЦ
ГОУ МГТУ «Станкин», 2006 - 242 с.
.
Интегральные микросхемы: Справочник / Б.В. Тарабрин, Л.Ф. Лунин, Ю.Н. Смирнов и
др.; Под ред. Б.В. Тарабрина. - М.: Радио и связь, 1983 - 528 с., ил.