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

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

Автоматов Способы Задания

Avtomatov Sposoby Zadaniya

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

Макроподход. В этом случае задать конечный автомат [Автоматов Способы Задания. Фото 1] при условии, что заданы алфавиты значит [Автоматов Способы Задания. Фото 2] описать функции [Автоматов Способы Задания. Фото 3] или описать поведение этого автомата (см. Автомата поведение). Для задания функций [Автоматов Способы Задания. Фото 4] обычно используют таблицу переходов, диаграмму переходов или матрицу переходов. Таблица переходов Тавтомата [Автоматов Способы Задания. Фото 5] состоит из двух подтаблиц [Автоматов Способы Задания. Фото 6] [Автоматов Способы Задания. Фото 7] , Функции [Автоматов Способы Задания. Фото 8] определяются как [Автоматов Способы Задания. Фото 9] Если все столбцы [Автоматов Способы Задания. Фото 10] совпадают, то таблица Тзадает автомат Мура. Напр., пусть [Автоматов Способы Задания. Фото 11] тогда таблица Т(рис. 1) задает функции [Автоматов Способы Задания. Фото 12] нек-рого автомата [Автоматов Способы Задания. Фото 13] (на рис. 2 показаны подтаблицы [Автоматов Способы Задания. Фото 14] таблицы Т).

[Автоматов Способы Задания. Фото 15]

Диаграмма автомата (диаграмма переходов автомата) - это ориентированный граф G, вершинам к-рого взаимно однозначно соответствуют элементы 5, а ребрам приписаны нек-рые множества пар вида [Автоматов Способы Задания. Фото 16] Из каждой вершины G исходит по крайней мере одно ребро; при этом множество [Автоматов Способы Задания. Фото 17] всех пар, приписанных ребрам, исходящим из одной вершины, имеет вид [Автоматов Способы Задания. Фото 18][Автоматов Способы Задания. Фото 19] Функции j и y) определяются следующим образом:[Автоматов Способы Задания. Фото 20] если ребру, исходящему из вершины si , приписана пара ( а i , b р).и это ребро ведет в вершину sr . Нек-рые свойства автоматов удобно формулировать на

[Автоматов Способы Задания. Фото 21]

языке диаграмм (связность автомата, достижимость состояний и т. п.). На рис. 3 представлена диаграмма переходов автомата [Автоматов Способы Задания. Фото 22]

Матрица переходов используется для описания функционирования переходной системы [Автоматов Способы Задания. Фото 23] (см. Автомат конечный). Она представляет собой

[Автоматов Способы Задания. Фото 24] элементами к-рой являются подмножества алфавита А(может быть, пустые) такие,

что [Автоматов Способы Задания. Фото 25] тогда и только тогда, когда [Автоматов Способы Задания. Фото 26] и, следовательно, для всякого [Автоматов Способы Задания. Фото 27] имеет место [Автоматов Способы Задания. Фото 28] Чтобы распространить функцию [Автоматов Способы Задания. Фото 29] на множество [Автоматов Способы Задания. Фото 30] (.[Автоматов Способы Задания. Фото 31] - множество всех слов в алфавите А, включая пустое слово), рассматривают последовательность степеней матрицы Р. Умножение матрицы Рна себя производится по обычному алгоритму с использованием вместо операций умножения и сложения операций произведения (к о н-катенации) и объединения множеств слов. Если [Автоматов Способы Задания. Фото 32] - слово длины [Автоматов Способы Задания. Фото 33] - элемент матрицы [Автоматов Способы Задания. Фото 34] Так, матрица переходов Рпереходной системы [Автоматов Способы Задания. Фото 35] и матрица [Автоматов Способы Задания. Фото 36] имеют, соответственно, вид:

[Автоматов Способы Задания. Фото 37]

С указанными А. с. з. связан ряд алгоритмов минимизации (приведения) и синтеза автоматов.


[Автоматов Способы Задания. Фото 38]

