Онлайн-калькулятор призвания

Математическая энциклопедия » Что такое «Автомат Конечный»?

Значение слова, определение и толкование термина

Автомат Конечный

Avtomat Konechny

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

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

Макроподход. А. к.- это система [Автомат Конечный. Фото 2] где [Автомат Конечный. Фото 3] - конечные, как правило непустые, алфавиты, наз., соответственно, входным алфавитом, множеством состояний и выходным алфавитом; [Автомат Конечный. Фото 4]- функция переходов, отображающая множество [Автомат Конечный. Фото 5] в [Автомат Конечный. Фото 6] [Автомат Конечный. Фото 7]- функция выходов, отображающая [Автомат Конечный. Фото 8] в В. Такие А. к. иногда называются автоматами Мили. В случае, когда функция выходов [Автомат Конечный. Фото 9] отображает Sв В(т. е. не зависит от букв входного алфавита), А. к. называют а в-томатом Мура. Всякий автомат Мура является автоматом Мили.

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

[Автомат Конечный. Фото 13]

(здесь [Автомат Конечный. Фото 14] а запись [Автомат Конечный. Фото 15] обозначает слово, получаемое путем приписывания буквы акслову a). Таким образом распространенные функции [Автомат Конечный. Фото 16] [Автомат Конечный. Фото 17] для произвольных [Автомат Конечный. Фото 18] и [Автомат Конечный. Фото 19] описывают соответственно состояние, в к-рое переходит автомат из состояния s под действием входного слова [Автомат Конечный. Фото 20] и выходную букву, к-рая выдается автоматом в момент поступления последней буквы входного слова [Автомат Конечный. Фото 21] Пусть [Автомат Конечный. Фото 22] обозначает начало длины [Автомат Конечный. Фото 23] слова [Автомат Конечный. Фото 24] - слова в алфавитах [Автомат Конечный. Фото 25] определяемые следующим образом:

[Автомат Конечный. Фото 26]

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

[Автомат Конечный. Фото 30]

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

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

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

2) Множество [Автомат Конечный. Фото 43] определяемое для выделенного множества [Автомат Конечный. Фото 44] заключительных состояний так:

[Автомат Конечный. Фото 45]

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

3) Множество значений функции [Автомат Конечный. Фото 49] для всевозможных [Автомат Конечный. Фото 50] называемое множеством, перечислимым данным [Автомат Конечный. Фото 51]

4) Множество [Автомат Конечный. Фото 52] определяемое для системы [Автомат Конечный. Фото 53] подмножеств множества [Автомат Конечный. Фото 54] следующим образом:


[Автомат Конечный. Фото 55]

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

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

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

[Автомат Конечный. Фото 63]

то автоматы Мура будут эквивалентны автоматам Мили. Автомат Мура [Автомат Конечный. Фото 64] наз. автономным автоматом, или генератором, если функция переходов не зависит от букв входного алфавита. Под поведением инициального автономного автомата [Автомат Конечный. Фото 65] принято понимать сверхслово

[Автомат Конечный. Фото 66]

где [Автомат Конечный. Фото 67] . Эта последовательность является периодической с нек-рым предпериодом.

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

Понятия А. к. и функционирования А. к. могут быть определены различными эквивалентными способами (см. Автоматов способы задания, Автомата поведение). Широкое распространение получили так наз. канонические уравнения. Для произвольного слова [Автомат Конечный. Фото 71] пусть [Автомат Конечный. Фото 72] обозначает t- юбукву слова [Автомат Конечный. Фото 73], а [Автомат Конечный. Фото 74]- длину слова [Автомат Конечный. Фото 75] Тогда функционирование FА. к.[Автомат Конечный. Фото 76] состоит из всех тех и только тех троек слов [Автомат Конечный. Фото 77] , к-рые удовлетворяют условиям: 1)[Автомат Конечный. Фото 78] 2) для всякого tтакого, что [Автомат Конечный. Фото 79] имеют место равенства [Автомат Конечный. Фото 80] Для определения поведения инициального А. к. [Автомат Конечный. Фото 81] необходимо добавить равенство [Автомат Конечный. Фото 82] Совокупность этих равенств однозначно определяет поведение инициального А. к. и наз. обычно каноническими уравнениями. Канонич. уравнения широко используются в задачах анализа и синтеза автоматов.

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

[Автомат Конечный. Фото 83]

выходными алфавитами вида [Автомат Конечный. Фото 84] где А - конечный алфавит, одинаковый для всех элементов. Правила построения структурных А. к. из элементов описывают дозволенные соединения (отождествления) входов и выходов, а также определяют множества входов и выходов, получаемых А. к.

Важнейшим примером таких А. к. являются логические сети (л. с.). Ниже приводится один из вариантов этого понятия. В рассматриваемом случае А={0,1} и элементами являются так наз. функциональные элементы (ф. э.), представляющие собой А. к. с одним состоянием, а также специальные автоматы Мура, наз. задержками. Последние характеризуются тем, что они имеют два состояния, к-рые обычно обозначаются буквами О и 1 входного алфавита, при

[Автомат Конечный. Фото 85]

чем функции переходов и выходов удовлетворяют условиям: [Автомат Конечный. Фото 86] Поскольку ф. э. имеет только одно состояние, то он полностью характеризуется функцией выходов y, являющейся в этом случае булевой функцией от паргументов, где п - число входов ф. э. Элементы являются исходными л. с., входы и выходы к-рых совпадают, соответственно, с входами и выходами элементов. Дальнейшее построение более сложных л. с. производится по следующим правилам.

1. Объединение двух л. с. есть л. с., входами и выходами к-рой являются, соответственно, входы и выходы объединяемых л. с. (рис. 1).

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

3. Результат отождествления выхода одной л. с. с входом другой л. с. есть л. с. Ее входами являются все входы первой л. с. и те входы второй л. с., к-рые не отождествлялись с выходом первой л. с.; ее выходами являются все выходы обеих л. с. (рис. 3).

[Автомат Конечный. Фото 87]

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

5. В любой л. с. можно объявить выходами только часть выходов, определенных согласно правилам 1 - 4. Л. с., получаемые из ф. э. с помощью правил 1, 2, 3, 5, наз. обычно схемами из ф. э.

Функционирование л. с. содержательно можно описать следующим образом.

[Автомат Конечный. Фото 88]

Пусть в момент tвсем входам л. с. приписаны входные буквы и определены состояния задержек. Тогда в этот же момент всем входам и выходам элементов л. с., в частности всем выходам л. с., будут приписаны буквы в соответствии со следующими правилами. Если входам ф. э. с выходной функцией [Автомат Конечный. Фото 89] приписаны, соответственно, буквы [Автомат Конечный. Фото 90] то его выходу в этот же момент будет приписана буква, являющаяся значением [Автомат Конечный. Фото 91]

Если задержка находится в момент tв состоянии a, то в этот же момент ее выходу приписывается буква а. Отождествленным входам и выходам приписываются одинаковые буквы. Далее, в момент [Автомат Конечный. Фото 92] состояния задержек определяются входными буквами в момент t, как было определено выше, т. е. [Автомат Конечный. Фото 93] Таким образом, при фиксированных начальных состояниях задержек л. с. определяет нек-рое отображение входных последовательностей в алфавите [Автомат Конечный. Фото 94] в

[Автомат Конечный. Фото 95]

выходные последовательности в алфавите [Автомат Конечный. Фото 96] где [Автомат Конечный. Фото 97] [Автомат Конечный. Фото 98] - число входов, а n, [Автомат Конечный. Фото 99] - число выходов л. с. Класс таких отображений совпадает с классом функций, реализуемых А. к. в первом смысле (т. е. с классом ограниченно детерминированных функций), поскольку описанное выше функционирование л. с. совпадает с функционированием А. к. ([Автомат Конечный. Фото 100][Автомат Конечный. Фото 101] ), где [Автомат Конечный. Фото 102] - число входов, [Автомат Конечный. Фото 103] - число выходов л. с., S - декартово произведение множеств состояний всех задержек л. с.; функция переходов ф является покоординатным применением функций переходов задержек, а функция выходов [Автомат Конечный. Фото 104] определяется в соответствии с вышеописанным функционированием ф. э. и задержек.

Пусть, напр., элементами являются задержки (к-рые на рисунке изображаются прямоугольниками) и ф. э. с выходными функциями [Автомат Конечный. Фото 105] (треугольники с соответствующими символами функции). На рис. 5 изображена л. с., к-рая в тактовый момент tвыдает выходную букву 1 в том и только в том случае, если среди входных букв в моменты 0, 1, 2, .. ., tсодержится нечетное число букв 1 (задержка в начальный момент имеет состояние 0; буквами а и bобозначены, соответственно, вход и выход л. с.). Если обозначить через s(t), a(t), b(t), соответственно, состояние, входную букву и выходную букву в момент t, то функционирование такой л. с. можно задать следующими канонич. уравнениями:

[Автомат Конечный. Фото 106]

При макроподходе этот автомат можно представить в виде [Автомат Конечный. Фото 107] (mod 2) и [Автомат Конечный. Фото 108]

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

[Автомат Конечный. Фото 109]

  • ВКонтакте

  • Facebook

  • Мой мир@mail.ru

  • Twitter

  • Одноклассники

  • Google+

См. также

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

  • (липарит), эффузивная горн. порода со стекловатой основной массой и порфировыми вкрапленниками кварца, санидина, плагиоклаза, биотита; изли