Реферат: К. Е. Карасёв Введение в теорию конечных автоматов

Министерство образования Российской Федерации
Московский государственный технический университет «СТАНКИН»
К.Е.Карасёв
Введение в теорию конечных автоматов


Учебное пособие

Москва, 2007




Предисловие
Данное пособие составлено на основе полугодового курса, прочитанного автором для студентов МГТУ «СТАНКИН» в 2005 и 2006 годах. В пособии представлены краткие теоретические сведения и задачи по таким основным разделам теории конечных автоматов, как: основы теории автоматов, теория экспериментов над автоматами, стохастические функции автоматов, реализация автоматов схемами, теория регулярных языков. С учётом особенностей учебной программы, в пособие также включены темы из смежных областей дискретной математики – синтез схем из функциональных элементов, теория алгоритмов (машина Тьюринга), теория рекурсивных функций. Также в пособие включены сведения, имеющие практическое применение в области программирования: регулярные выражения в современных языках программирования, понятие формальной грамматики.

Для изучения этого курса теории автоматов желательно наличие следующих предварительных знаний:

основы теории графов;

теория функций алгебры логики;

теория вероятностей, понятие цепи Маркова (для изучения стохастических функций автоматов).

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

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

Задачи и упражнения выделены полужирным шрифтом.

^ 1.Определение конечного автомата.
Определение. Конечным инициальным автоматом (или просто автоматом) называется шестёрка (A, Q, B, , , q0), где:

A – конечное множество произвольной природы, называемое входным алфавитом автомата (в дальнейшем под алфавитом будет пониматься конечное множество произвольной природы, его элементы будем называть символами);

Q – конечное множество, называемое алфавитом состояний автомата;

B – конечное множество, называемое выходным алфавитом автомата;

 – отображение :AXQ→Q, называемое функцией переходов автомата;

 – отображение :AXQ→B, называемое функцией выходов автомата;

q0 - элемент алфавита Q, называемый начальным состоянием автомата.

Это определение соответствует следующей математической модели. Некоторое устройство – конечный автомат – принимает сигналы, являющиеся символами алфавита A и выдаёт сигналы – символы алфавита B, при этом устройство принимает конечное число состояний, и сигнал на выходе определяется только сигналом на входе и состоянием автомата. Состояние автомата в сущности есть содержимое его памяти. Время в этой модели предполагается дискретным, переменная t принимает значения из множества натуральных чисел. Обозначим x(t) символ, принимаемый автоматом в момент времени t, y(t) – символ, выводимый автоматом, q(t) – состояние автомата в момент времени t. Эти функции от t связываются следующими соотношениями:



Эти соотношения называются уравнениями переходов и выходов автомата (первое – уравнение переходов, второе – уравнение выходов). Поскольку множества, на которых эти функции определены, конечны, эти функции (а следовательно, и весь автомат) можно описать таблицей. Назовём таблицу для функции таблицей переходов. Мы говорим, что символ x переводит автомат из состояния q в состояние q,x).

Другой подход к определению автомата – понятие ограниченно-детерминированной функции. Назовём словом в алфавите A произвольную конечную упорядоченную последовательность символов из этого алфавита. Множество всех слов в алфавите A обозначается A*. Пусть функция f:A*→B* отображает слова в алфавите A в слова в алфавите B. Функция называется детерминированной, если она, во-первых, сохраняет длину слова, и, во-вторых, если в двух словах в алфавите A совпадают первые n символов, то и в словах – образах этих слов при применении функции f – первые n символов совпадают. Условие детерминированности можно записать следующим образом: если ax1 и ax2 – два слова из A* с общим началом a , то f(axi)=byi , где b – общее начало длины, равной длине a, двух слов by1 и by2. Таким образом, для любого слова a существует функция fa:A*→B*, такая, что f(ax)=bfa(x). Функция fa также будет детерминированной: в самом деле, fa сохраняет длину слова, и, если fa(cx)=dy, то f(acx)=bdy, и если f(acx’)=bdy’, следовательно, fa(cx’)=dy’. Мы видим, что любая детерминированная функция f для каждого слова a из A* определяет детерминированную функцию fa, которая называется остаточной функцией функции f.

Определение. Если для всех слов a число различных остаточных функций fa конечно, то функция f называется ограниченно-детерминированной (сокращённо о.-д.) функцией.

^ Упражнение 1.1. Приведите пример детерминированной, но не ограниченно-детерминированной функции.

Каждому автомату с входным алфавитом A и выходным алфавитом B можно поставить в соответствие функцию f, переводящую слово =a(1)a(2)…a(t) в слово =b(1)b(2)…b(t), где t – переменная времени. В этом случае говорят, что автомат вычисляет функцию f. Справедливо следующее утверждение:

^ Функция, вычисляемая автоматом, является о.-д. функцией. Для любой о.-д. функции существует автомат, её вычисляющий.

Функцию, которую автомат вычисляет, обычно называют поведением автомата.

Если остаточные функции о.д. функции известны, то автомат можно построить, взяв в качестве множества состояний множество (множество классов эквивалентности) остаточных функций, взять функцию переходов, удовлетворяющую соотношению f, x)= fx и функцию выходов f, x)= fx).

Кроме таблиц наглядным способом изображения конечного автомата являются диаграммы переходов, или диаграммы Мура. Диаграмма Мура представляет собой ориентированный граф, каждая вершина которого соответствует состоянию автомата, а каждое ребро, идущее из вершины qi в вершину qj, соответствует значению функции переходов (x,qi)=qj . и помечено парой (x,(x,qi)), и, наоборот, для каждого значения аргументов функции переходов в диаграмме существует такое ребро. Обычно в вершины графа изображаются кругами, начальное состояние помечается звёздочкой. Пара (x,y) у ребра графа изображается без скобок через дробь: x/y.

Функция переходов автомата доопределяется до расширенной функции переходов автомата: пусть x=(x1,...,xk)∈A*, q1∈Q и (xi,qi)=qi+1. Тогда положим (x,q1)=qk+1 и будем говорить, что слово x переводит автомат из состояния q1 в состояние qi+1.

Упражнения. Приведённые ниже соотношения связывают последовательность входных символов автомата x(t)∈{0,1} и выходных у(t)∈{0,1}. Построить таблицу для функций переходов и выходов автомата, диаграмму Мура.

y(t)=x(t-1) & x(t-2), y(1)=y(2)=0.

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

Итак, состоянием автомата будет двоичный вектор q1q2=(q1,q2), связанный с входными символами соотношениями q1(t)=x(t-1), q2(t)=x(t-2). Соотношения можно переписать в виде q1(t+1)=x(t), q2(t+1)=q1(t). Для соответствия функции условиям y(1)=y(2)=0 дополним уравнения переходов значениями q1(0)=q2(0)=0. Функция выходов примет вид (x,q1,q2)=q1&q2.

Таблица функции переходов автомата примет следующий вид:

x

(00,x)

(01,x)

(10,x)

(11,x)

0

00

10

00

10

1

01

11

01

11


Диаграмма Мура автомата примет вид:




y(t)=x(1)→x(t)

y(t)=x(2)⋁x(t)

y(t)=x(t)&(x(t-1)⋁x(1)),x(0)=1

В автомат последовательно вводятся цифры натурального числа (рассмотреть два варианта – с начала и с конца). Автомат в каждый момент выводит остаток от деления уже введённого на этот момент числа на n, n<10. Покажите, что такой автомат существует. Постройте диаграмму Мура для n=2,3,4,5.

^ Приведённые ниже соотношения связывают последовательность входных символов автомата x(t)=( x1(t), x2(t))∈{0,1} и выходных у(t)∈{0,1}. Построить таблицу для функций переходов и выходов автомата, диаграмму Мура.

y(t)=x1(t-1)→x2 (t)

y(t)=x1(t)+ x2(t) x1(1)

y(t)=x1(1)&( x2(t) ⋁ x2(1))


Следующие задачи заключаются в моделировании конечными автоматами реально используемых технических устройств. (Конечно, наиболее яркие примеры – микроэлектронные устройства, от электронных часов до компьютера). Для решения задач следует перейти от модели с непрерывным временем к модели с дискретным. Можно считать n-ными (имеющими номер) те моменты времени, когда системе подаётся очередной сигнал. Также полезно понятие так называемого асинхронного автомата, функция переходов которого удовлетворяет соотношению (xx,q)=(x,q) – автомата, меняющего своё состояние только при изменении входного сигнала.