Для задания поведения инициального (не обязательно конечного) автомата [Автоматов Способы Задания. Фото 39] (преобразователя) необходимо описать функцию [Автоматов Способы Задания. Фото 40] отображающую [Автоматов Способы Задания. Фото 41] (или [Автоматов Способы Задания. Фото 42] в [Автоматов Способы Задания. Фото 43] - множества всех сверхслов в алфавитах Аи В, соответственно). Эта функция может быть задана информационным деревом. Из каждой вершины информационного дерева исходит [Автоматов Способы Задания. Фото 44] ребер, взаимно однозначно соответствующих буквам алфавита [Автоматов Способы Задания. Фото 45]. Каждой вершине приписано состояние автомата [Автоматов Способы Задания. Фото 46] а каждому ребру - буква алфавита Вследующим образом. Корню приписано состояние [Автоматов Способы Задания. Фото 47] Если нек-рой вершине приписано состояние [Автоматов Способы Задания. Фото 48] то ребру, соответствующему букве [Автоматов Способы Задания. Фото 49] приписана буква [Автоматов Способы Задания. Фото 50] и вершине, в к-рую ведет это ребро, приписано состояние [Автоматов Способы Задания. Фото 51] Каждому слову [Автоматов Способы Задания. Фото 52][Автоматов Способы Задания. Фото 53] соответствует единственная последовательность [Автоматов Способы Задания. Фото 54] ребер этого дерева такая, что [Автоматов Способы Задания. Фото 55] исходит из корня и [Автоматов Способы Задания. Фото 56] исходит из вершины, в к-рую ведет [Автоматов Способы Задания. Фото 57] Слово [Автоматов Способы Задания. Фото 58] где [Автоматов Способы Задания. Фото 59] - буква из В, приписанная ребру [Автоматов Способы Задания. Фото 60] совпадает со значением [Автоматов Способы Задания. Фото 61] Если функция f реализуется конечным автоматом, то соответствующее информационное дерево может быть задано эффективно своим конечным поддеревом. На рис. 4 изображено поддерево информационного дерева, задающее поведение инициального автомата [Автоматов Способы Задания. Фото 62] (левые ребра, исходящие из вершин, соответствуют символу [Автоматов Способы Задания. Фото 63] правые - символу [Автоматов Способы Задания. Фото 64]).

Описание поведения конечного автомата (акцептора) в терминах представимого события (сверхсобытия) может быть сделано с помощью регулярного выражения (см. Регулярное событие). Такие события могут быть также заданы как множества слов, порождаемых (выводимых) в нек-рой формальной системе (полу-Туэ грамматике и т. п.). Система полу-Туэ в этом случае задается четверкой [Автоматов Способы Задания. Фото 65] где [Автоматов Способы Задания. Фото 66]- конечные алфавиты, [Автоматов Способы Задания. Фото 67]- аксиом схема вида [Автоматов Способы Задания. Фото 68] и [Автоматов Способы Задания. Фото 69] - множество схем правил вывода вида [Автоматов Способы Задания. Фото 70] где [Автоматов Способы Задания. Фото 71] - переменная, принимающая значения из [Автоматов Способы Задания. Фото 72]. При этом, если [Автоматов Способы Задания. Фото 73] и [Автоматов Способы Задания. Фото 74] принадлежат [Автоматов Способы Задания. Фото 75] то [Автоматов Способы Задания. Фото 76]. Слово [Автоматов Способы Задания. Фото 77] выводимо в системе [Автоматов Способы Задания. Фото 78] если существует последовательность слов [Автоматов Способы Задания. Фото 79] [Автоматов Способы Задания. Фото 80] такая, что [Автоматов Способы Задания. Фото 81] получается из [Автоматов Способы Задания. Фото 82] [Автоматов Способы Задания. Фото 83] применением нек-рого правила из [Автоматов Способы Задания. Фото 84] не содержит правила [Автоматов Способы Задания. Фото 85] Аналогичный вид имеет грамматика, порождающая регулярное событие. Она задается четверкой [Автоматов Способы Задания. Фото 86] где [Автоматов Способы Задания. Фото 87] из [Автоматов Способы Задания. Фото 88] - аксиома, [Автоматов Способы Задания. Фото 89] - множество правил вида [Автоматов Способы Задания. Фото 90] либо [Автоматов Способы Задания. Фото 91]

Слово [Автоматов Способы Задания. Фото 92] выводимо в Г, если в w имеются правила [Автоматов Способы Задания. Фото 93] Известны алгоритмы, позволяющие получать матрицу переходов автомата по формальным системам описанного типа. Так, событие, представимое в акцепторе [Автоматов Способы Задания. Фото 94] состоянием [Автоматов Способы Задания. Фото 95] может быть, напр., задано как множество слов, выводимых в системе полу-Туэ, к-рая имеет вид:

[Автоматов Способы Задания. Фото 96]

Существует ряд других А. с. з. Напр., переходная система [Автоматов Способы Задания. Фото 97] не обязательно конечная, может быть задана как алгебра [Автоматов Способы Задания. Фото 98] где [Автоматов Способы Задания. Фото 99] есть множество унарных операций на [Автоматов Способы Задания. Фото 100] таких, что [Автоматов Способы Задания. Фото 101] Так, переходную систему [Автоматов Способы Задания. Фото 102] можно рассматривать как алгебру [Автоматов Способы Задания. Фото 103] [Автоматов Способы Задания. Фото 104] Можно также рассматривать алгебру [Автоматов Способы Задания. Фото 105] , где [Автоматов Способы Задания. Фото 106] - множество слов вида [Автоматов Способы Задания. Фото 107]- множество унарных операций на [Автоматов Способы Задания. Фото 108] таких, что [Автоматов Способы Задания. Фото 109] Алгебра [Автоматов Способы Задания. Фото 110] задается системой образующих Sи множеством определяющих соотношений [Автоматов Способы Задания. Фото 111]

