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

Используя материал из раздела 1, по описанию алгоритма выполнения некоторой операции, заданному преподавателем разработать программу моделирования автомата с магазинной памятью (МП).

1. Разработать алгоритм моделирования машины автомата с магазинной памятью.

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

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

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

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

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

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

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

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

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

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

Исследование автомата с жесткой логикой.

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

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

Структурный синтез автомата с жесткой логикой

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

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

1. Сигналы структурного выходного алфавита как функции от сигналов структурного входного алфавита и сигналов структурного алфавита состояний автомата;

2. Внутренние сигналы автомата как функции сигналов и .

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

П - элемент памяти, представляющий собой элементарный автомат Мура.

- вектор состояния автомата, заданный символами структурного алфавита состояний.

- вектор функций управления элементами возбуждения элементов памяти автомата.

- вектор выходных сигналов, заданный символами структурного выходного алфавита .

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

Переход отдельного элемента памяти из состояния в состояние происходит следующим образом: , т.е. под действием сигнала .

Компоненты вектора зависят от:

1. кодирования выходных сигналов абстрактного алфавита;

2. состояния автомата, т.е. от вектора ;

3. для автомата Мили – от вектора .

Поэтому сигналы выходного алфавита могут быть описаны в виде булевых функций:

…

Компоненты вектора зависят:

1. от кодов , ;

2. от особенностей элементов памяти - от особенностей функции переходов автомата Мура, реализованного в виде отдельного элемента памяти.

Сигналы алфавита также могут быть заданы в виде булевых функций:

…

В качестве элементарных автоматов Мура, используемых как элемент памяти автомата будем использовать триггера различных типов ( -, -, -, - триггера).

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

Кодирование ГСА и разметка состояний автомата. Построение

графа переходов и таблиц переходов и выходов.

Процесс синтеза автомата зависит от следующих факторов:

• от критерия синтеза:

  • минимум оборудования;

  • максимум быстродействия;

• от типа автомата (Мили, Мура);

• от элементной базы;

• от способа кодирования состояний.

Синтез осуществляется в несколько этапов:

1. Разметка ГСА

2. Построение таблиц переходов

3. Получение логических функций для выходных сигналов и функций возбуждения.