Смоделируйте конечным автоматом работу 4-значной железнодорожной автоблокировки. Путь двухпутной линии, предназначенный для движения в одном направлении, разделён светофорами на блок-участки – участки, на каждом из которых по требованиям безопасности не должно находиться более одного поезда. Светофор сочетанием огней показывает, сколько за ним свободных блок-участков (красный огонь – участок за светофором занят, красный и жёлтый – один, жёлтый – два, зелёный – три или более). Светофор принимает показания следующего по ходу светофора, а также определяет, занят ли блок-участок непосредственно за ним.

^ 1.8. Смоделируйте конечным автоматом работу лифта.
^ 2.Отношения эквивалентности автоматов и их состояний
Уравнения переходов, диаграммы Мура или таблицы функций переходов и выходов однозначно задают поведение автомата; обратное может быть неверно. В связи с этим для автоматов и их состояний вводятся различные отношения эквивалентности.

Рассмотрим вначале несколько полезных определений.

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

Автомат называется связным, если все его состояния достижимы, и сильно связным, если при этом любое состояние достижимо из другого.

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

Справедлива следующая теорема Мура: если два состояния автомата отличимы, то существует слово длины не более |Q|-1, различающее эти состояния, где |Q| - число состояний автомата.


Упражнение 2.1. Приведите пример автомата с числом состояний не менее 4, для которого любые два состояния а) различаются словом длины 1; б) различаются словом длины не менее 2, причём какие-то два не различаются словом длины 1.

Упражнение 2.2. Приведите пример автомата, для которого эта оценка достигается, то есть существуют два отличимых состояния, не различаемые словом длины меньшей, чем |Q|-1.

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

Определение. Назовём два автомата эквивалентными, если они имеют одинаковое поведение, то есть вычисляют одну и ту же о.-д. функцию.

^ Эквивалентное определение. Два автомата эквивалентны, если их начальные состояния неотличимы друг от друга.

Определение Скажем, что автомат является автоматом приведённого вида, если все его состояния достижимы и попарно отличимы.

Для любого автомата существует эквивалентный ему автомат приведённого вида. Однако приведённый вид не ещё задаёт автомат однозначно: существуют эквивалентные автоматы приведённого вида с разным числом состояний.


^ Упражнение 2.3. Приведите пример такой пары автоматов.

(Решение можно получить из нижеприведённых соображений).


У автоматов существует приведённый вид с более однозначно определённым набором состояний. В этом виде функция переходов имеет вид (x,q)=((x,q)), где  – некоторая функция, то есть вывод автомата в данный момент времени зависит от состояния, в которое он переходит. В самом деле, рассмотрим произвольный автомат, состояния которого - пары вида (q,y), где q – достижимое состояние исходного автомата, а y – одно из значений функции (x,q') для тех пар (x,q') при, которых (x,q')=q. В качестве начального состояния можно взять какую-либо пару (x,q0), где q0 – начальное состояние исходного автомата. Преобразованная функция переходов будут иметь вид '(x,(q,y))=('(x,q),'(x,q)), функция  имеет вид (q,y)=y.

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


Упражнение 2.4. Приведите автоматы, построенные в упражнениях 1.2 -1.5 к вышеуказанному виду.

^ 3.Стохастические функции конечных автоматов
Понятие конечного автомата связано с понятием цепи Маркова, также моделирующим объект с несколькими состояниями в дискретном времени (Существует также понятие вероятностного автомата, для которого входной символ задаёт набор вероятностей перехода автомата в другие состояния – обобщение как конечного автомата, так и цепи Маркова).

Пусть задан сильно связный (см. определение в следующей главе) автомат с входным и выходным алфавитом {0,1}, и на его вход подаётся случайная последовательность символов. Подобная система из генератора случайных чисел и конечного автомата меняет свои состояния по законам цепи Маркова. Функция f(p), выражающая зависимость частоты появления единицы в выходной последовательности символов от входной (при длине входного слова, стремящейся к бесконечности) называется стохастической функцией автомата. Она определяется по стационарному распределению соответствующей цепи Маркова.

Теорема. 1)Стохастическая функция любого конечного автомата равна частному двух многочленов с целыми коэффициентами.