Такая алгебра задает автомат воооще говоря, частичный) [Автоматов Способы Задания. Фото 112] такой, что если [Автоматов Способы Задания. Фото 113] - соотношение из [Автоматов Способы Задания. Фото 114] Напр., переходную систему [Автоматов Способы Задания. Фото 115] можно задать системой образующих [Автоматов Способы Задания. Фото 116] и множеством определяющих соотношений [Автоматов Способы Задания. Фото 117] [Автоматов Способы Задания. Фото 118] При этом предполагается, что [Автоматов Способы Задания. Фото 119]

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

Указанные А. с. з. могут быть использованы с соответствующими модификациями при макроподходе к поведению нек-рых обобщений конечных автоматов (недетерминированных, бесконечных и т. п., см. Автомат), Так, элементами таблицы [Автоматов Способы Задания. Фото 120] конечного недетерминированного автомата могут быть произвольные подмножества множества S. Поведение конечного недетерминированного акцептора описывается регулярным выражением, как и в детерминированном случае. Другими обобщениями конечных автоматов являются конечные автоматы вероятностные, автоматы над термами, мозаичные структуры и т. п.

Задать вероятностный автомат [Автоматов Способы Задания. Фото 121] если известны алфавиты [Автоматов Способы Задания. Фото 122] [Автоматов Способы Задания. Фото 123] - значит при любых фиксированных iи [Автоматов Способы Задания. Фото 124] указать условную вероятностную меру |[Автоматов Способы Задания. Фото 125] на множестве всех пар [Автоматов Способы Задания. Фото 126] [Автоматов Способы Задания. Фото 127] Для этого обычно рассматривают систему квадратных матриц с неотрицательными элементами

[Автоматов Способы Задания. Фото 128]

такую, что каждая матрица [Автоматов Способы Задания. Фото 129] является стохастической. Мера [Автоматов Способы Задания. Фото 130] определяется так: [Автоматов Способы Задания. Фото 131][Автоматов Способы Задания. Фото 132] Вероятностный автомат [Автоматов Способы Задания. Фото 133] рассматривается совместно с нек-рым начальным распределением вероятностей на множестве [Автоматов Способы Задания. Фото 134]

[Автоматов Способы Задания. Фото 135]
Иногда при задании вероятностных автоматов ограничиваются либо указанием матриц [Автоматов Способы Задания. Фото 136], либо указанием матриц [Автоматов Способы Задания. Фото 137] где

[Автоматов Способы Задания. Фото 138]

[Автоматов Способы Задания. Фото 139] Любая конечная Маркова цепь может рассматриваться как конечный вероятностный автомат, у к-рого матрицы [Автоматов Способы Задания. Фото 140] [Автоматов Способы Задания. Фото 141] совпадают. Ниже представлены система матриц, задающая нек-рый вероятностный автомат [Автоматов Способы Задания. Фото 142] [Автоматов Способы Задания. Фото 143] и матрицы [Автоматов Способы Задания. Фото 144] этого автомата:

[Автоматов Способы Задания. Фото 145]

Чтобы задать конечный автомат над термами [Автоматов Способы Задания. Фото 146][Автоматов Способы Задания. Фото 147] когда известны алфавиты [Автоматов Способы Задания. Фото 148] [Автоматов Способы Задания. Фото 149][Автоматов Способы Задания. Фото 150] необходимо, во-первых, указать отображение а множества Ав конечное множество неотрицательных целых чисел, причем так, чтобы существовал хотя бы один элемент [Автоматов Способы Задания. Фото 151] такой, что [Автоматов Способы Задания. Фото 152] а во-вторых, для всякого [Автоматов Способы Задания. Фото 153] требуется определить [Автоматов Способы Задания. Фото 154] -местную функцию [Автоматов Способы Задания. Фото 155] отображающую множество [Автоматов Способы Задания. Фото 156] Каждому элементу [Автоматов Способы Задания. Фото 157] такому, что [Автоматов Способы Задания. Фото 158] ставится в соответствие элемент [Автоматов Способы Задания. Фото 159] наз. начальным состоянием автомата. Напр., если [Автоматов Способы Задания. Фото 160] [Автоматов Способы Задания. Фото 161] то [Автоматов Способы Задания. Фото 162] функции [Автоматов Способы Задания. Фото 163] задают нек-рый автомат над термами [Автоматов Способы Задания. Фото 164] с начальным состоянием [Автоматов Способы Задания. Фото 165]

