50. Конечный автомат как математическая модель устройства с конечной памятью и как управляющая система. Способы описания конечных автоматов: перечислительный; диаграмма состояний; таблица состояний.

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

Содержательно конечный автомат можно охарактеризовать как устройство, имеющее входной и выходной каналы и находящееся в каждый из моментов дискретного времени, называемых тактовыми моментами, в одном из состояний. По входному каналу в каждый тактовый момент в устройство поступают сигналы a — буквы входного алфавита A; в те же моменты по выходному каналу устройство выдает сигналы b — буквы выходного алфавита B, причем b определяется состоянием s из алфавита состояний S и буквой a; внутреннее состояние s' в следующий тактовый момент также определяется состоянием s и буквой a из предыдущего момента. Таким образом, для некоторых функций j и f имеет место b = j(a, s), s' = f(a, s);

эти функции называются соответственно выходной и переходной функциями; они определяют закон «переработки» слов в алфавите A, подаваемых побуквенно на входной канал устройства при условии задания начального состояния устройства.

Конечным автоматом называется система M ={А, S, B, j, f}, в которой А = {а1, ..., am}, S ={s1, ..., sn}, B ={b1, ..., bk} — конечные множества (алфавиты), а j: А ´ S ® S и f: А ´ S ® B — функции, определенные на этих множествах.

А называется входным алфавитом,

B — выходным алфавитом,

S — алфавитом состояний,

j — функцией переходов,

f — функцией выходов.

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

Автомат «вообще» (от греческого zotamotua — самодействующий) — управляющая система, являющаяся конечным автоматом или некоторой его модификацией, полученной путем изменения его компонент или функционирования. Основное понятие — конечный автомат — возникло в середине 20 века в связи с попытками описать на математическом языке функционирование нервных систем, универсальных вычислительных машин и других реальных автоматов. Характерной особенностью такого описания является дискретность соответствующих математических моделей и конечность областей значений их параметров, что приводит к понятию конечного автомата.

• Автоматы, у которых некоторые из алфавитов A (входной), S (состояний) или B (выходной) бесконечны, в связи с чем такие автоматы называются бесконечными.

• Автоматы, у которых вместо выходной и переходной функций j и f допускаются произвольные отношения или случайные функции. Таковы частичные, недетерминированные, вероятностные и другие автоматы.

• Автоматы со специфическими множествами входных объектов. Таковы, например, автоматы с переменной структурой.

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

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

Способы задания автоматов:

• таблица переходов автомата, или просто автоматная таблица

• ориентированный мультиграф, называемый графом переходов или диаграммой переходов

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

• для любой входной буквы aj имеется дуга, выходящая из si, на которой написано aj (условие полноты);

• любая буква aj, встречается только на одном ребре, выходящем из si (условие непротиворечивости или детерминированности).

Пример:

Рассмотрим следующий конкретный конечный автомат M = [A, S, B, j, f]. Входной алфавит A = {0, 1}; выходной алфавит B = {0, 1}; три внутренних состояния S = {s0, s1, s2}; функции выхода и перехода задаются предписаниями

j: (s0, 0) ® s1 f: (s0, 0) ® 0

(s0, 1) ® s0 (s0, 1) ® 1

(s1, 0) ® s2 (s1, 0) ® 1

(s1, 1) ® s1 (s1, 1) ® 0

(s2, 0) ® s0 (s2, 0) ® 1

(s2, 1) ® s2 (s2, 1) ® 0

Диаграмма состояний:

Таблица состояний:

Пример2: