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

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

1. Разработать алгоритм моделирования МСА.

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

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

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

4. Задание на выполнение работы

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

4. Контрольные вопросы

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

2. Какие правила необходимо соблюдать при объединении МСА?

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

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

Исследование автоматных языков описания цифровых автоматов

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

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

Тема 2.1. Автоматные языки описания цифровых автоматов.

Графы переходов, таблицы переходов и выходов

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

Рассмотрим примеры таблиц для автоматов Мили и Мура

Пример автомата Мили

Таблица переходов:						Таблица выходов:

На пересечении столбца и строки ставят: и .

Таблицы переходов и выходов могут быть объединены в единую совмещенную таблицу переходов и выходов:

Пример автомата Мура:

Автомат Мура задается одной отмеченной таблицей переходов:

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

Граф автомата – это ориентированный граф, вершинам которого соответствуют состояния автомата, а дугам – переходы.

Дуге , направленной от вершины к вершине приписывается (в модели Мили) входной сигнал и выходной сигнал , либо ставится прочерк.

В модели Мура выходной сигнал приписывается вершине, т.е. состоянию .

Автоматы и , заданные выше в виде таблиц, задаются следующими графами:

Функции заключительного состояния и заключительного выхода

Расширим функции и , определив их на множестве пар:

(состояние, входное слово)

Обозначим: - -е входное слово длиной символов;

- слово длиной нуль (пустое слово);

- множество всех конечных входных слов ненулевой длины: .

Функция заключительного состояния: на множестве определяется следующим образом:

1. для всех ;

2.

1) , если определена для всех ; ;

2) не определена в противном случае.

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

Функция заключительного выхода .

Модель Мура:

	, для , если определена
	Не определена, если не определена

Модель Мили:

	, , если определена
	Не определена, если не определена

Функция заключительного выхода – это выходной сигнал, который появляется в результате действия последнего символа цепочки :

• в модели Мура – это выходной сигнал отмечающий заключительное состояние;

• в модели Мили – это выходной сигнал, появляющийся на переходе в заключительное состояние.

Пример для автомата (Мили) введенного ранее.

Найдем

Решение

Последний переход , поэтому .

Реакция автомата

Реакция автомата в состоянии на входное слово - это цепочка выходных символов (выходное слово) вырабатываемая автоматом.

Для модели Мили:

	Не определена, если не определена.
	иначе:

Для модели Мура:

	Не определена, если не определена
	иначе:

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

Под реакцией автомата Мура в состоянии на входное слово понимается выходное слово длины , но сдвинутое на 1 такт автоматного времени сравнительно с выходным словом автомата Мили.