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

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

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

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

языке диаграмм (связность автомата, достижимость состояний и т. п.). На рис. 3 представлена диаграмма переходов автомата

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

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

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

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

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

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

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

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

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

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

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

Задать вероятностный автомат если известны алфавиты значит при любых фиксированных iи указать условную вероятностную меру | на множестве всех пар Для этого обычно рассматривают систему квадратных матриц с неотрицательными элементами

такую, что каждая матрица является стохастической. Мера определяется так: Вероятностный автомат рассматривается совместно с нек-рым начальным распределением вероятностей на множестве