Белов А.Г. Теория автоматов

Подождите немного. Документ загружается.

Министерство образования и науки Российской Федерации

Дальневосточный институт коммуникаций

(ДВИК)

ТЕОРИЯ АВТОМАТОВ

Методические рекомендации и контрольные задания

для студентов заочной формы обучения вузов

Направление Информатика и вычислительная техника

Специальность Вычислительные машины, комплексы, системы и сети

Разработал доцент, к.т.н. А.Г.Белов

Одобрено Методическим Советом ДВИК

(Протокол МС № 01/07/04-/2007 от 12.04.2007)

Владивосток

2007

Методические рекомендации и контрольные задания по дисциплине

«Теория автоматов» составлены в соответствии с требованиями

Государственного образовательного стандарта высшего профессионального

образования по специальности «Вычислительные машины, комплексы, системы

и сети».

Одобрено Методическим Советом ДВИК (протокол МС № 01/07/04-2007

от 12.04.2007).

Председатель Совета проф., к.т.н. В.Л.Лосев

Разработал доц., к.т.н. А.Г.Белов

Рецензент проф. д.т.н. И.М.Орощук

(Тихоокеанский высший военно-морской институт им.С.О.Макарова)

1. ЦЕЛЬ И ЗАДАЧИ ДИСЦИПЛИНЫ

Целью изучения дисциплины является приобретение знаний и навыков в

вопросах применения теории автоматов для решения практических задач

компьютерной техники.

В задачи дисциплины входит:

- математическое моделирование цифровых автоматов,

- изучение связей автоматов с формальными языками и грамматиками,

- анализ способов задания и принципов построения цифровых автоматов,

- освоение методов и средств синтеза цифровых аппаратов.

2. ТРЕБОВАНИЯ К УРОВНЮ ОСВОЕНИЯ СОДЕРЖАНИЯ

ДИСЦИПЛИНЫ

Изучение дисциплины базируется на знаниях студентами дисциплин

«Дискретная математика», «Математическая логика и теория алгоритмов»,

«Программирование на языке высокого уровня», «Электротехника и

электроника», «Информатика».

В результате теоретического изучения дисциплины студент должен:

- иметь представление о месте и роли теории автоматов, алгоритмов и

языков при решении реальных задач компьютерной техники;

- знать основные понятия теории конечных автоматов, необходимую

терминологию, этапы абстрактного и структурного синтеза конечных

автоматов;

- знать элементы теории формальных языков.

В результате практического изучения дисциплины студент должен:

- уметь использовать изученную теорию при построении автоматов с

учетом специфики решаемых задач;

- иметь навыки синтеза и анализа конечных автоматов с комбинационными

схемами и памятью.

3. ОБЪЕМ ДИСЦИПЛИНЫ И ВИДЫ УЧЕБНОЙ РАБОТЫ

Полная и сокращенная заочные формы обучения (на базе среднего

(полного) общего образования и среднего профессионального

образования)

Виды учебной работы

Всего

часов

Распределение по курсам

1 2 3 4 5

Общая трудоемкость дисциплины 153

153

Лекции 8 8

Практические занятия

Лабораторные занятия

Всего самостоятельная работа, в том числе:

139

Курсовая работа

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

Рефераты

Изучение литературы 99 99

Вид итогового контроля (экзамен, зачет) экз. экз.

4. СОДЕРЖАНИЕ ДИСЦИПЛИНЫ

4.1. Содержание программы дисциплины

Введение

Предмет дисциплины, ее объем, содержание и связь с другими

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

исторический очерк развития и основное содержание теории автоматов, обзор

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

Раздел 1. Классификация и характеристики автоматов

Определение цифрового автомата. Абстрактная и структурная теория

автоматов. Модель дискретного преобразователя В.М.Глушкова. Основные

понятия теории автоматов: входной и выходной алфавиты, множества

состояний автомата, автоматные языки. Типы и математические модели

автоматов. Бесконечные и конечные автоматы.

Обобщения, модификации и подклассы конечных автоматов.

Конечные автоматы Мура и Мили (частичные конечные автоматы Мура и

Мили) и их эквивалентные преобразования. Автоматы с магазинной памятью.

Детерминированные и недетерминированные конечные автоматы. Автоматы

