Материал: Ковригин Теория автоматов Лабораторный практикум 2012

УДК 004.3(076.5)

ББК 32.973я7 Т33

Теория автоматов. Лабораторный практикум: учебное пособие

/Под ред. Б.Н. Ковригина. М.: НИЯУ МИФИ, 2012. 192 с.

Авторы: Н.А. Дмитриев, А.А. Дюмин, М.Н. Ёхин, Б.Н. Ковригин, В.Г. Тышкевич, Л.И. Шустова, И.М. Ядыкин.

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

Предназначено для приобретения и закрепления практических навыков при использовании теории автоматов для разработки цифровых устройств и программного обеспечения. Сопутствующая задача это начальное изучение и освоение профессиональной САПР фирмы Xilinx, используемой на последующих трех семестрах.

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

Пособие подготовлено в рамках Программы создания и развития НИЯУ МИФИ

Рецензент канд. техн. наук Воронков А.Ф.

ISBN 978-5-7262-1781-9

© Национальный исследовательский ядерный университет «МИФИ», 2012

3

ВВЕДЕНИЕ

Конечные автоматы. Основные понятия и определения

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

построение систем ПО, включая лексические анализаторы компиляторов;

проектирование систем технической диагностики;

проектирование узлов и блоков ЭВМ и других вычислительных систем и устройств;

проектирование устройств промышленной автоматики и др. Общую теорию автоматов подразделяют на абстрактную и

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

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

4