Математическая энциклопедия - автомат конечный

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

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

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

Важнейшей характеристикой А. к. является его поведение (см. Автомата поведение), к-рое может быть определено по-разному. В зависимости от того, какой тип поведения рассматривается, А. к. подразделяются на преобразователи, акцепторы (распознаватели), генераторы и др. Чтобы определить основные виды поведения А. к., функции j и y распространяют на множество (где множество всех слов в алфавите А, включая пустое слово ):

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

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

наз. функционированием А. к. =( А, S, В,j, y). Функции естественно распространяются и на бесконечные последовательности (сверхслова) в алфавите А. Поэтому под функционированием А. к. иногда понимают отношение вида F, в к-ром a произвольное сверхслово. В этом случае значение функции определяется как множество всех тех и только тех состояний, к-рые встречаются в последовательности бесконечное число раз.

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

1) Функция отображающая (или , где множества всех сверхслов в алфавитах Аи Всоответственно). Эта функция наз. функцией вычислимой, или реализуемой, инициальным А. к.

2) Множество определяемое для выделенного множества заключительных состояний так:

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

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

4) Множество определяемое для системы подмножеств множества следующим образом:

Множество наз. сверхсобытием, представимым А. к. с системой' заключительных подмножеств состояний. А. к. с поведением типа 1) наз. конечным преобразователем, ас поведением типа 2) конечным распознавателем, или акцептором.

Если в качестве входного и выходного алфавитов взять декартовы произведения X соответственно, то поведением типа 1) будет набор из га функций от таргументов. В этом случае говорят, что автомат имеет твходов и n выходов, причем алфавиты наз., соответственно, входными и выходными алфавитами такого автомата. Класс событий, представимых А. к., и класс функций, вычислимых А. к., могут быть описаны различными математич. средствами. Основной результат состоит в том, что события, представимые А. к., совпадают с так наз. регулярными событиями, а функции, вычислимые А. к., совпадают с ограниченно-детерминированными функциями. Кроме того, класс множеств, перечислимых А. к., совпадает с классом событий, представимых А. к.

Относительно поведений 2), 3) и 4) автоматы Мура эквивалентны автоматам Мили в том смысле, что для всякого автомата Мили найдется эквивалентный ему, т. е. имеющий то же самое поведение, автомат Мура, и обратно. Для поведения 1) это неверно. Однако, если в автоматах Мура вместо брать функции вида

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

где . Эта последовательность является периодической с нек-рым предпериодом.

А. к. паз. переходной системой, если B-S и для всякого s из Sимеет место или же если выходной алфавит В - пустой. Таким образом, переходная система полностью определяется тройкой

Понятия А. к. и функционирования А. к. могут быть определены различными эквивалентными способами (см. Автоматов способы задания, Автомата поведение). Широкое распространение получили так наз. канонические уравнения. Для произвольного слова пусть обозначает t- юбукву слова , а длину слова Тогда функционирование FА. к. состоит из всех тех и только тех троек слов , к-рые удовлетворяют условиям: 1) 2) для всякого tтакого, что имеют место равенства Для определения поведения инициального А. к. необходимо добавить равенство Совокупность этих равенств однозначно определяет поведение инициального А. к. и наз. обычно каноническими уравнениями. Канонич. уравнения широко используются в задачах анализа и синтеза автоматов.

Микроподход. Рассматривается множество элементов, состоящее из определенных выше А. к. с входными и