без памяти. Операционные и управляющие автоматы. Микропрограммные

автоматы (понятия микрооперации, микрокоманды, микропрограммы). Другие

виды автоматов.

Композиции автоматов (структурные автоматы). Структурная теория

автоматов и ее основные результаты.

Системы канонических уравнений и системы выходных функций

автоматов.

Задачи теории автоматов: синтез, анализ, полнота, минимизация,

эквивалентные преобразования. Эксперименты с автоматами.

Раздел 2. Формальные языки и грамматики

Задание автоматов различными формализованными (автоматными)

языками. Стандартные автоматные языки, задающие функции переходов и

выходов автоматов: таблицы переходов, матрицы переходов, диаграммы

переходов (графы), таблицы включений и т.д. Начальные автоматные языки:

язык регулярных выражений алгебры событий, язык операторных схем

алгоритмов, язык граф-схем алгоритмов.

Основные понятия теории формальных языков и грамматик,

классификация языков по Хомскому. Автоматы распознаватели и

преобразователи. Регулярные выражения и языки. Свойства регулярных

языков. Связь регулярных языков и конечных автоматов. Задача распознавания

и синтаксического анализа. Контекстно-свободные грамматики и языки, их

свойства. Связь абстрактных автоматов с формальными языками и

грамматиками.

Автоматы с магазинной памятью. Языки, допускаемые магазинным

автоматом. Эквивалентность магазинного автомата и контекстно-свободных

грамматик. Построение магазинного автомата по заданной грамматике.

Построение магазинного преобразователя, выполняющего синтаксический

разбор.

Машина Тьюринга. Техника программирования машин Тьюринга.

Расширения базовой машины Тьюринга. Машины Тьюринга с ограничениями.

Машины Тьюринга и компьютеры.

Назначение, характеристика, структура и способы представления сетей

Петри.

Раздел 3. Основные понятия и законы алгебры логики

Алгебра состояний. Логические функции (ЛФ) одной и двух переменных.

Контактная и бесконтактная реализация ЛФ.

Законы алгебры логики. Законы де Моргана. Обобщение Шеннона.

Дизъюнктивная и конъюнктивная нормальные формы. Конституенты нуля и

единицы. Совершенные дизъюнктивная и конъюнктивная нормальные формы.

Теорема разложения совершенной дизъюнктивной и совершенной

конъюнктивной нормальных форм. Принцип двойственности. Суперпозиция

ЛФ. Полная, максимальная и минимальная системы ЛФ.

Раздел 4. Синтез комбинационной схемы автомата

Этапы синтеза автоматов: системное, программно-Mлогическое,

техническое и технологическое проектирование.

Реализация комбинационной части автоматов комбинационной схемой

(КС). Логические элементы и их характеристики. Функциональная схема и

базис КС. Задание автоматов таблицей состояний. Использование условных

состояний автоматов.

Диаграмма ВейчаM-Mкарта Карно (КК). Составление КК по таблицам

истинности. Свойства КК. Соседние клетки КК. Получение по КК

алгебраических выражений ЛФ. Минимизация ЛФ с помощью КК.

Представление КК бòльшего числа переменных через сумму КК меньшего

числа переменных.

Пример синтеза КС посредством КК.

Раздел 5. Синтез автоматов с памятью

Абстрактный синтез автоматов: представление автоматов на стандартном

языке на основе их задания на начальном языке. Минимизация автоматов,

заданных на стандартном языке.

Канонический метод структурного синтеза автоматов. Теорема о

структурной полноте В.М.Глушкова. Основные этапы структурного синтеза

автоматов. Обобщенные структурные схемы автоматов с памятью.

Представление функционирования автомата в виде прямой таблицы переходов

и выходов. Проблема отражения времени при проектировании схем автоматов:

синхронные, асинхронные и апериодические схемы. Кодирование внутренних

состояний автомата для синхронных и асинхронных автоматов с учетом

сложности КС и с учетом гонок в автоматах. Учет неиспользованных кодовых

групп. Использование метода прямого кодирования и применение элементов

памяти для кодирования состояний автомата. Выбор элементов памяти.

Построение функций возбуждения элементов памяти и функций выходов

автомата.

Пример синтеза автомата на основе таблицы переходов и КК.

Синтез автоматов на основе циклограмм. Понятия и определения.

Составление алгебраических выражений по циклограммам. Проверки

реализуемости циклограмм.

Пример синтеза автомата по циклограмме.

Заключение

Связь разделов курса. Перспективы использования основных положений

теории автоматов для построения системного программного обеспечения и

систем логического управления.

4.2. Содержание лабораторных занятий

Минимизация ЛФ. Построение бесконтактных и релейно-контактных схем

автомата.

Синтез КС автомата по заданным условиям ее функционирования.

Исследование КС на стенде-тренажере.

Стандартные способы задания автоматов с памятью.

Синтез автомата с памятью по заданному графу.

Исследование автоматов с памятью на стенде-тренажере.

Синтез автоматов по циклограмме.

Моделирование автоматов c использованием компьютерных программ

Electronics Workbench v5.12 и Electronics Workbench Multisim 7.

4.3. Темы рефератов (для студентов полной и сокращенной заочных форм

обучения)

1. Понятие об информации и ее преобразованиях. Преобразование

алфавитной информации.

2. Основные понятия теории формальных грамматик.

3. Концепция порождения и распознавания. Распознающие и

порождающие формальные грамматики.

4. Способы задания автоматов.

5. Основные понятия и определения теории абстрактных автоматов.

Абстрактный синтез автомата.

6. Структурный синтез автомата: задачи синтеза, канонический метод

структурного синтеза.

7. Элементарные автоматы с памятью (триггерные устройства) и их

свойства.

8. Кодирование внутренних состояний автомата.

9. Методы анализа и синтеза КС.

10. Управляющие и операционные автоматы.

11. Способы описания алгоритмов и микропрограмм.

12. Структурный синтез микропрограммных автоматов Мура и Мили.

13. Гонки в автоматах и способы их устранения.

4.4. Распределение часов по разделам дисциплины

4.4.1. Полная и сокращенная заочные формы обучения (на базе среднего

(полного) общего и среднего профессионального образования)

Наименование раздела дисциплины Всего

Аудиторные занятия

Самост.

работа

Лекции

Лаборат.

занятия

Практич.

занятия

Раздел 1. Классификация и характерис-

тики автоматов

Раздел 2. Формальные языки и

грамматики

2 29

Раздел 3. Основные понятия и законы

алгебры логики

Раздел 4. Синтез комбинационной

схемы автомата

2 27

Раздел 5. Синтез автоматов с памятью 30

2 27

Всего 153

6 139

5. УЧЕБНО-МЕТОДИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ

5.1. Рекомендуемая литература

5.1.1. Основная литература:

1. Хопкрофт Д., Мотвани Р., Ульман Д. Введение в теорию автоматов,

языков и вычислений. М.: Вильямс, 2002 – 528 с.(21. pdf )

2. Карпов Ю.Г. Теория автоматов: Учебник для вузов. СПб.: Питер, 2003 –

208 с.

3. Лазарев В.Г., Пийль Е.И. Синтез управляющих автоматов. М.:

Энергоатомиздат, 1989 – 327 с.

4. Савельев А.Я. Прикладная теория цифровых автоматов: Учебник для

вузов. М.: Высшая школа, 1987 – 272 с.

5.1.2. Дополнительная литература:

1. Гилл А. Введение в теорию конечных автоматов. М.: СП ЭКОМ, 1966 –

272 с.

2. Глушков В.М., Трахтенброт Б.А. Введение в теорию конечных автоматов.

М.: СП ЭКОМ, 1962 – 384 с.

3. Глушков В.М. Синтез цифровых автоматов. М.: Физматгиз, 1962 – 476 с.

4. Лазарев В.Г., Маркин Н.П., Лазарев Ю.В. Проектирование дискретных

устройств автоматики: Учебное пособие для вузов связи. М.: Радио и

связь, 1985 – 168 с.

5. Миллер Р. Теория переключательных схем. Т.M1. Комбинационные схемы.

М: Наука, 1970 – 416 с.

6. Миллер Р. Теория переключательных схем. Т.M2. Последовательностные

схемы и машины. М: Наука, 1971 – 304 с.

7. Проектирование бесконтактных управляющих логических устройств

