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

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

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

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

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_j), y_dÎY);

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

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

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

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

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

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

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

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

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

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

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

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

Следует отметить, что в начальный момент t =0 автомат всегда находится в начальном состоянии q (0) =q₁. В последующие моменты р,КА в зависимости от входного символа х (р)Î Х выдает на выходе соответствующий выходной сигнал y (p) =l (q (p), x (p)), переходя в состояние q (p +1)=d(q(p), х(р)); q(p)ÎQ, y(p)ÎY.

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

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

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

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)

Рис. 2.1. Конечный автомат: а - автоматное время;

б - структура; в - автомат Мили; г - автомат Мура

 

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

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

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

3) автомат Мили содержит меньшее число состояний, чем эквивалентный ему автомат Мура.

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

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

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

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

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

A1 x1 x2 q1 q2/y1 q3/y2 q2 q3/y3 — q3 q1/y3 q2/y1

A2 x1 x2 q1/y1 q2 q3 q2/y1 q3 q1 q3/y2 q3 q1

 

Граф автомата – ориентированный связный граф, вершины которого соответствуют состояниям, а дуги – переходам между ними. Две вершины графа автомата q_i и q_j соединяются направленной дугой от q_i — исходного состояния к q_j — состояние перехода. В случае автомата Мили дуге графа приписывается входной символ x_k и выходной символ y_g =l(q_i, х_k). При описании автомата Мура в виде графа выходной символ y_g =l(q_i) записывается рядом с вершиной q_j (или внутри неё).

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

 

Рис. 2.2. Пример графа частичного автомата Мили

Рис. 2.3. Пример графа автомата Мура

2.3.2. Машина Тьюринга, её свойства и особенности

 

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

• машина должна быть полностью детерминированной и действовать в соответствии с заданной системой правил;

• машина должна допускать ввод различных начальных данных, соответствующих различным задачам из заданного класса задач;

• заданная система правил работы машины и класс решаемых задач согласованы так, чтобы всегда можно было "прочитать" результат работы машины.

Предложены различные конструкции машин, способные выполнять алгоритмы. Наиболее наглядную конструкцию предложил английский математик Тьюринг (рис. 2.4,а).

Машина содержит бесконечную одномерную ленту, которая разделена на ячейки. Считается, что лента бесконечна лишь в одном направлении (вправо), так что существует ячейка, про которую можно сказать, что она нулевая (самая левая). В каждой ячейке может быть записан лишь один символ х_i из конечного алфавита Х={x₀, x₁,..., х_n}; символ x₀ выделяется специально: если в некоторой ячейке записан символ х ₀, то эта ячейка "пустая". В дальнейшем будем считать, что непустых символов на ленте каждый раз имеется конечное (но сколь угодно большое) число, остальные ячейки – пустые. Символом # отмечается левый конец ленты.

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

Головка может также по команде uÎU = {R, L, S} перемещаться на одну позицию вправо (R-Right) или влево (L-Left), если она не находится в самой левой ячейке, либо не перемещаться (S-Stop). Команды на головку подаются от управляющего устройства, которое в свою очередь получает от головки сигнал о наличии того или иного символа в ячейке ленты, расположенной под головкой.

Управляющее устройство (УУ) машины Тьюринга – это конечный автомат, который имеет конечное число состояний (m +1)из множества Q = { q ₀, q ₁ ,..., q_m) и работает в дискретном времени t = 0,1,2.... Структурная схема УУ как автомата приведена на рис 2.4,б; здесь F1, F2, F3 – комбинационные схемы (преобразователи дискретной информации без памяти); D1, D2 - элементы задержки символа (сигнала) на один такт.

Рис. 2.4. Машина Тьюринга: а - конструкция; б - структура

 

Нетрудно видеть, что блоки F1, D1, F2 образуют автомат Мили (рис. 2.1,б), который формирует новый символ х, хÎХ, для записи на ленте, а дополнительные к ним блоки F3, D2 формируют команду uÎU на перемещение головки.

Рассмотрим функционирование машины Тьюринга.

Входным данным для УУ является символ х_i, считываемый головкой с текущей ячейки с номером l.

Выходными данными для УУ являются: символ х_k, который головка должна записать в ячейку, а также команда и из алфавита U.

Пусть в момент t головка находилась напротив второй ячейки l, в которой был записан символ х_i, а управляющее устройство находилось в состоянии q_j. УУ в зависимости от пары символов (q_j, x_i) выдаёт символ х_k, (т.е. головка стирает старый символ х_i и записывает новый символ x_k), a затем – один из символов перемещения головки R, L, S. После этого УУ переходит в новое состояние q_r (также однозначно определяемое парой символов (q_j, х_i,)). Тем самым в момент t +1 в ячейке l будет записан символ x_k, УУ будет находиться в состоянии q_r, а головка может находиться справа или слева ячейки l, либо над ней.

Важно отметить, что МТ работает последовательно, т.е. последовательно обрабатывает ячейку за ячейкой (данные, записанные в них) в зависимости от команд, формируемых УУ.

Функционирование машины Тьюринга осуществляется в соответствии с так называемой функциональной схемой, в каждой клетке которой записывается тройка символов: символ нового состояния, новый входной символ, а также символ команды на перемещение головки.

Каждую строку функциональной схемы можно рассматривать как условный оператор с множеством альтернатив, определяемых значением входного символа, а имя строки (данное состояние машины) – как метку этого оператора. Тогда вся функциональная схема (ФС) представляет собой программу функционирования МТ.

Если функциональная схема МТ задана, то при каждом заполнении ленты работа машины однозначно определена.

Далее будем считать, что символ q₀ состояния УУ означает состояние покоя МТ, т.е. строка q ₀ФС обладает следующими свойствами:

•первым символом в каждой клетке этой строки всегда является q ₀;

•вторым символом в клетке столбца х _i, этой строки является символ х_j;

•третьим символом в каждой клетке строки является символ S.

Поэтому, если УУ в какой-то момент имеет состояние q ₀, то где бы ни находилась головка и каким бы ни было заполнение ленты, в последующий момент времени УУ будет оставаться в том же состоянии. Для упрощения записи ФС строка q ₀ в ней опускается.

В дальнейшем для простоты будем предполагать, что алфавит символов X состоит из двух символов: "пустого" - 0 и "не пусто" -1.

Рассмотрим несколько примеров МТ. Начальным состоянием машины здесь и далее будем считать состояние q ₁; рассмотренные в этих примерах машины имеют по одному состоянию (не считая состояния покоя).

 

Таблица 2.4 Таблица 2.5 Таблица 2.6 Таблица 2.7

A     q1 q01S q11R

B     q1 q10L q00L

C     q1 q00L q11L

D     q1 q’00S q”01S

 

Пример 2.4. Машина А (табл. 2.4). Если в начальный момент машина воспринимает заполненную ячейку, то она "отыскивает" на ленте первую пустую (т.е. заполненную символом 0 ячейку) справа от той, под которой находится головка, вписывает туда символ 1 и останавливается. Если вначале головка находится напротив пустой ячейки, то машина её "заполняет" и останавливается, не передвигая головку.

Пример 2.5. Машина В (табл. 2.5) "стирает" единицу в той ячейке, над которой находится головка (если ячейка не пустая), передвигает головку влево и останавливается. Если в начальный момент ячейка под головкой пустая, то машина передвигает головку влево до тех пор, пока не найдёт заполненную ячейку, очищает её, передвигает головку влево и останавливается.

Пример 2.6. Машина С (табл. 2.6), отправляясь от заполненной ячейки, идёт влево и останавливается левее группы единиц на две ячейки.

Пример 2.7. Машина D (табл. 2.7), имея два состояния покоя, распознает, напротив какой ячейки находится, - пустой либо заполненной; в зависимости от этого переходит в первое либо второе состояние покоя.

В некоторых случаях МТ может быть недоопределена в том смысле, что не все ячейки её ФС заполнены. Это допускается в тех случаях, когда можно заранее сказать, что некоторые сочетания состояний машины и символов на ленте по тем или иным причинам никогда не встречаются.

Иногда МТ может иметь несколько состояний покоя: q^’₀, q’’₀, q’’’₀ ....