Модели дискретной обработки информации

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

Автомат - это математическая абстракция, которая предназначена для описания и анализа поведения разнообразных устройств дискретного действия или протекания процессов дискретной обработки информации, для моделирования и построения устройств и процессов. Такая модель успешно используется как в технике (проектирование вычислительных машин, систем управления и связи), так и в других областях деятельности человека - теории и практике административного управления, лингвистике (анализ синтаксиса формального языка, расшифровка древних рукописей) и т. д. Универсальность теории автоматов позволяет рассматривать с единой точки зрения различные объекты, учитывать связи и аналогии между ними, переносить результаты из одной области в другую.

Автомат описывается шестёркой элементов А=(Q, X, Y, d, l,q₁),

где Q = {q₁, q₂,..., q_r} - множество состояний (алфавит состояний);

X = {x₁, x₂,..., x_n} - множество входных символов (входной алфавит);

Y = {y₁, y₂,..., y_m} - множество выходных символов (выходной алфавит);

d - функция переходов, реализующая отображение множества D_d,

D_dÍQ´X, на множество Q (q_p = d(q_j, x_j), q_pÎQ);

l - функция выходов, реализующая отображение множества D_l, D_lÍQ´X, на множество Y (y_d = l(q_j, x_i), y_d Î Y);

q₁ - начальное состояние автомата.

В общем случае автомат может иметь некоторое количество входов и выходов, и тогда каждому входу и каждому выходу может соответствовать свой алфавит. Рассмотрим более простой случай автомата с одним входом и одним выходом.

Автомат называется конечным, если конечны множества Q, X и Y. Автомат называется полностью определённым, если D_d=D_l=Q´X; у частичного автомата функции d и l определены не для всех пар (q_j, x_i)ÎQ´Y.

Символами x_i и y_k обозначают события в процессе или сигналы в устройствах. Иногда используют вместо понятия “символ” понятие “буква”; а последовательность букв называют словом.

В отличие от привычного рассмотрения времени (время непрерывно и задается на континууме), при изучении и проектировании автоматов удобно рассматривать воображаемое дискретное время (автоматное время, заданное на счётном множестве). Разобьём непрерывную числовую полуось на бесконечное число конечных интервалов, не обязательно равных между собой, и обозначим точки, разделяющие интервалы, неотрицательными целыми числами, начиная с 0 (рис. 2.1,а).

Будем называть дискретным временем t время, которое принимает лишь эти целочисленные значения. Моменты времени, обозначенные числами 0,1,2,..., будем называть тактами.

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

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

При рассмотрении КА значения символов состояний и входов существенны лишь в моменты тактов и несущественны - в промежутках между ними. Поэтому эту модель можно использовать и для описания непрерывных устройств (процессов), если фиксировать значения символов состояний и входов в моменты тактов; при этом важно, чтобы в рассматриваемые дискретные моменты множество возможных состояний было конечным и чтобы удовлетворялось требование однозначной связи между состояниями в соседних тактах.

Понятие “состояние автомата” определяет некоторую предысторию его поведения как реакции на символы, которые поступали ранее на его входы, т. е. состояние соответствует некоторой памяти о прошлом.

Строгое определение понятия состояния связывается с той ролью, которую оно играет при определении конечных автоматов. Во-первых, значение выходной переменной на p-м такте (p-present-настоящее) y(p) однозначно определяется состоянием q(p) и значением входной переменной x(p) на том же такте, т. е. y(p)=l(q(p), x(p)). Во-вторых, состояние q(p+1) в следующем, (p+1)-м такте, однозначно определяется состоянием q(p) и входной переменной x(p) в рассматриваемом такте - q(p+1)=d(q(p), x(p)).

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

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

Термин “состояние” позволяет устранить время как явную переменную и выразить выходные символы как функцию состояний автомата и входов в данный момент (такт). В каждый момент t=0,1,2,... дискретного времени КА находится в определённом состоянии q(t) из множества Q состояний автомата, причём в начальный момент t=0 он всегда находится в начальном состоянии q(0)=q₁. В момент p (рис. 2.1,б), находясь в состоянии q(p), КА способен воспринять на входе символ x(p)ÎX и выдать на выходе сигнал y(p)=l(q(p), x(p)), переходя в состояние q(p+1)=d(q(p), x(p),); q(p)ÎQ, y(p)ÎY.