промышленной автоматики /Грейнер Г.Р., Ильяшенко В.П., Май В.П. и

др. М.: Энергия, 1977 – 384 с.

8. Широков Л.А. Исследование систем управления. Учебное пособие. М.:

МГИУ, 1999.-123с. (43. pdf )

9. Кузнецов А.П. Теория автоматического управления. Учебное пособие.

Минск: Дизайн-ПРО, 2002.-352с. (141. pdf )

10.Белов А.Г. Теория автоматов. Методические рекомендации и

контрольные задания для студентов заочной формы обучения вузов.

Владивосток: ДВИК, 2007. - 20 с.

5.2. Задания на контрольные работы (для студентов полной и сокращенной

форм заочного обучения)

В соответствии с учебным планом студенты должны выполнить по данной

дисциплине две контрольные работы по конкретному варианту задания.

Студент-заочник до начала установочной сессии выбирает вариант

задания, номер которого совпадает с последней цифрой номера зачетной

книжки, и, выполнив его, отправляет почтой на проверку в ДВИК.

Студент, не приступивший к выполнению расчетно-графического задания

до начала сессии, получает вариант задания у преподавателя дисциплины из

дополнительного списка.

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

Синтез комбинационной схемы автомата

1. По заданной таблице истинности, описывающей функционирование КС

автомата, построить КК. Таблицу истинности, соответствующую своему

варианту, взять из таблицыM1.

2. По КК получить алгебраические выражения ЛФ, описывающих КС

автомата, в двух формах:

а) в дизъюнктивной форме, получаемой по единичным контурам КК;

б) в конъюнктивной форме, получаемой по нулевым контурам КК;

в) по единичным и нулевым контурам с учетом условных (безразличных)

состояний ~ .

3. Проверить правильность полученных ЛФ.

4. По одному из полученных выражений построить КС автомата:

а) на логических элементах ИM–MНЕ;

б) на логических элементах ИЛИM–MНЕ.

Таблица 1

Варианты таблиц истинности

0 1 2 3 4

a b c x a b c x a b c x a b c x a b c x

0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0

0 0 1 1 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0

0 1 0 0 0 1 0 ~ 0 1 0 0 0 1 0 0 0 1 0 1

0 1 1 0 0 1 1 ~ 0 1 1 0 0 1 1 1 0 1 1 ~

1 0 0 ~ 1 0 0 1 1 0 0 0 1 0 0 1 1 0 0 ~

1 0 1 0 1 0 1 1 1 0 1 0 1 0 1 0 1 0 1 1

1 1 0 1 1 1 0 0 1 1 0 1 1 1 0 0 1 1 0 0

1 1 1 0 1 1 1 0 1 1 1 ~ 1 1 1 ~ 1 1 1 0

5 6 7 8 9

a b c x a b c x a b c x a b c x a b c x

0 0 0 1 0 0 0 1 0 0 0 ~ 0 0 0 ~ 0 0 0 0

0 0 1 0 0 0 1 ~ 0 0 1 ~ 0 0 1 1 0 0 1 0

0 1 0 1 0 1 0 0 0 1 0 1 0 1 0 0 0 1 0 0

0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0

1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 1 1 0 0 ~

1 0 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1

1 1 0 0 1 1 0 1 1 1 0 0 1 1 0 1 1 1 0 1

1 1 1 ~ 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 0

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

Синтез автомата с памятью

1. По заданному графу переходов построить исходную таблицу переходов.

Граф, соответствующую своему варианту, взять из таблицыM2.

2. Выбрать дополнительные переменные, ввести промежуточные состояния,

построить измененную таблицу переходов.

3. Построить общую КК для дополнительных и выходных переменных.

4. Построить отдельные КК для каждой из переменных, по которым в

соответствии с методом простого кодирования получить алгебраические

выражения для соответствующих выходных и дополнительных переменных.

Построить схему автомата, используя логические элементы И, ИЛИ, ИM–MНЕ,

ИЛИM-MНЕ.

5. Применив в качестве кодирующих элементов RSM–Mтриггеры и используя

таблицу переходов RSM–Mтриггера построить для каждой переменной КК, в

клетках которой проставить значения функции возбуждения элемента

памяти. Получить алгебраические выражения для входов S и R триггеров