2. Методика выполнения

Используя материал из раздела 1, по ГСА, заданной преподавателем, разработать программу моделирования конечного автомата

1. Разработать алгоритм моделирования конечного автомата.

2. Разработать структуру данных

3. Составить программу функционирования конечного автомата

4. Исследовать поведение автомата на построенной модели

3. ЗАДАНИЕ НА ВЫПОЛНЕНИЕ РАБОТЫ

Согласно методике, изложенной в разделе 2, и краткой теории из раздела 1, по ГСА, заданной преподавателем, разработать программу моделирования конечного автомата. Исследовать поведение автомата на построенной модели. Результаты исследований оформить в виде отчета.

4. КОНТРОЛЬНЫЕ ВОПРОСЫ

1. Какие объекты и функции используются для описания закона функционирования конечного автомата?

2. Какие правила необходимо соблюдать при моделировании конечного автомата?

3. Какое различие между структурными автоматами и автоматами Мили и Мура?

Лабораторная работа № 4

Исследование абстрактного автомата.

Цель лабораторной работы: Получение навыков исследования абстрактных автоматов.

1. Краткая теория

Тема 3.1. Определение абстрактного автомата. Соединение

двух автоматов: последовательное, параллельное и с обратной

связью.

Абстрактный автомат (АА) задается шестеркой (шестикомпонентным вектором):

- множество (алфавит) состояний;

- множество (алфавит) входных сигналов;

- множество (алфавит) выходных сигналов;

- функция переходов автомата. Функция паре ставит в соответствие некоторое состояние :

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

- начальное состояние АА.

Автомат называется конечным, если конечны множества , , .

В дальнейшем будем иметь в виду только конечные автоматы.

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

В рамках курса будем рассматривать как синонимы следующие термины:

• алфавит, буква, символ;

• слово, цепочка.

С мысл вышеприведенных терминов очевиден и не требует формальных определений.

АА имеет один вход и один выход:

Автомат работает в дискретном времени, принимающем значения

Всегда

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

На этом заканчивается один цикл работы автомата.

Последовательность символов входного алфавита: задает входное слово (слово входного алфавита).

Последовательность символов выходного алфавита задает выходное слово (слово выходного алфавита).

Работа АА состоит в преобразовании слов входного алфавита в слова выходного алфавита.

В АА отвлекаются от внутренней структуры автомата, рассматривая его как “черный ящик”. При этом основное внимание уделяется поведению автомата относительно внешней среды. В качестве элементов, связывающих автомат с внешней средой, выступают входные и выходные слова.

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

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

Основными видами соединений 2х автоматов являются:

• п араллельное;

• последовательное;

Параллельное соединение

Начальное состояние не выделено.

- функциональный преобразователь (автомат без памяти).

.

Результирующий автомат

1. - множество всевозможных пар вида ;

2. - входной алфавит автоматов и ;

3. - заданное отображение

4. Функция переходов определяется следующим образом:

, или по другому:

5. Функция выходов определяется следующим образом:

, или иначе:

.

Пример:

Построим автомат .

Построение таблиц:

Пример

Последовательное соединение:

, у которого:

1) , или

2)

3)

4) , определяется следующим образом:

или

5) , определяется следующим образом:

или

Пример:

- тот же, что при параллельном соединении.

Результирующим автоматом будет автомат , у которого

1)

2)

3)

4)

Здесь, например,

5)