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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Все операции можно разделить на следующие пять групп:

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

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

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

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

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

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

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

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

Все тождества  алгебры алгоритмов действуют в алгебре автоматов. В системе тождеств выделяются группы:

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