- •Воронежский государственный технический университет
- •(Часть 1) Учебное пособие
- •Глава 1. Становление теории автоматов и ее основные задачи
- •Взаимосвязь теории автоматов и других научно-технических направлений
- •Подходы к определению конечного автомата.
- •Сущность метода "черного ящика".
- •Основные задачи теории автоматов
- •Глава 2. Формальная классификация абстрактных автоматов и их математические модели.
- •2.1 Словесные определения автоматов.
- •2.4.3 Модель совмещенного автомата (с-автомата)
- •2.4.4 Модель микропрограммного автомата
- •Глава 3 Структурные модели первого уровня абстрактных автоматов
- •3.1. Структурная модель автомата Мили
- •3.2. Структурная модель автомата Мура
- •3.3 Структурная модель с - автомата
- •3.4 Структурная модель микропрограммного автомата
- •Глава 4. Способы задания абстрактных и структурных автоматов.
- •Глава 5 Минимизация абстрактных автоматов
- •Глава 6. Математические основы алгебры логики
- •Теоремы алгебры логики
- •6.4.1 Словесная форма представления логических функций
- •6.4.3 Аналитическая форма представления логических функций
- •6.4.4 Геометрическая и кубическая формы представления
- •2.4.3 Модель совмещенного автомата………………25
- •Глава 5 Минимизация абстрактных автоматов……………..58
- •Глава 6. Математические основы алгебры логики……...…70
- •Учебное издание
- •394026 Воронеж, Московский просп.,14
С. В. ТЮРИН
ЭЛЕМЕНТЫ ТЕОРИИ АВТОМАТОВ
(Часть 1)
УЧЕБНОЕ ПОСОБИЕ
ВОРОНЕЖ 2002
МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ
ФЕДЕРАЦИИ
Воронежский государственный технический университет
ЭЛЕМЕНТЫ ТЕОРИИ АВТОМАТОВ
(Часть 1) Учебное пособие
Воронеж 2002
УДК 519.713(075)
Тюрин С.В. Элементы теории автоматов (Часть 1): Учебное пособие. Воронеж: Воронеж. гос. техн. ун-т, 2002. 98 с.
Рассматриваются основные задачи теории автоматов; различные словесные определения автоматов и их формальная классификация; математические и структурные модели типовых автоматов; способы задания абстрактных и структурных автоматов; вопросы минимизации абстрактных автоматов.
Изложены математические основы алгебры логики, некоторые понятия и определения, дающие возможность формального описания логических преобразователей (комбинационных автоматов), которые являются основой всех конечных автоматов, включая последовательностные (автоматы с памятью).
Учебное пособие предназначено для студентов технических вузов, обучающихся по специальности 220100 "Вычислительные машины, комплексы, системы и сети".
Учебное пособие подготовлено на магнитном носителе в текстовом редакторе MS WORD 97.0 и содержится в файле "Элементы ТА.doc).
Табл. 16. Ил. 35. Библиогр.: 21 назв.
Научный редактор д-р техн. наук С.Л. Подвальный
Рецензенты: кафедра автоматизированных систем управле- ния Военного института радиоэлектроники (начальник кафедры канд. техн. наук М.И. Чурсин);
д-р техн. наук Н.И.Баранников
Издается по решению редакционно-издательского совета Воронежского государственного технического университета.
© Тюрин С.В., 2002
© Оформление. Воронежский государственный технический университет, 2002
ВВЕДЕНИЕ
Объектами профессиональной деятельности инженеров по специальности 220100 "Вычислительные машины, комплексы, системы и сети" являются "способы и методы проектирования, производства и эксплуатации аппаратных и программных средств вычислительной техники, применяемых в различных областях" [Государственный образовательный стандарт высшего профессионального образования. - М:, 1995г.].
Одной из общих профессиональных дисциплин по специальности 220100 является "Теория автоматов". Изложение материалов этой теории базируется на содержании таких дисциплин как "Дискретная математика", "Математическая логика", "Основы алгоритмизации и программирования". Содержание самой "Теории автоматов" наиболее тесно связано с такими дисциплинами, как "Схемотехника ЭВМ", "Микропроцессорные системы", "Организация ЭВМ, комплексов и систем", "Системное программное обеспечение".
Рождение теории автоматов как самостоятельного научно - технического направления относят к 1950 году. Естественно, что за прошедшие более чем 70 лет трудом многих талантливых ученых и инженеров накоплен огромный объем общих и специфических знаний, совокупность которых и объединяют понятием - теория автоматов. В данном пособии предпринята попытка взаимоувязано изложить лишь элементы теории автоматов, необходимые и достаточные для подготовки студентов к самостоятельному углублению знаний в данной предметной области, а также к практическому применению полученных знаний по синтезу и анализу комбинационных и последовательностных автоматов малой сложности.
У
3
4
В данной части пособия рассматриваются основные понятия абстрактной и структурной теории автоматов, а также различные языки задания автоматов. Изложены математические основы алгебры логики и ее применение для формального описания комбинационных и последовательностных автоматов.