Таким образом, КА реализует некоторое отображение j множества слов входного алфавита X во множество слов выходного алфавита Y: если на вход автомата, установленного в начальное состояние q₁, подавать некоторую последовательность букв входного алфавита x(0), x(1), x(2),..., т. е. входное слово, то на выходе КА будут последовательно появляться буквы выходного алфавита y(0), y(1), y(2),..., т. е. выходное слово. Относя к каждому входному слову соответствующее ему выходное слово, получим отображение j, индуцированное конечным автоматом.

Автомат без памяти называется тривиальным автоматом, или комбинационной схемой. В таких автоматах значения выходных переменных определяются только комбинацией входных переменных в данный момент; для комбинационных схем функция переходов не имеет смысла, а функция выходов вырождается к виду y(p)=l(x(p)).

На практике наибольшее распространение получили автоматы Мили и Мура, приведенные на рис. 2.1,в и г; здесь: F1 и F2 - комбинационные схемы; D - задержка на один такт (память), q’ - новое (следующее) состояние в момент t = p.

Закон функционирования автомата Мили задается уравнениями:

q(t+1) = d(q(t), x(t)); y(t) = l(q(t), x(t)), t = 0, 1, 2, ..., (2.11)

а автомата Мура -

q(t+1) = d(q(t), x(t)); y(t) = l(q(t)), t = 0, 1, 2, ..., (2.12)

Отметим особенности функционирования автоматов Мили и Мура:

· оба автомата одинаково формируют новое состояние (q, x)®q’, которое затем задерживается на один такт, q(p+1) = q’(p);

· выходной символ в автомате Мили определяется непосредственно входным символом и состоянием в текущий момент t=p ((q, x)®y), а в автомате Мура - только состоянием в текущий момент (q®y) и опосредованно - состоянием и входным символом в предыдущий момент t=p-1 (y(p)=l(q(p)), где q(p)=d(q(p-1), x(p-1)));

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

· автомат Мили обычно проще (в смысле меньшего числа состояний) эквивалентного ему автомата Мура.

При анализе и синтезе КА используются в основном две стандартные формы представления автомата: табличная и графическая. Рассмотрим эти формы.

Автомат может быть представлен двумя таблицами для каждой из функций d и l либо совмещённой таблицей, несколько отличающейся для автоматов Мили и Мура.

При табличном представлении строки именуются символами состояний, а столбцы - символами входа; в клетках таблиц проставляются символы состояний, причём состояния записываются рядом через разделитель “/” с соответствующими выходными символами: для автомата Мили - в клетках, а для автомата Мура - в именующем столбце.

Для примера табл. 2.1 описывает поведение автомата Мили, а табл. 2.2 - автомата Мура.

Таблица 2.1 Таблица 2.2

A1	x1	x2		A2	x1	x2
q1	q2/y1	q3/y2	q1/ y1	q2	q4
q2	q3/y3	---	q2/y1	q5	q2
q3	q4/y3	q2/y1	q3/y3	q5	q2
q4	---	q2/y2	q4/y2	q3	q1
	q5/y3	q3	q1

Граф автомата - ориентированный связный граф, вершины которого соответствуют состояниям, а дуги - переходам между ними. Две вершины графа автомата q_i и q_j (исходное состояние и состояние перехода) соединяются дугой, направленной от q_i к q_j, если в автомате есть переход q_i®q_j, т. е. если q_j=d(q_i, x_k) при некотором x_kÎX. В случае автомата Мили дуге графа приписываются входной символ x_k и выходной символ y_g=l(q_i, x_k), Если некоторые состояния автомата не определены, то в соответствующих клетках таблицы ставится прочерк; в этом случае автомат является частичным. Если переход q_i®q_j происходит под действием нескольких входных символов, то дуге (q_i, q_j) приписываются все эти входные и соответствующие выходные символы. При описании автомата Мура в виде графа выходной символ y_g=l(q_j) записывается рядом с вершиной q_j (или внутри неё).

На рис. 2.2 и 2.3 приведены заданные ранее табл. 2.1 и 2.2 графы автоматов А1 (частичный автомат Мили) и А2 (автомат Мура; здесь переход q₂®q₂ является петлёй).