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

управляющая система, являющаяся автоматом конечным или некоторой его модификацией, полученной путем изменения компонент или функционирования. Основное понятие конечный А. возникло в середине 20 в. в связи с попытками описать на математическом языке функционирование нервных систем, универсальных вычислительных машин и других реальных А., предпринятыми впервые У. Мак-Калло-ком и У. Питтсом (W. McCulloch, W. Pitts, 1943), С. К. Клини (S. С. Kleene, 1951), А. Бёрксоми Дж. Райтом (A. W. Burks, 1954, J. Wright) и др. Характерной особенностью такого описания является дискретность соответствующих математических моделей и конечность областей значений их параметров, что приводит к понятию конечного А. При этом внешние воздействия, реакции и состояния рассматриваются как буквы трех алфавитов, наз., соответственно, входным алфавитом, выходным алфавитом и алфавитом состояний. Тогда законы их взаимодействия могут быть заданы двумя функциями функцией переходов и функцией выходов, отображающими пары "состояние входная буква" в состояния и выходные буквы, соответственно. В каждый из моментов дискретного времени устройство, находящееся в определенном состоянии, воспринимает входной сигнал букву входного алфавита, выдает выходной сигнал букву выходного алфавита, определяемую функцией выходов, и переходит в новое состояние, определяемое функцией переходов. Наряду с понятием конечного А. рассматриваются различные его обобщения и модификации, отражающие те или иные особенности реальных устройств. Для конечного А. существующие модификации можно разбить на следующие три основные группы. К первой группе относятся А., у которых некоторые из алфавитов А, S или Вбесконечны, в связи с чем такие А. наз. бесконечными. Ко второй группе относятся А., у к-рых вместо функций j и y допускаются произвольные отношения или случайные функции. Таковы частичные, недетерминированные, вероятностные и другие А. К третьей группе относятся А. со специфич. множествами входных объектов. Таковы А. с переменной структурой, А. над термами (см. Автоматов алгебраическая теория). Существуют А., принадлежащие одновременно разным группам; напр., А. нечеткие относятся ко всем трем группам. Наряду с этим большую роль играют специальные подклассы конечных А.; например, А. без памяти, автономные, обратимые А. и т. д. Кроме того, использование понятий и методов из других разделов математики также приводит к появлению специфич. классов А. и связанных с ними задач. Напр., при применении алгебраич. средств возникают понятия А. над термами, линейного, группового, свободного и других А. (см. Автоматов алгебраическая теория);вопросы теории кодирования порождают понятия самонастраивающихся, обратимых А. и др. (см. также Автомат вероятностный). Для структурных А. также имеется целый ряд обобщений, сводящихся в основном к допущению бесконечных сетей и возможности изменения связей между элементами в процессе функционирования. Таким образом возникает понятие растущего А. Ниже описываются основные модификации и подклассы конечных А., а также их важнейшие свойства.

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

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

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

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

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

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

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

4. Нечеткие А. получаются как обобщение понятия конечного А. путем замены функций переходов и выходов нечеткими отношениями. Нечеткое подмножество множества Мзадается функцией, отображающей Мв отрезок [0,1]. Таким образом, роль функций переходов и выходов в нечетком А. играют функции, отображающие множества X в отрезок [0,1], где S - множество состояний, А - входной алфавит, В - выходной алфавит. Для нечетких А. естественно обобщаются основные понятия и задачи, характерные для конечных А., в частности задачи представления нечетких событий и реализации нечетких отношений. Нечеткие А. являются математич. моделями нек-рых распознающих устройств и используются в задачах распознавания образов.

5. Специальные классы конечных А. А.