§ 3.3. Конечные автоматы

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

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

Введем в рассмотрение -мерный вектор с координатами и -мерный вектор с координатами .

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

Соответственно множество, на котором задан , состоит из k элементов.

Совершенно аналогично вектор с координатами задается на конечном множестве, содержащем элементов, где — число элементов множества, на котором задана .

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

Аналогично введем в рассмотрение алфавит

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

Теперь надо определить «движение» в рассматриваемой системе, т. е. указать, как определяется состояние системы в каждый такт. Очень важный случай такого определения и приводит нас к понятию конечный автомат.

Определение. Конечная динамическая система называется конечным автоматом, если состояние системы в каждый такт однозначно определяется: а) состоянием системы в предыдущий такт и б) входом в предыдущий или в рассматриваемый такт.

Конечные автоматы, состояние которых определяется их состоянием в предыдущий такт и входом в предыдущий такт, назовем конечными автоматами типа П - П («предыдущее—предыдущее»). Автоматы же, состояние которых определяется их состоянием в предыдущий такт и входом в рассматриваемый такт, назовем конечными автоматами типа П — Н («предыдущее — настоящее»).

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

В соответствии с определением конечного автомата символ , соответствующий любому такту, однозначно определяется символом в предыдущий такт и символами в предыдущий или в рассматриваемый такт, т. е. для конечного автомата типа П — П

а для конечного автомата типа П — Н

где F — функция в том смысле, в каком этот термин был разъяснен в гл. I. Она ставит символ из алфавита в соответствие символам из алфавитов . Но в отличие от того, что имелось в виду в гл. I, здесь уже символы - аргументы и символ - функция относятся также и к разным моментам времени. Поэтому формулы (3.5) определяют не преобразователь, а динамическую систему.

Моменты времени, к которым относятся символы и , обозначены верхними индексами и соответствуют текущим тактам: — настоящему, — последующему, — предшествующему.

Если ввести в рассмотрение символ , заданный на том же алфавите , что и символ , то соотношения (3.5) и можно рассматривать как следствие соотношений

В первом соотношении (3.6) все символы относятся к одному и тому же моменту времени.

Если отнести их к моменту , т. е. записать

и добавить второе соотношение (3.6), исключив затем , то получим

т. е. соотношение (3.5).

Если же отнести первое соотношение (3.6) к моменту т. е. записать

и добавить второе соотношение (3.6), исключив уже то получим

т. е. соотношение вида .

Рассмотрим формулу (3.5):

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

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

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

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

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

Часы не являются частью конечного автомата. Их сигналы — внешние для автомата в такой же мере, как и воздействия р. Но вместе с тем сигналы от часов — временной вход — отличны и от внешних входных воздействий, так как они не шифруются символами из алфавита и не являются аргументами функции F в шениях (3.5). В тех случаях, когда конечным автоматом является какой-либо наблюдаемый процесс, сигналы от часов используются лишь в устройстве, которое фиксирует и в моменты тактов. При технической реализации конечного автомата сигналы от часов могут использоваться лишь для определения момента наступления такта.

Приведем примеры условий, определяющих разбиение шкалы непрерывного времени на такты:

а) Такты наступают через равные промежутки времени.

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

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

в) Такт наступает всякий раз, когда на входе появляется символ или .

г) Такт наступает, когда символ с нечетным индексом заменяется символом с четным индексом и т. п.

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

где — фиксированное неизменное значение .

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

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

В заключение этого параграфа заметим, что, отвлекаясь от содержательной стороны введенного выше понятия «конечный автомат» (связанной с понятиями «конечная динамическая система», «состояние» и ), можно это же определение понимать формально следующим образом: даны два конечных алфавита символов и переменные , принимающие значения из этих алфавитов. Конечным автоматом называются рекуррентные соотношения (3.5), связывающие эти переменные. Разумеется так определенный конечный автомат — далеко идущая абстракция.

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