Чтобы задать мозаичную структуру (бесконечное соединение переходных систем вида [Автоматов Способы Задания. Фото 166] где А [Автоматов Способы Задания. Фото 167] , см. Автомат), необходимо для каждой целочисленной точки n-мерного пространства определить конечное упорядоченное множество целочисленных точек - ее окрестность. При этом входной алфавит Апереходной системы [Автоматов Способы Задания. Фото 168] помещенной в нек-рую точку, есть декартово произведение множеств состояний переходных систем, помещенных в точки ее окрестности. Напр., пусть [Автоматов Способы Задания. Фото 169] и для всякой целочисленной точки двумерного пространства [Автоматов Способы Задания. Фото 170] ее окрестность [Автоматов Способы Задания. Фото 171] есть упорядоченное множество [Автоматов Способы Задания. Фото 172][Автоматов Способы Задания. Фото 173] Чтобы задать однородную двумерную мозаичную структуру, определяют функцию j следующим образом:[Автоматов Способы Задания. Фото 174] в остальных случаях. Входной алфавит Ав данном случае - декартово произведение [Автоматов Способы Задания. Фото 175]

Микроподход. При микроподходе задать структурный автомат - значит описать элементы, из к-рых он построен, и схему их соединения. Описание может производиться на различных уровнях детализации. Часто ограничиваются рассмотрением так наз. канонической схемы построения автоматов; при этом элементы делят на две группы - функциональные элементы (автоматы с одним состоянием) и элементы памяти. Канонич. схема (рис. 5) состоит из двух функциональных блоков f и gс присоединенными к ним элементами памяти, в качестве к-рых используются автоматы Мура:[Автоматов Способы Задания. Фото 176] [Автоматов Способы Задания. Фото 177] Блоки [Автоматов Способы Задания. Фото 178] построены из функциональных элементов. При данном способе задания структуру этих блоков не описывают, а задают (напр., таблично) реализуемые ими вектор-функции:

[Автоматов Способы Задания. Фото 179]

[Автоматов Способы Задания. Фото 180]

где [Автоматов Способы Задания. Фото 181] -, соответственно, входной и выходной алфавиты канонич. схемы. Эта схема задает структурный автомат [Автоматов Способы Задания. Фото 182], где [Автоматов Способы Задания. Фото 183] а функции [Автоматов Способы Задания. Фото 184] определяются следующим образом:

[Автоматов Способы Задания. Фото 185]

Важным примером структурных автоматов являются логич. сети (см. Автомат конечный). На рис. 6 представлена канонич. схема автомата [Автоматов Способы Задания. Фото 186] изоморфного автомату [Автоматов Способы Задания. Фото 187], диаграмма к-рого изображена на рис. 3, [Автоматов Способы Задания. Фото 188] Автомат [Автоматов Способы Задания. Фото 189] - автомат Мура такой, что [Автоматов Способы Задания. Фото 190]

Для описания структурных автоматов часто используются канонические уравнения, т. е. системы вида:

[Автоматов Способы Задания. Фото 191]

где [Автоматов Способы Задания. Фото 192] - целочисленный параметр, [Автоматов Способы Задания. Фото 193] а функции [Автоматов Способы Задания. Фото 194] и переменные х r , [Автоматов Способы Задания. Фото 195] принимают значения из множества А . Этой системе соответствует канонич. схема, в к-рой все элементы памяти совпадают: [Автоматов Способы Задания. Фото 196] где [Автоматов Способы Задания. Фото 197] Функционирование автомата [Автоматов Способы Задания. Фото 198] содержательно может быть описано следующим образом. Пусть в момент времени t входу [Автоматов Способы Задания. Фото 199] приписана буква [Автоматов Способы Задания. Фото 200] тогда эта же буква будет приписана выходу [Автоматов Способы Задания. Фото 201] в момент [Автоматов Способы Задания. Фото 202] На рис. 6 представлен автомат [Автоматов Способы Задания. Фото 203] канонич. уравнения к-рого имеют вид:

[Автоматов Способы Задания. Фото 204]

В общем случае описание структурных автоматов связано с заданием набора элементарных автоматов и не-к-рого класса "правильно устроенных" схем (сетей), причем последние обычно определяются индуктивно. Лит.:[1] Автоматы. Сб. статей, пер. с англ., М., 1956; [2] Глушков В. М., Синтез цифровых автоматов, М., 1962.

В. А. Буееич, С. В. Алешин.

  • ВКонтакте

  • Facebook

  • Мой мир@mail.ru

  • Twitter

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

  • Google+

См. также

  • , циклизация динитрилов, в к-рых группы CN разделены четырьмя и более атомами С (В-основание): Динитрилы, в молекуле к-рых между группами CN

  • род птиц сем. утиных. 3 вида, в Евразии, Сев. Африке и Австралии, обитают по берегам водоёмов. Обыкновенная П. (дл. ок. 60 см) - объект промысла (пу