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

Варианты описания автоматов, их функционирования или поведения. А. с. з. зависят от подхода к определению понятия автомата. При макроподходе (см. Автомат конечный).описывается внешнее поведение автомата; при микроподходе задание должно содержать описание элементов, из к-рых строится автомат, и схемы их соединения. Ниже приводятся способы задания конечных автоматов. Макроподход. В этом случае задать конечный автомат при условии, что заданы алфавиты значит описать функции или описать поведение этого автомата (см. Автомата поведение). Для задания функций обычно используют таблицу переходов, диаграмму переходов или матрицу переходов. Таблица переходов Тавтомата состоит из двух подтаблиц , Функции определяются как Если все столбцы совпадают, то таблица Тзадает автомат Мура. Напр., пусть тогда таблица Т(рис. 1) задает функции нек-рого автомата (на рис. 2 показаны подтаблицы таблицы Т). Диаграмма автомата (диаграмма переходов автомата) — это ориентированный граф G, вершинам к-рого взаимно однозначно соответствуют элементы 5, а ребрам приписаны нек-рые множества пар вида Из каждой вершины G исходит по крайней мере одно ребро; при этом множество всех пар, приписанных ребрам, исходящим из одной вершины, имеет вид Функции j и y) определяются следующим образом: если ребру, исходящему из вершины si , приписана пара ( а i , b р).и это ребро ведет в вершину sr . Нек-рые свойства автоматов удобно формулировать на языке диаграмм (связность автомата, достижимость состояний и т. п.). На рис. 3 представлена диаграмма переходов автомата Матрица переходов используется для описания функционирования переходной системы (см. Автомат конечный). Она представляет собой элементами к-рой являются подмножества алфавита А(может быть, пустые) такие, что тогда и только тогда, когда и, следовательно, для всякого имеет место Чтобы распространить функцию на множество (. — множество всех слов в алфавите А, включая пустое слово), рассматривают последовательность степеней матрицы Р. Умножение матрицы Рна себя производится по обычному алгоритму с использованием вместо операций умножения и сложения операций произведения (к о н-катенации) и объединения множеств слов. Если — слово длины — элемент матрицы Так, матрица переходов Рпереходной системы и матрица имеют, соответственно, вид: С указанными А. с. з. связан ряд алгоритмов минимизации (приведения) и синтеза автоматов. Для задания поведения инициального (не обязательно конечного) автомата (преобразователя) необходимо описать функцию отображающую (или в — множества всех сверхслов в алфавитах Аи В, соответственно). Эта функция может быть задана информационным деревом. Из каждой вершины информационного дерева исходит ребер, взаимно однозначно соответствующих буквам алфавита . Каждой вершине приписано состояние автомата а каждому ребру — буква алфавита Вследующим образом. Корню приписано состояние Если нек-рой вершине приписано состояние то ребру, соответствующему букве приписана буква и вершине, в к-рую ведет это ребро, приписано состояние Каждому слову соответствует единственная последовательность ребер этого дерева такая, что исходит из корня и исходит из вершины, в к-рую ведет Слово где — буква из В, приписанная ребру совпадает со значением Если функция f реализуется конечным автоматом, то соответствующее информационное дерево может быть задано эффективно своим конечным поддеревом. На рис. 4 изображено поддерево информационного дерева, задающее поведение инициального автомата (левые ребра, исходящие из вершин, соответствуют символу правые — символу ). Описание поведения конечного автомата (акцептора) в терминах представимого события (сверхсобытия) может быть сделано с помощью регулярного выражения (см. Регулярное событие). Такие события могут быть также заданы как множества слов, порождаемых (выводимых) в нек-рой формальной системе (полу-Туэ грамматике и т. п.). Система полу-Туэ в этом случае задается четверкой где — конечные алфавиты, — аксиом схема вида и — множество схем правил вывода вида где — переменная, принимающая значения из . При этом, если и принадлежат то . Слово выводимо в системе если существует последовательность слов такая, что получается из применением нек-рого правила из не содержит правила Аналогичный вид имеет грамматика, порождающая регулярное событие. Она задается четверкой где из — аксиома, — множество правил вида либо Слово выводимо в Г, если в w имеются правила Известны алгоритмы, позволяющие получать матрицу переходов автомата по формальным системам описанного типа. Так, событие, представимое в акцепторе состоянием может быть, напр., задано как множество слов, выводимых в системе полу-Туэ, к-рая имеет вид: Существует ряд других А. с. з. Напр., переходная система не обязательно конечная, может быть задана как алгебра где есть множество унарных операций на таких, что Так, переходную систему можно рассматривать как алгебру Можно также рассматривать алгебру , где — множество слов вида — множество унарных операций на таких, что Алгебра задается системой образующих Sи множеством определяющих соотношений Такая алгебра задает автомат воооще говоря, частичный) такой, что если — соотношение из Напр., переходную систему можно задать системой образующих и множеством определяющих соотношений При этом предполагается, что Поведение автомата может быть описано средствами языка логики одноместных предикатов. При этом выбор класса формул, задающих конечные автоматы, осуществляется различными способами. Описание может быть неполным, тогда оно определяет нек-рый класс автоматов, поведение к-рых идентично с точностью до этого описания. Напр., "анкетный" подход связан с заданием класса автоматов с помощью фрагментов информационных деревьев, частичного определения функций j и y и т. п. Указанные А. с. з. могут быть использованы с соответствующими модификациями при макроподходе к поведению нек-рых обобщений конечных автоматов (недетерминированных, бесконечных и т. п., см. Автомат), Так, элементами таблицы конечного недетерминированного автомата могут быть произвольные подмножества множества S. Поведение конечного недетерминированного акцептора описывается регулярным выражением, как и в детерминированном случае. Другими обобщениями конечных автоматов являются конечные автоматы вероятностные, автоматы над термами, мозаичные структуры и т. п. Задать вероятностный автомат если известны алфавиты — значит при любых фиксированных iи указать условную вероятностную меру | на множестве всех пар Для этого обычно рассматривают систему квадратных матриц с неотрицательными элементами такую, что каждая матрица является стохастической. Мера определяется так: Вероятностный автомат рассматривается совместно с нек-рым начальным распределением вероятностей на множестве Иногда при задании вероятностных автоматов ограничиваются либо указанием матриц , либо указанием матриц где Любая конечная Маркова цепь может рассматриваться как конечный вероятностный автомат, у к-рого матрицы совпадают. Ниже представлены система матриц, задающая нек-рый вероятностный автомат и матрицы этого автомата: Чтобы задать конечный автомат над термами когда известны алфавиты необходимо, во-первых, указать отображение а множества Ав конечное множество неотрицательных целых чисел, причем так, чтобы существовал хотя бы один элемент такой, что а во-вторых, для всякого требуется определить -местную функцию отображающую множество Каждому элементу такому, что ставится в соответствие элемент наз. начальным состоянием автомата. Напр., если то функции задают нек-рый автомат над термами с начальным состоянием Чтобы задать мозаичную структуру (бесконечное соединение переходных систем вида где А , см. Автомат), необходимо для каждой целочисленной точки n-мерного пространства определить конечное упорядоченное множество целочисленных точек — ее окрестность. При этом входной алфавит Апереходной системы помещенной в нек-рую точку, есть декартово произведение множеств состояний переходных систем, помещенных в точки ее окрестности. Напр., пусть и для всякой целочисленной точки двумерного пространства ее окрестность есть упорядоченное множество Чтобы задать однородную двумерную мозаичную структуру, определяют функцию j следующим образом: в остальных случаях. Входной алфавит Ав данном случае — декартово произведение Микроподход. При микроподходе задать структурный автомат — значит описать элементы, из к-рых он построен, и схему их соединения. Описание может производиться на различных уровнях детализации. Часто ограничиваются рассмотрением так наз. канонической схемы построения автоматов; при этом элементы делят на две группы — функциональные элементы (автоматы с одним состоянием) и элементы памяти. Канонич. схема (рис. 5) состоит из двух функциональных блоков f и gс присоединенными к ним элементами памяти, в качестве к-рых используются автоматы Мура: Блоки построены из функциональных элементов. При данном способе задания структуру этих блоков не описывают, а задают (напр., таблично) реализуемые ими вектор-функции: где -, соответственно, входной и выходной алфавиты канонич. схемы. Эта схема задает структурный автомат , где а функции определяются следующим образом: Важным примером структурных автоматов являются логич. сети (см. Автомат конечный). На рис. 6 представлена канонич. схема автомата изоморфного автомату , диаграмма к-рого изображена на рис. 3, Автомат — автомат Мура такой, что Для описания структурных автоматов часто используются канонические уравнения, т. е. системы вида: где — целочисленный параметр, а функции и переменные х r , принимают значения из множества А . Этой системе соответствует канонич. схема, в к-рой все элементы памяти совпадают: где Функционирование автомата содержательно может быть описано следующим образом. Пусть в момент времени t входу приписана буква тогда эта же буква будет приписана выходу в момент На рис. 6 представлен автомат канонич. уравнения к-рого имеют вид: В общем случае описание структурных автоматов связано с заданием набора элементарных автоматов и не-к-рого класса "правильно устроенных" схем (сетей), причем последние обычно определяются индуктивно. Лит.:[1] Автоматы. Сб. статей, пер. с англ., М., 1956; [2] Глушков В. М., Синтез цифровых автоматов, М., 1962. В. А. Буееич, С. В. Алешин.