2) Пусть функция f(x) определена на интервале (0,1), на этом интервале принимает значения из отрезка [0,1] (причём если эта функция где-либо принимает значения 0 или 1, то она – константа) и представима в виде частного двух многочленов с целыми коэффициентами, второй из которых – знаменатель – больше 0 на всём интервале (0,1). Тогда существует конечный автомат, для которого f(x) – стохастическая функция.


3.1. Постройте автомат со стохастической функцией, равной а) ½ б) x/2.


Для расчёта стохастической функции автомата следует сделать следующее:

1.Обозначить состояния числами от 1 до n.

1. Построить матрицу А(x) размерности nXn, На пересечении i-го столбца и j-той строки должно быть:

1, если автомат переходит из состояния i в состояние j безусловно;

x, если автомат переходит из состояния i в состояние j при вводе 1;

1-x, если автомат переходит из состояния i в состояние j при вводе 0;

0 в остальных случаях.

Решить линейную систему уравнений Ay=y (другими словами, найти собственный вектор, соответствующий собственному значению 1) при условии, что сумма координат вектора y будет равна 1. Этот вектор будет задавать стационарное распределение вероятности в соответствующей цепи Маркова.

Стохастическая функция будет иметь вид



Здесь суммирование ведётся по тем состояниям, в которых автомат выводит 1 при вводе 1 (первая сумма) или при вводе 2 (вторая сумма).


^ 3.2. Посчитайте стохастическую функцию автомата с диаграммой Мура следующего вида:






Решение. Матрица переходов в соответствующей цепи Маркова примет вид:



Решим систему уравнений:



Где, естественно, х – параметр, а a, b и c – переменные – стационарное распределение вероятностей.

Тогда из первого уравнения bx=c;

из второго ax – b +(1 - x)bx=0

откуда a=bпри x>0

и b(+1+x)=1,

откуда b=. Поскольку автомат выводит 1 только при одном переходе, стохастическая функция равна b(1-x)=

^ 3.3.Найдите стохастические функции автоматов из упражнений 1.2-1.6.

^ 4. Эксперименты над автоматами
В теории экспериментов над автоматами рассматривается следующая задача. Имеется неизвестный автомат («чёрный ящик») с известным входным и выходным алфавитом и некоторыми другими известными свойствами, позволяющие отнести его к некоторому известному классу автоматов. Требуется определить неизвестные свойства автомата (восстановить автомат, определить, каким именно автоматом из класса является данный) путём ввода в автомат входных последовательностей и наблюдения за выводом автомата. Алгоритм, который решает подобную задачу, называют экспериментом над автоматом. Эксперименты делятся на условные и безусловные, кратные и простые. Более формально, определения таковы:

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

^ Кратным безусловным экспериментом называется конечное множество слов во входном алфавите автомата. Испытание осуществляется путём ввода в автомат, находящийся в начальном состоянии, каждого слова с переводом автомата в начальное состояние после ввода. (Считается, что автомат имеет «кнопку возврата в начальное состояние» или имеется достаточное количество экземпляров автомата для испытаний).

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

^ Кратный условный эксперимент определяется аналогично кратному безусловному, но вместо входных слов вершины помечаются простыми условными экспериментами, а рёбра – результатами соответствующих экспериментов в вершинах, из которых они исходят.

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

Для оценки сложности экспериментов (относительно данного класса автоматов) применяются следующие величины:

^ Длина эксперимента – максимальная длина слова, которое может быть введено в автомат при применении эксперимента.

Объём эксперимента – максимальная суммарная длина слов, которые могут быть введены в автомат при применении эксперимента.

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


^ 4.1. Переформулируйте теорему Мура о различении состояний, используя понятия теории экспериментов.


Очевидно, что простой эксперимент – частный случай кратного, и безусловный - частный случай условного; однако возможности простых и условных экспериментов больше, чем кратных и безусловных.

Теорема. Существует класс автоматов, для которого не существует диагностического простого эксперимента.


4.2. Постройте класс автоматов, для которого существует условный кратный диагностический эксперимент кратности 2, но не существует безусловного кратного диагностического эксперимента такой или меньшей кратности.

^ 4.3. Пусть n – фиксированное натуральное число, {А} – класс автоматов Мура A=({1..n}, {0,1}n,{0,1}, ,,(0 … 0)), таких, что

Входной алфавит {1..n} – множество натуральных чисел от 1 до n, множество состояний - множество строк из 0 и 1 длины n, выходной алфавит {0,1}, начальное состояние – строка (0 … 0) - общие для всех автоматов класса;

