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

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

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

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

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

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

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

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

D_QX, на множество Q (q_p = (q_j, x_j), q_pQ);

 - функция выходов, реализующая отображение множества D_ D_QX, на множество Y (y_d = (q_j, x_i), y_d  Y);

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

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

Автомат называется конечным, если конечны множества Q, X и Y. Автомат называетсяполностью определённым,если D_=D_=QX; участичногоавтомата функциииопределены не для всех пар (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)=(q(p), x(p)). Во-вторых, состояниеq(p+1) в следующем, (p+1)-м такте, однозначноопределяется состояниемq(p) и входной переменнойx(p) в рассматриваемом такте -q(p+1)=(q(p), x(p)).

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

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

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

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

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

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

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

q(t+1) =(q(t),x(t));y(t) =(q(t),x(t)),t= 0, 1, 2, ..., (2.11)

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

q(t+1) =(q(t),x(t));y(t) =(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)=(q(p)), гдеq(p)=(q(p-1),x(p-1)));

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

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

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

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

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

Для примера табл. 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=(q_i,x_k) при некоторомx_kX. В случае автомата Мили дуге графа приписываются входной символx_kи выходной символy_g=(q_i,x_k), Если некоторые состояния автомата не определены, то в соответствующих клетках таблицы ставится прочерк; в этом случае автомат являетсячастичным. Если переходq_iq_jпроисходит под действием нескольких входных символов, то дуге (q_i,q_j) приписываются все эти входные и соответствующие выходные символы. При описании автомата Мура в виде графа выходной символy_g=(q_j) записывается рядом с вершинойq_j (или внутри неё).

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