• Автоматы. Абстрактные, структурные и микропрограммные автоматы

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

·     Способы построения синхронных, асинхронных и апериодических автоматов.

·     Структурные модели конечных автоматов при их реализации на ПЛИС.

 

Конечные автоматы

Автомат – идеализированное устройство, работающее в идеализированном дискретном времени t = 0,1,2,3,… В каждый момент этого времени на входах и выходах формируется некоторый алфавит, т.е. непустые множества.

Упорядоченная последовательность символов или букв образует слово в данном входном или выходном алфавите.

Различают автоматы:

·     Абстрактные

·     Структурные

·     Микропрограммные

·     М-автоматы

Абстрактные автоматы

Абстрактный автомат – устройство с одним входом и одним выходом. Автомат описывается следующим множеством элементов:

Z = {z1,z2,…   zk},

W = {w1,w2, …   wp},

A = {a1,a2,…    am},

φ  функция переходов в следующий момент автоматного времени (t+1):

φ(z, at) Þat+1

ψ — функция выходов:

ψ(z,a) ÞW,

a1 – начальное состояние автомата (t = 0).

Этот набор параметров называется кортеж.

Начальное состояние автомата а1, безусловно, принадлежит множеству А:

a1 ÎA; 

a1 = A|t=o.

Несколько определений.

Комбинационые автоматы – это подкласс абстрактных автоматов с одним внутренним состоянием, т.е. в этих схемах нет памяти. Автоматы с памятью называются последовательностными.

Автомат называется конечным и детерминированным, если конечны множества A, W, Z и переходы между ними однозначны, т.е. только в одно состояние под действием одного и того же входного сигнала (слова, алфавита).

Автомат называется инициальным, если выделено начальное состояние.

Автомат называется полностью определенным, если область определения функции ψ совпадает с областью определения множества возможных пар вида {A,W}.

Задать автомат – значит, описать все элементы кортежа {W, Z, A, ψ, j, a1}.

Известны два способа: табличный и графический.

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

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

Ссылка на основную публикацию
Adblock detector