функция переходов , также общая для всех автоматов, от строки q и входного символа k выдаёт строку q, в которой k-й символ заменён на 1;

функция выходов (q,x)=f((q,x)), где f – некоторая функция алгебры логики от n переменных, своя для каждого автомата класса.

Покажите, что уже при n≥2 простой диагностический эксперимент для этого класса невозможен. Покажите, что объём кратного диагностического эксперимента не ниже 2n, длина не ниже n.

Покажите, что при n≥2d кратностьэксперимента не ниже .

Покажите, что существует эксперимент кратности, равной наибольшему коэффициенту в разложении многочлена (1+x)n, диагностический для данного класса. Каков его объём?

Упражнение. 3.4. Пусть n – фиксированное натуральное число, {Аi} – класс автоматов Мура Ai=({0,1},Zn,{0,1}, i,,0), i=1..n, таких, что:

i(0,k)=k+1 mod n,

i(1,k)=k+1 mod n, при k≠i

i(1,k)=i-1 mod n.

Постройте условный диагностический эксперимент для этого класса автоматов. Оцените его длину, объём, кратность.
^ 5. Синтез схем из функциональных элементов
Эта глава посвящена реализации схемами из функциональных элементов функций алгебры логики и не использует результаты теории автоматов, однако необходима для следующей главы. Определение. Схемой из функциональных элементов, реализующей набор двоичных функций, называется ориентированный граф, имеющий следующие типы вершин:

вершины-входы, из которых исходит ровно одно ребро и ни одно не входит. Они соответствуют двоичным входам автомата;

вершины-выходы, в которые входит ровно одно ребро и ни одно не исходит. Они соответствуют функциям, реализованным схемой;

узловые вершины, в которые входит одно ребро и выходит некоторое количество рёбер (но не наоборот, т.е. более одного ребра входить не может!);

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

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


^ Упражнение 4.1. Реализуйте схемой из функциональных элементов функцию f(x,y,z,t)=.


В схеме будет 5 элементов – против 6 функциональных символов в формуле.

Обозначим L(f) минимальную сложность схемы, реализующей функцию f, в стандартном базисе, и L(n) – максимальное значение функции L(f) для всех функций f от n переменных. Функция L(n) называется функцией Шеннона.

Теорема. Функция L(n) имеет асимптотический порядок роста . Это означает, что любую функцию можно реализовать схемой сложности не более С*, где можно взять C=8 для всех функций и всё меньшее C для функций от достаточно большого числа переменных.


Упражнение 5.1. Реализуйте одной схемой все функции от 2 (3, 4, n…) переменных. Оцените сложность схемы.


Удобный способ реализации функций алгебры логики СФЭ основан на следующей идее. Набор переменных функции разделяется на две части, функция f (x1,x2,…xk,y1,y2,…yn) представляется в виде

f=

причём число различных функций относительно мало, и схема, реализующая функцию f cостоит из схемы, реализующей все функции , k инвертеров и соответствующего числа дизъюнкторов и конъюнкторов.


Упражнение 5.2. Возьмите произвольный двоичный вектор из 16 компонент и реализуйте соответствующую ему функцию от 4 переменных схемой.
^ 6.Операции над автоматами
В этой главе мы рассмотрим, как автоматы соединяются между собой, рассмотрим задачу о синтезе автомата – построении его из некоторого набора автоматов путём определённых операций.

Чтобы автоматы можно было соединять между собой, следует ограничить множество автоматов так, чтобы рассматриваемые автоматы были «совместимы».

Определение. Назовём автомат двоичным, если его входной и выходной алфавит есть декартова степень (декартово произведение нескольких экземпляров) множества E={0,1}, то есть множество двоичных векторов.

На самом деле класс двоичных автоматов достаточно универсален. Утверждение. Любой автомат изоморфен некоторому двоичному автомату.

Доказательство. Пусть дан автомат (A, Q, B, , , q0). Возьмём числа k и l, такие, что 2k≥|A| и 2l≥|B|. Существуют инъективные отображения f:A→Ek и g:B→El, называемые кодированиями входного и выходного алфавита соответственно. Отображение, обратное к f, будет биекцией, определённой на f(A) - части Ek; доопределим его как-нибудь на остальной части Ek, получив таким образом отображение f-1 из Ek на A. Рассмотрим двоичный автомат (Ek, Q, El, ', ', q0) c функциями переходов и выходов:

