Главная » Файлы » Методички » Теория автоматов [ Добавить материал ]

Теория автоматов: учебное пособие томского политехнического университета

[Скачать с сервера (225.6Kb) - бесплатно] 04.04.2010, 03:42
Триханов А.В. Теория автоматов: Учебное пособие. – Томск: Изд. ТПУ, 1999. - 103 с.

В пособии изложены основы прикладной теории автоматов применительно к компьютерам: общие сведения об автоматах (основные определения, обозначения, свойства и характеристики автоматов,  типы автоматов, отношения между автоматами, "0”, ”1” алгебры автоматов и др.), способы задания (описания) автоматов, операции над автоматами (композиция автоматов, декомпозиция автомата, алгебраические операции, проверка отношений, упрощение автомата), законы и тождества алгебры автоматов. Описаны основные подпрограммы преобразования автоматов, изложены вопросы синтеза и анализа логических схем управляющих автоматов с жесткой логикой, вопросы контроля и диагностирования работы автоматов. Пособие подготовлено на кафедре вычислительной техники ТПУ и предназначено для студентов специальности 220100 "Вычислительные машины, системы, комплексы и сети” Центра дистанционного образования.


Печатается по постановлению Редакционно – издательского Совета Томского политехнического университета


Рецензенты:

Коваленок С.И. - к.т.н., доцент кафедры телевизионных устройств Томского университета автоматизированных систем управления и радиоэлектроники;

Прищепа Л.С.    - к.т.н., доцент кафедры конструирования вычислительной аппаратуры Томского университета автоматизированных систем управления и радиоэлектроники

©  Томский политехнический университет, 1999



Фрагменты из пособия:

ВВЕДЕНИЕ

Учебное пособие посвящено учебному курсу "Теория автоматов". В пособии рассматриваются общие сведения об автоматах, способы задания (описания) автоматов, операции над автоматами с законами и тождествами алгебры автоматов, вопросы синтеза логических схем, вопросы контроля и диагностирования работы автоматов, синтез управляющих цифровых автоматов с жесткой логикой.

Над цифровыми автоматами, как и над другими объектами дискретной математики, могут выполняться операции композиции, декомпозиции (формирование булеана объекта, разбиение, покрытие, проверка разбиения, проверки покрытия), алгебраические операции (объединение, вычитание, симметрическая разность, дополнение, пересечение), проверка отношений между объектами, упрощение (на основе тождеств, на основе учета сохраняемости логических условий).

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

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

Это сдерживает развитие данной теории, не дает ей возможностей утвердиться в качестве полнокровной теории.

Известные операции в достаточной степени не формализованы, не унифицированы и не стандартизированы, что затрудняет их использование при решении конкретных задач с объектами дискретной математики. Совершенно не затрагиваются вопросы законов и тождеств алгебры автоматов, возможность которой даже не упоминается.

Таким образом, насущной задачей является проработка в более полном объеме операционного инструментария для преобразований автоматов, что несомненно окажет благотворное влияние на решение вопросов теоретической кибернетики, в том числе теории математических машин, программирования, искусственного интеллекта.

На кафедре вычислительной техники Кибернетического центра ТПУ с 1975 года ведутся работы по разработке инструментария для преобразования различных объектов дискретной математики, имеется определенный задел по преобразованию цифровых автоматов, логических схем.

Инструментарий для кубов и кубических покрытий (кубический под-ход), описанный в [14], оказался полезным для проработки процедур преобразования объектов, которым посвящено данное пособие. Естественно, при разработке, унификации процедур преобразований объектов будет использоваться теоретико-множественный подход.

Кроме того, применяется алгоритмический подход как со стороны вида деятельности, так и формы труда, что способствует улучшению процесса познания.

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

1.3. Об операциях над автоматами, о законах и тождествах алгебры автоматов

Над цифровыми автоматами, как и над другими объектами дискретной математики, могут выполняться разнообразные операции.

Все операции можно разделить на следующие пять групп:
  • группу операций декомпозиции;
  • группу операций композиции;
  • группу алгебраических операций;
  • группу операций проверки отношения между автоматами;
  • группу операций упрощения автомата.

В первую группу входят операции формирования булеана (множества всех подавтоматов) автомата, разбиения и покрытия автомата, проверки разбиения и покрытия.

Группа вторая включает в себя операции различного соединения автоматов: последовательного, параллельного соединений и соединения с обратной связью.

В группу алгебраических операций входят операции объединений, вычитания, симметрической разности, дополнения, пересечения.

Группа четвертая включает в себя операции проверки отношений между автоматами. В эту группу входит операция проверки равенства автоматов.

Упрощать автоматы можно на основе тождеств алгебры автоматов, на основе учета сохраняемости логических условий.

Все законы обычной алгебры справедливы и в алгебре автоматов, однако распределительный закон имеет в ней  и вторую форму (форму распределения "слагаемого” относительно "произведения”).

Имеющуюся форму распределительного закона в обычной алгебре следует называть формой распределения "произведения” относительно "слагаемого”.

Все тождества  алгебры алгоритмов действуют в алгебре автоматов. В системе тождеств выделяются группы:
  1. тождеств отдельных операций;
  2. тождеств склеивания;
  3. тождеств поглощения;
  4. тождеств Порецкого;
  5. тождеств де Моргана;
  6. тождеств для общих "множителя” и "слагаемого” совершенного ранга.
Похожие материалы:

Добавил: COBA (04.04.2010) | Категория: Теория автоматов
Просмотров: 8681 | Загрузок: 835 | Рейтинг: 0.0/0 |
Теги: теория автоматов
Комментарии (2)
0   Спам
1. imwasonly21whenidied   22.05.2010   19:37
вместо лекций по автоматам Кузнецова пойдет? или еще что-нибудь прочитать? порекомендуйте плиз
0   Спам
2. COBA   22.05.2010   21:48
А где же ты учишься, если не секрет?
У нас вот теории автоматов как таковой не было, а эти лекции лежали в аудитории А200а...

Имя *:
Email *:
Код *: