Как начинался компьютер
Компьютерная революция
Двоичный код
Разработки военных лет
Интегральные микросхемы
Микрокомпьютер
Персоны
Сеть
Язык компьютера
Развитие ПО
Гибкие системы
Средства разработки
Информатика
Вычислительная наука
Операционные системы
Искусственный интеллект
Предыстория
Поиск
Знания и рассуждения
Логика
Робототехника
 

 
Конечный автомат Печать

В ЭВМ преобразование информации выполняется логическими схемами, которые подразделяются на два класса:

  1. комбинационные схемы, или автоматы без памяти;
  2. последовательностные схемы, или автоматы с памятью.

Существует синтез комбинационных (или логических) схем. Каждому набору (комбинации) входных сигналов х1, х2, ...xL комбинационной схемы соответствует определенная комбинация выходных сигналов y1, y2, ..., yn, ..., yN, являющаяся выходной функцией (L — число входов комбинационной схемы, N — число ее выходов).

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

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

Абстрактным автоматом называют дискретный преобразователь информации с конечным входным алфавитом Z = {z1,..., zf,...,zF}, конечным выходным алфавитом W = {w1,..., wg,...,wG}, конечным множеством внутренних состояний A = {a1,..., am,...,aM} и двумя характеристическими функциями: функцией переходов δ и функцией выходов λ.

Алфавит есть конечное множество попарно различимых символов, которые называются буквами этого алфавита. Алфавит, как любое множество, задается перечислением его элементов, т.е. символов. Примеры алфавитов: A = {α, β, γ, *, ψ}; B = {x, y, z}; 

Абстрактный автомат имеет один входной и один выходной каналы. Функционирование автомата происходит в дискретные моменты автоматного времени, ход которого обозначается натуральными числами i = 0, 1, 2, ...

В каждый момент дискретного времени t автомат находится в определенном состоянии a(t) = am, воспринимает на входном канале некоторую букву входного алфавита z(t) = zm (входной сигнал), выдает на выходном канале некоторую букву выходного алфавита w(t) = wg (выходной сигнал), определяемую функцией выходов λ как w(t) = λ(a(t), z(t)) или wg = h(am, zf), и переключается в новое состояние a(t + 1) = as, которое определяется функцией переходов δ как а(t + 1) = δ(a(t), z(t)) или as = δ(am, zf).

Абстрактный автомат называется конечным, так как множества A, Z, W конечны. Кроме того, он называется полностью определенным, если для любой пары (am, zf) определены функции δ и λ. У частичного автомата функции δ и λ определены не для всех пар (аm, zf). При рассмотрении функционирования автомата считается, что исходным состоянием в момент t = 0 является а(0)=а1, которое называется начальным состоянием.

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

В зависимости от способа определения значений выходных сигналов различают два типа автоматов.

Автоматами первого типа или автоматами Мура называют такие автоматы, в которых выходной символ w(t) не зависит явно от входного символа z(t) а определяется внутренним состоянием автомата в момент времени t. Иначе говоря, автоматы Мура описываются системой уравнений:

a(t + 1)  = δ(a(t), z(t));

ω(t) = λ(a(t)).

Другой тип автоматов составляют автоматы Мили, у которых функции переходов и выходов описываются следующей системой уравнений:

a(t + 1)  = δ(a(t), z(t))

ω(t)  = λ(a(t), z(t))

Таким образом, в автомате Мили выходной сигнал (буква выходного алфавита) и момент автоматного времени t зависит как от внутреннего состояния автомата в момент t, так и от входного сигнала (буквы входного алфавита) в момент t.

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

В показанных ниже таблицах (таблица переходов) и (таблица выходов) приведен пример задания автомата Мили, у которого А = {а1, a2, а3, а4}; Z = {z1, z2, z3}; W = {w1, w2, w3}.

z(t)\a(t)a1
a2
a3
a4
z1
w1
w1
w2
w1
z2
w2
w2
w3
w1
z3
w3
w1
w2
w4

 

 z(t)\a(t)a1
a2
a3
a4
z1
a1 
a3 
a3 
a3 
z2 
a4 
a1 
a4 
a2 
z3 
a2 
a3 
a4 
a1 

Строки таблиц отмечены входными сигналами, а столбцы — состояниями. Крайний левый столбец таблиц отмечается начальным состоянием автомата а1. Входные сигналы и состояния, отмечающие строки и столбцы таблиц, относятся к моменту времени t, т. е. отражают z(t) и a(t). На пересечении столбца a(t) = am и строки z(t) = zf в таблице переходов указывается состояние a(t + 1) = as, определяемое функцией переходов as = δ(am, zf). В состояние as автомат переключается из состояния аm под действием сигнала zf. В таблице выходов на пересечении столбца a(t) = аm и строки z(t) = zf ставится соответствующий тому переходу выходной сигнал w(t) = wg, определяемый функцией выходов wg = λ(am, zf).

По таблицам можно проследить последовательность работы автомата. И начальный момент времени t = 0 автомат находится в исходном состоянии a(0) = a1. Если на входном канале в момент t = 0 будет действовать, к примеру, буква z(0) = z2, то автомат сформирует на выходном канале букву w2 = w(0) = λ(a(0), z(0)) и следующий момент времени t = 1 переключится в новое состояние a4 = a(1) = δ(a(0),z(0)).

В момент времени t = 1 автомат, находясь в состоянии a(1) = a4, может воспринять, на входном канале любую букву множества Z, например z(1) = z2. Тогда автомат сформирует на выходном канале букву w1 = w(1) = λ(a(1), z(1)) и в следующий момент времени t = 2 переключится в новое состояние a2 = a(2) = δ(a(1), z(1)) и т. д. Таким образом, если на вход автомата, предварительно установленного в начальное состояние а1, подавать в последовательные моменты времени t = 0, 1, 2, ... некоторую последовательность букв входного алфавита z(0), z(1), z(2), ... (входное слово), то на выходе автомата будут последовательно появляться буквы выходного алфавита w(0), w(1), w(2), ... (выходное слово); при этом автомат будет переключаться в состояния a(1), a(2), а(3), .... Выходное слово называется также реакцией автомата на входное слово.