'(x,q)=(f-1(x),q),

'(x,q)=g((f-1(x),q)).

Здесь x=(x1,...xk) - входной символ двоичного автомата, из алфавита Ek.. Мы видим, что при вводе в автомат этот символ «декодируется» отображением f-1, а выходной символ «кодируется» отображением g. Легко видеть, что этот автомат будет изоморфен исходному.

Если у двоичного автомата входной алфавит и выходной алфавит, будем говорить, что автомат имеет k двоичных входов и l двоичных выходов. Соответствующие входы и выходы на схемах обозначаются стрелками, входящими/выходящими в прямоугольник (или другую фигуру), обозначающую автомат.

Для того, чтобы строго определить, что есть соединение автоматов, введём следующие операции над двоичными автоматами:

Операция добавления фиктивного входа. Автомат (Ek, Q, El, , , q0) при добавлении (k+1)-го фиктивного входа преобразуется в автомат (Ek+1, Q, El-1, ', , q0), где
'((x1,...xk+1),q)=((x1,...xk),q). Аналогично вводится операция добавления фиктивного входа под любым другим номером.

Операция удаления фиктивного входа. Пусть i-тый вход автомата фиктивен, то есть функции переходов и выходов не зависят существенно от компоненты xiвходного вектора x. Тогда можно преобразовать данный автомат в автомат(Ek-1, Q, El, ', ', q0) с функцией переходов '((x1,...xi-1,xi+1, ,...xk, ),q)=((x1,...xk),q) и аналогично изменённой функцией выходов.

Операция удаления выхода. Автомат (Ek, Q, El, , , q0) при удалении i-го выхода преобразуется в автомат (Ek, Q, El-1, , ', q0), где '(q,x)=(y1,...yi-1,yi+1, ,....yk, ), если '(q,x)=(y1,...yi-1,yi,yi+1, ,....yk, ).

Операция склеивания (отождествления) входов. Автомат (Ek, Q, El, , , q0) при склеивании i-го и j-го выхода преобразуется в автомат (Ek-1, Q, El, ', ', q0), с функцией переходов
'((x1,...xi-1,xi+1,,..,xj,....xk, ),q)=(x1,...xi-1,xj,xi+1,,..,xi-1,xi,xi+1,....xk, ),q)
(на место i-го входа подставляется j-й) и аналогично изменённой функцией выходов.

^ Параллельное соединение автоматов. Рассмотрим автоматы A1=(Ek, Q2, El, 1, 1, q1) и A2=(Em, Q2, En, 2, 2, q2). Параллельное соединение автоматов – автомат A3=(Ek+m, Q1×Q2, El+n, , , q) с функциями переходов и выходов:
((x1,x2),(q1,q2))=(1(x1,q1),2(x2,q2)),
((x1,x2),(q1,q2))=(1(x1,q1),2(x2,q2))
и начальным состоянием q=(q1,q2). (Здесь под x1 и x2 понимаются не компоненты одного двоичного вектора, а два вектора – один размерности k, второй размерности m. Аналогично (x1,x2) – это двоичный вектор размерности k+m.

Последовательное соединение автоматов. Рассмотрим автоматы A1=(Ek, Q2, El, 1, 1, q1) и A2=(Ek, Q2, El, 2, 2, q2). Соединим i-тый выход первого автомата с j-тым входом второго. Получится автомат A4=(Ek+m-1, Q1×Q2, El+n, , , q) со следующими функциями переходов и выходов:
((x1,z2),(q1,q2))=(1(x1,q1),2(u2,q2)),
((x1,z2),(q1,q2))=(1(x1,q1),2(u2,q2)).
Здесь z2 – вектор размерности m-1 , представляющий собой x2 с изъятой j-той компонентой, u2 - вектор x2, в котором j-тая компонента заменена на i-тую компоненту вектора 1(x1,q1). Аналогично можно соединить большее число выходов с таким же количеством входов, это также будет операцией 6; в частности, при соединении 0 выходов и входов операция аналогична операции 7.

Операция обратной связи. Скажем, что j-тый вход автомата A1=(Ek, Q2, El, , , q1) зависит с задержкой от i-го входа, если j-тая компонента функции (x,q) не зависит существенно от i-той компоненты вектора x. Тогда можно построить автомат A5=(Ek-1, Q2, El, ', ', q1) с функциями переходов и выходов '(z,q)=(u,q), '(z,q)=(u,q), где z– вектор размерности m-1 , представляющий собой xс изъятой j-той компонентой, u- вектор x, в котором j-тая компонента заменена на i-тую компоненту вектора '(z,q). Таким образом, эта операция – своеобразное последовательное соединение автомата с самим собой.



Упражнение 6.1. Покажите, что операция 6 сводится к операциям 5 и 7.

Упражнение* 6.2. Покажите, что операция последовательного соединения с автоматом, имеющим одно состояние, приводит к автомату, гомоморфному данному.


Определение. Операции 1-6 в совокупности называются операциями суперпозиции автоматов, операции 1-7 – операциями композиции. Множество функций, получаемых из функций данного множества M операциями суперпозиции (в том числе и конечным числом последовательно применяемых операций) будем называть замыканием множества M относительно оператора суперпозиции  и обозначать (M). Множество функций, получаемых из функций данного множества M операциями композиции (также в любом числе) будем называть замыканием множества M относительно оператора композиции  и обозначать (M).

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

Определение. Схемой автомата называется ориентированный граф со следующими видами вершин:

вершины-входы, из которых исходит ровно одно ребро и ни одно не входит. Они соответствую двоичным входам автомата;

вершины-выходы, в которые входит ровно одно ребро и ни одно не исходит. Они соответствую двоичным выходам автомата ;

узловые вершины, в которые входит одно ребро и выходит некоторое количество рёбер (но не наоборот, т.е. более одного ребра входить не может!);

вершины-автоматы, каждой из которых сопоставлен некоторый двоичный автомат, причём каждое входящее ребро соответствует двоичной компоненте входного вектора, а каждое исходящее – выходного.

Операциям над автоматами очевидным образом ставятся в соответствие операции над схемами: удаление выхода – удаление вершины-выхода и ведущего к ней ребра, склеивание входов – добавление узловой вершины и перенаправление входившего ребра в узловую вершину, из которой два ребра ведут к склеиваемым входам и так далее.


^ Упражнение 6.3. Покажите, что в схеме автомата, полученного путём суперпозиции, нет ориентированных циклов.

Очевидно, для любого множества M справедливо M⊆(M)⊆(M). Однако существуют множества M, для которых включение (M)⊆(M) нестрогое, поэтому добавление операции обратной связи существенно. Назовём множество автоматов полным относительно данного оператора замыкания (K или ), если для любого автомата существует автомат в замыкании данного множества относительно данного оператора, изоморфный этому автомату.

Теорема. 1.Никакая конечная система автоматов не может быть полной относительно оператора  . 2. Существует конечная система автоматов, полная относительно оператора K.

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

Построим конечную систему автоматов, полную относительно операций композиции. Назовём задержкой (с нулевым начальным состоянием) следующий автомат:





Поведение задержки описывается соотношениями y(t+1)=x(t), y(0)=0.


Упражнение 6.4. Выпишите уравнение поведения а) двух последовательно соединённых задержек; б) n последовательно соединённых задержек. Постройте диаграмму Мура для двух последовательно соединённых задержек.


Системой автоматов, полной относительно композиции будет множество, состоящее из задержки и системы автоматов с одним состоянием, соответствующим функциям какой-либо полной системы булевых функций (например, конъюнкции, дизъюнкции и отрицания).

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

Закодируем множество состояний автомата двоичными векторами (аналогично кодированию входного и выходного алфавитов в первой теореме главы). Будем считать, что состояние автомата есть двоичный вектор; наложим также ограничение, что начальное состояние автомата кодируется нулевым вектором. Если число состояний не является степенью 2, то двоичные вектора, не входящие в образ кодирующего отображения, являются недостижимыми состояниями;

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

Возьмём батарею задержек - параллельно соединённые задержки в количестве, равном числу компонент состояния автомата. Очевидно, батарея также описывается уравнениями y(t+1)=x(t), y(0)=0, где x и y теперь обозначают двоичные вектора.

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

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

П
олученная схема автомата выглядит следующим образом:


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

Поскольку автоматы, реализующие двоичные операторы – автоматы с одним состоянием, в