Автомат
АВТОМАТ – управляющая система, являющаяся автоматом конечным или некоторой его модификацией, полученной путём изменения компонент или функционирования. Основное понятие – конечный А. – возникло в середине 20 века в связи с попытками описать на математическом языке функционирование нервных систем, универсальных вычислительных машин и других реальных А., предпринятыми впервые У. Мак-Каллоком и У. Питтсом (W. McCulloch, W. Pitts, 1943), С. К. Клини (S. C. Kleene, 1951), А. Бёрксом и Дж. Райтом (A. W. Burks, 1954, J. Wright) и др. Характерной особенностью такого описания является дискретность соответствующих математических моделей и конечность областей значений их параметров, что приводит к понятию конечного А. (А, С, В, φ, ψ). При этом внешние воздействия, реакции и состояния рассматриваются как буквы трех алфавитов, называемые, соответственно, входным алфавитом, выходным алфавитом и алфавитом состояний. Тогда законы их взаимодействия могут быть заданы двумя функциями – функцией переходов и функцией выходов, отображающими пары «состояние – входная буква» в состояния и выходные буквы, соответственно. В каждый из моментов дискретного времени устройство, находящееся в определенном состоянии, воспринимает входной сигнал – букву входного алфавита, выдает выходной сигнал – букву выходного алфавита, определяемую функцией выходов, и переходит в новое состояние, определяемое функцией переходов. Наряду с понятием конечного А. рассматриваются различные его обобщения и модификации, отражающие те или иные особенности реальных устройств. Для конечного А. , , , существующие модификации можно разбить на следующие три основные группы. К первой группе относятся А., у которых некоторые из алфавитов , или бесконечны, в связи с чем такие А. называются бесконечными . Ко второй группе относятся А., у которых вместо функций и допускаются произвольные отношения или случайные функции. Таковы частичные, недетерминированные, вероятностные и другие А. К третьей группе относятся А. со специфическими множествами входных объектов. Таковы А. с переменной структурой, А. над термами ( см. Автоматов алгебраическая теория ). Существуют А., принадлежащие одновременно разным группам; например, А. нечеткие относятся ко всем трем группам. Наряду с этим большую роль играют специальные подклассы конечных А.; например, А. без памяти, автономные, обратимые А. и т. д. Кроме того, использование понятий и методов из других разделов математики также приводит к появлению специфических классов А. и связанных с ними задач. Например, А. над термами, линейного, группового, свободного и других А. (см. Автоматов алгебраическая теория ); вопросы теории кодирования порождают понятия самонастраивающихся, обратимых А. и др. (см. также Автомат вероятностный ). Для структурных А. также имеется целый ряд обобщений, сводящихся в основном к допущению бесконечных сетей и возможности изменения связей между элементами в процессе функционирования. Таким образом возникает понятие растущего А . Ниже описываются основные модификации и подклассы конечных А., а также их важнейшие свойства.
Макроподход. 1. А. бесконечные (первая группа) отличаются от А. конечных только тем, что их алфавиты A, B или S (входной, выходной и множество состояний) могут быть бесконечными. Большинство понятий и задач, связанных с конечными А., естественно распространяются на бесконечные А. Увеличение мощности алфавитов расширяет вычислительные возможности А. Так, например, если конечные А. реализуют ограниченно-детерминированные функции, то с помощью бесконечных А. можно реализовать любую детерминированную функцию. Более того, с помощью бесконечных А. может быть описано функционирование любых А. и машин. Вместе с тем большая общность понятия бесконечного А. снижает его содержательное значение, так что в основном изучаются лишь специальные подклассы бесконечных А., связанные с конкретными моделями управляющих систем.
2. Недетерминированные А. и асинхронные А . (вторая группа). Формально недетерминированный А . определяется как система , , , , где , , – алфавиты, имеющие прежний смысл, а – отношение переходов-выходов. В том случае, когда отношение является функцией, отображающей в , недетерминированный А. называется детерминированным А . и фактически совпадает с конечным А., поскольку в этом случае функцию можно рассматривать как пару функций , , отображающих в и , соответственно. В отличие от конечного А., инициальный недетерминированный А. имеет несколько начальных состояний, образующих подмножество множества . Под поведением этого А. обычно понимают одно из следующих обобщений поведения конечного А.
1) Вместо функции автомат реализует отношение , состоящее из всех пар слов таких, что найдутся состояния , для которых и для любого имеет место . Класс отношений, реализуемых инициальным недетерминированным А., совпадает с классом ограниченно-детерминированных отношений (см. Ограниченно-детерминированная функция ).
2) Инициальный недетерминированный А. , у которого выделено множество заключительных состояний, а алфавит пуст (т.е. ), представляет событие состоящее из всех слов таких, что найдутся состояния , для которых , и для любого имеет место . Класс событий, представимых А. , совпадает с классом регулярных событий, т.е. относительно такого поведения недетерминированные А. эквивалентны конечным А. В то же время большая общность понятия недетерминированного А. проявляется в том, что для представления одного и того же события с помощью недетерминированного А. и конечного А. требуется различное число состояний. Существуют события, представимые недетерминированными А. с состояниями и представимые конечными А. с состояниями, причем никакие конечные А. с меньшим числом состояний не представляют эти события.
Специальный подкласс недетерминированных А. образуют так называемые частичные А. , у которых отношение является частичной функцией, отображающей множество в , и которые реализуют частичные ограниченно-детерминированные функции.
Термином «асинхронный А.» обычно обозначают один из двух следующих видов А. К первому относятся А. вида , где функция выходов отображает множество в (у конечного А. отображает в ). Эти А. используются главным образом в теории кодирования. Ко второму виду относятся конечные А., функция переходов у которых обладает следующим свойством: для любых и . Эти А. также используются в теории кодирования и, кроме того, для моделирования некоторых систем в технике и биологии.
3. А. с переменной структурой (третья группа) – это конечные А. с двумя входами, у которых зафиксирована некоторая бесконечная последовательность (сверхслово) в алфавите А. На первый вход такого А. подаются произвольные слова в алфавите А, а на второй – начала последовательности той же длины. Тем самым накладывается ограничение на множество пар входных слов. Если А. с переменной структурой рассматривать как А. с одним первым входом (на который могут подаваться любые слова в алфавите А), то его функции переходов и выходов будут зависеть от длины поданной части входного слова. Относительно поведения А. с переменной структурой эквивалентны бесконечным А. с конечными входным и выходным алфавитами и счетным множеством состояний.
4. Нечеткие А. получаются как обобщение понятия конечного А. путем замены функций переходов и выходов нечеткими отношениями. Нечеткое подмножество множества задается функцией, отображающей в отрезок [0,1]. Таким образом, роль функций переходов и выходов в нечетком А. играют функции, отображающие множества и в отрезок [0,1], где – множество состояний, – входной алфавит, В – выходной алфавит. Для нечетких А. естественно обобщаются основные понятия и задачи, характерные для конечных А., в частности задачи представления нечетких событий и реализации нечетких отношений. Нечеткие А. являются математическими моделями некоторых распознающих устройств и используются в задачах распознавания образов.
5. Специальные классы конечных А.
А. без памяти – это конечные А. с одним состоянием или А., эквивалентные им. Для таких А. каждая выходная буква полностью определяется входной буквой, поступившей в тот же,момент. Эти А. часто называются функциональными элементами и широко применяются в задачах синтеза А.
А. с конечным запоминанием , называются иногда А. с конечной памятью , – это конечные А., любая выходная буква которых при любом исходном состоянии полностью определяется ограниченным отрезком входного слова, поступившим в предшествующие моменты. Минимальная длина таких отрезков для А. с конечным запоминанием с состояниями не превосходит , причем для некоторых А. эта оценка достигается. А. с конечным запоминанием называется самонастраивающимся , если для некоторого выходная буква в любой момент не зависит от исходного состояния. Эти А. используются в теории кодирования (см. Кодирование и декодирование), где обычно рассматривается модификация таких А., которая удовлетворяет указанному условию не для всех входных слов, а только для некоторого подмножества их. А. с конечным запоминанием реализуются логическими сетями без обратных связей.
А. обратимые , или А. без потери информации , – это конечные А., реализующие взаимно однозначные функции. Эти А. также используются в теории кодирования.
Микроподход. Существует три вида обобщений структурных А., которые можно рассматривать как обобщенные логические сети: 1) обобщенные логические сети с неизменной структурой, у которых элементы и связи между ними не меняются в процессе функционирования; 2) обобщенные логические сети с изменяющейся структурой; 3) обобщенные логические сети из объемных элементов и связей. Ниже приведены основные классы таких А.
1. Обобщенные логические сети с неизменной структурой . К ним относятся мозаичные структуры и итеративные сети , являющиеся конечными фрагментами мозаичных структур с аналогичным кругом задач.
Мозаичные структуры представляют собой бесконечные соединения переходных систем (т. е. конечных А. вида , где функция выходов совпадает с функцией переходов, а выходной алфавит – с множеством состояний). Такие системы помещаются в целочисленные точки -мерного пространства, причем для каждой точки определено конечное множество целочисленных точек, называемое ее окрестностью. Входной алфавит переходной системы, помещенной в данную точку, представляет собой декартово произведение множеств состояний переходных систем, помещенных в точки ее окрестности.
Мозаичную структуру можно рассматривать как бесконечный А., входной и выходной алфавиты, а также, множество состояний которого равны и являются бесконечным декартовым произведением множеств состояний всех переходных систем, содержащихся в ней. Это позволяет сводить многие задачи для мозаичных структур к задачам для бесконечных А. К числу специфических задач для мозаичных структур относится моделирование эффективных процедур и, в частности, вычислительных процессов. Иногда рассматривают мозаичные структуры, в которых вместо переходных систем используются произвольные А.
Важный класс мозаичных структур образуют однородные структуры. В случае, когда все переходные системы одинаковы и окрестность любой точки получается параллельным переносом некоторой окрестности, мозаичная структура называется однородной структурой . При этом обычно предполагается, что имеется некоторое "устойчивое" состояние переходной системы, которое сохраняется, когда входной буквой является кортеж, каждый член которого совпадает с этим состоянием. Характерными задачами для однородных структур являются задачи о самовоспроизведении и "райских садах".
В каждый момент состояния переходных систем, помещенных в точках целочисленной решетки, образуют как бы пространственную мозаичную картину, называемую обычно конфигурацией . Конфигурация, содержащая только конечное множество переходных систем, находящихся в состояниях, отличных от устойчивого (возбужденная часть), называется конечной. Задача о самовоспроизведении состоит в выяснении существования конечных конфигураций, которые в процессе функционирования однородной системы переходят в конфигурации, возбужденная часть которых представляет собой многократно повторенную возбужденную часть исходной конфигурации. "Райским садом" называется конфигурация, которая не может возникнуть из конфигураций, отличных от нее. Задача о "райских садах" состоит в выяснении существования "райских садов" для заданной однородной структуры.
2. Обобщенные логические сети с изменяющейся структурой . Существуют разные виды таких логических сетей. К числу наиболее общих из них относятся мозаичные структуры, у которых в процессе функционирования меняются как окрестности элементов, так и сами элементы. Примером такой обобщенной логической сети может служить одномерная структура, имитирующая работу Тьюринга машины со входом. Одному из узлов одномерной решетки в этом случае соответствует управляющее устройство, а остальным – ячейки ленты, рассматриваемые как переходные системы, входными буквами и состояниями которых являются буквы рабочего алфавита машины Тьюринга. Коммутация определяется положением головки.
Другим видом обобщенных логических сетей с изменяющейся структурой являются так называемые растущие А. Они представляют собой однородные структуры, в которых возбужденная часть растет в процессе функционирования. Существует несколько моделей таких А., отражающих различные особенности реальных устройств.
3. Обобщенные логические сети из объемных элементов отличаются тем, что элементарным А. и связям между ними приписывается определенный объем, в связи с чем возникает задача синтеза А., имеющих минимальный объем. Термин «А.» употребляется также в таких понятиях, как двусторонний, многоленточный, многоголовочный, линейно ограниченный и т. п. А., которые фактически являются модификациями машин Тьюринга. Более того, иногда в понятие А. включают все абстрактные машины.
References
[1] Мак-Каллок У., Питтс В., в сб.: Автоматы, м., 1956, с. 362-84;
[2] Клини С., там же, с. 15-67;
[3] Бёркс А., Райт Д., в кн.: Кибернетический сборник, в. 4, М., 1962, с. 33-57;
[4] Глушков В. М., Успехи математических наук, 1961, т. 16, № 5, с. 3-62; 1962, т. 17, № 2;
[5] Рабин М. О., Скотт Д., в кн.: Кибернетический сборник, в. 4, М., 1962, с. 58-91;
[6] Zadeh L. A., J. Math. Anal. and Appl., 1968, v. 23, № 2, p. 421-427;
[7] Аладьев В. З., К теории однородных структур, Тал., 1972.
В. Б. Кудрявцев.
Выходные данные:
- Просмотров: 5
- Комментариев: 0
- Опубликовано: 27.10.2010
- Версий: 40 , текущая: 40
- Статус: пользовательская
- Рейтинг: 0.0
Автор:
Алешин Станислав Владимирович
- профессор; доктор физико-математических наук
- Редактор
Ссылки отсюда
Персоны:Категории:Детализирующие понятия:
Автомат вероятностный; Автоматов алгебраическая теория; Информация; Моделирование; Модель; Распознавание образов; Техника.
Ссылки сюда
Категории:
Алгебра; Оружие и системы вооружений; Ракетно-космическая техника;
Детализирующие понятия:Автомата поведение; Автоматизация энергосистем; Автоматов алгебраическая теория; Автоматов эквивалентность; Артиллерия; Дискретная математика; Математическая биология; Молочная промышленность; Мясная промышленность; Стрелковое оружие; Теория интеллектуальных систем; Управляющая система.