Категория
Информатика
Тип
контрольная работа
Страницы
5 стр.
Дата
04.04.2013
Формат файла
.html — Html-документ
Архив
327067.zip — 3.23 kb
  • minimizacija-konechnyx-avtomatov_327067_1.html — 16.65 Kb
  • Readme_docus.me.txt — 125 Bytes
Оцените работу
Хорошо  или  Плохо


Текст работы

Государственное Образовательное Учреждение Высшего Профессионального Образования

Московский Государственный Технологический Университет «СТАНКИН»

Кафедра «Компьютерные системы управления»

Учебный курс «Теория дискретных систем управления»



Контрольная работа

по теме: «Минимизация конечных автоматов»


Выполнила: студентка Богачев Д.С.

Принял: к.т.н., преп. Нежметдинов Р.А.



Москва, 2012 г.


Содержание


1.Исходные данные

. Составление треугольной таблицы

. Нахождение списка максимальных классов совместимости

. Составление списка простых классов совместимости

. Нахождение минимального замкнутого покрытия

. Таблица переходов и выходов минимального автомата

. Синтез конечного автомата

. Получение логических функций выходов конечного автомата

. Минимизация логических функций

. Синтез функциональной схемы

. Принципиальная электрическая схема

Список литературы


1. Исходные данные


Конечный автомат задан совмещенной таблицей переходов и выходов

а 1 a 2 a 3a 4 a 5 a 6 a 7 a 8a 9 z 5 /--/-а 5 /-а 5 /w 2 a 2 /- a 1 / w 1 a 6 /--/- а 2 /- z 2 a 1 / w 1 a 6 /--/ w 1 -/- a 1 /--/ w 2 -/- а 8 /-а 5 /- z 3-/--/--/--/--/-a 2 /--/-а 7 /-a 6 /- z 4-/--/- a 1 /-a 2 /-а 4 /--/-а 1 /--/-a 1 /-

Тип элемента памяти - D-триггер.


2. Составление треугольной таблицы


2х3VV4VVх5хххх6хVххх7хVхх2,6 1,4х81,86,8VV1,82,7V9хххххх2,6 х12345678



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} Ø

. Нахождение минимального замкнутого покрытия


Простые классыСостоянияПорожденные множества1234567891,41,82,62,76,85,65,7,8 xxxooo 02,6,8xxxxox02,4,8xxxoх2,3,8xxxo01,4,8 xxxxx 1,3,8xxxx02,7xxx7,9xxo07,8xx2,6 xxx 02,4xx04,8xx2,3xx3,8xx1,4xxx1,3 xx 5x9 x


Выбираем новые состояния:

{5,7,8} - b1

{1,4,8} - b2

{2,6} - b3

{1,3} - b4

{9} - b5


6. Таблица переходов и выходов минимального автомата


Используя замену простых классов на новые переменные из п.3, получаем следующую таблицу минимального автомата:


b1b2b3b4b5Z1b 3 /-b 1 /w 2 b 2( b 4) /w 1 b 1 /-b 3 /-Z2b 2 /-b 2 /w 1 b 3 /w 2 b 2( b 4) /w 1 b 1 /-Z3b 1 /-b 1 /-b 3 /--/-b 3 /-Z4b 2 /-b 3 /--/-b 2( b 4) /-b 2 /-



7. Синтез конечного автомата


Производим кодирование входов, выходов и состояний:


Входы:

Х 1 Х 2 Z 1 00 Z 2 01 Z 3 10 Z 4 11


Состояния:

t 1 t 2 t 3 b 1 000



Ваше мнение



CAPTCHA