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

- варианты описания автоматов, их функционирования или поведения. А. с. з. зависят от подхода к определению понятия автомата. При макроподходе (см. Автомат конечный).описывается внешнее поведение автомата; при микроподходе задание должно содержать описание элементов, из к-рых строится автомат, и схемы их соединения. Ниже приводятся способы задания конечных автоматов. Макроподход. В этом случае задать конечный автомат [img: http://localhost:8080/file/010106-174.jpg] при условии, что заданы алфавиты значит [img: http://localhost:8080/file/010106-175.jpg] описать функции [img: http://localhost:8080/file/010106-176.jpg] или описать поведение этого автомата (см. Автомата поведение). Для задания функций [img: http://localhost:8080/file/010106-177.jpg] обычно используют таблицу переходов, диаграмму переходов или матрицу переходов. Таблица переходов Тавтомата [img: http://localhost:8080/file/010106-178.jpg] состоит из двух подтаблиц [img: http://localhost:8080/file/010106-179.jpg] [img: http://localhost:8080/file/010106-180.jpg], Функции [img: http://localhost:8080/file/010106-181.jpg] определяются как [img: http://localhost:8080/file/010106-182.jpg] Если все столбцы [img: http://localhost:8080/file/010106-183.jpg] совпадают, то таблица Тзадает автомат Мура. Напр., пусть [img: http://localhost:8080/file/010106-184.jpg] тогда таблица Т(рис. 1) задает функции [img: http://localhost:8080/file/010106-185.jpg] нек-рого автомата [img: http://localhost:8080/file/010106-186.jpg] (на рис. 2 показаны подтаблицы [img: http://localhost:8080/file/010106-187.jpg] таблицы Т). [img: http://localhost:8080/file/010106-188.jpg] Диаграмма автомата (диаграмма переходов автомата) - это ориентированный граф G, вершинам к-рого взаимно однозначно соответствуют элементы 5, а ребрам приписаны нек-рые множества пар вида [img: http://localhost:8080/file/010106-189.jpg] Из каждой вершины G исходит по крайней мере одно ребро; при этом множество [img: http://localhost:8080/file/010106-190.jpg] всех пар, приписанных ребрам, исходящим из одной вершины, имеет вид [img: http://localhost:8080/file/010106-191.jpg] [img: http://localhost:8080/file/010106-192.jpg] Функции j и y) определяются следующим образом: [img: http://localhost:8080/file/010106-193.jpg] если ребру, исходящему из вершины si, приписана пара (а i, b р).и это ребро ведет в вершину sr. Нек-рые свойства автоматов удобно формулировать на [img: http://localhost:8080/file/010106-194.jpg] языке диаграмм (связность автомата, достижимость состояний и т. п.). На рис. 3 представлена диаграмма переходов автомата [img: http://localhost:8080/file/010106-195.jpg] Матрица переходов используется для описания функционирования переходной системы [img: http://localhost:8080/file/010106-196.jpg] (см. Автомат конечный). Она представляет собой [img: http://localhost:8080/file/010106-197.jpg] элементами к-рой являются подмножества алфавита А(может быть, пустые) такие, что [img: http://localhost:8080/file/010107-1.jpg] тогда и только тогда, когда [img: http://localhost:8080/file/010107-2.jpg] и, следовательно, для всякого [img: http://localhost:8080/file/010107-3.jpg] имеет место [img: http://localhost:8080/file/010107-4.jpg] Чтобы распространить функцию [img: http://localhost:8080/file/010107-5.jpg] на множество [img: http://localhost:8080/file/010107-6.jpg] (. [img: http://localhost:8080/file/010107-7.jpg] - множество всех слов в алфавите А, включая пустое слово), рассматривают последовательность степеней матрицы Р. Умножение матрицы Рна себя производится по обычному алгоритму с использованием вместо операций умножения и сложения операций произведения (к о н-катенации) и объединения множеств слов. Если [img: http://localhost:8080/file/010107-8.jpg] - слово длины [img: http://localhost:8080/file/010107-9.jpg] - элемент матрицы [img: http://localhost:8080/file/010107-10.jpg] Так, матрица переходов Рпереходной системы [img: http://localhost:8080/file/010107-11.jpg] и матрица [img: http://localhost:8080/file/010107-12.jpg] имеют, соответственно, вид: [img: http://localhost:8080/file/010107-13.jpg] С указанными А. с. з. связан ряд алгоритмов минимизации (приведения) и синтеза автоматов. [img: http://localhost:8080/file/010107-19.jpg] Для задания поведения инициального (не обязательно конечного) автомата [img: http://localhost:8080/file/010107-14.jpg] (преобразователя) необходимо описать функцию [img: http://localhost:8080/file/010107-15.jpg] отображающую [img: http://localhost:8080/file/010107-16.jpg] (или [img: http://localhost:8080/file/010107-17.jpg] в [img: http://localhost:8080/file/010107-18.jpg] - множества всех сверхслов в алфавитах Аи В, соответственно). Эта функция может быть задана информационным деревом. Из каждой вершины информационного дерева исходит [img: http://localhost:8080/file/010107-20.jpg] ребер, взаимно однозначно соответствующих буквам алфавита [img: http://localhost:8080/file/010107-21.jpg]. Каждой вершине приписано состояние автомата [img: http://localhost:8080/file/010107-22.jpg] а каждому ребру - буква алфавита Вследующим образом. Корню приписано состояние [img: http://localhost:8080/file/010107-23.jpg] Если нек-рой вершине приписано состояние [img: http://localhost:8080/file/010107-24.jpg] то ребру, соответствующему букве [img: http://localhost:8080/file/010107-25.jpg] приписана буква [img: http://localhost:8080/file/010107-26.jpg] и вершине, в к-рую ведет это ребро, приписано состояние [img: http://localhost:8080/file/010107-27.jpg] Каждому слову [img: http://localhost:8080/file/010107-28.jpg] [img: http://localhost:8080/file/010107-29.jpg] соответствует единственная последовательность [img: http://localhost:8080/file/010107-30.jpg] ребер этого дерева такая, что [img: http://localhost:8080/file/010107-31.jpg] исходит из корня и [img: http://localhost:8080/file/010107-32.jpg] исходит из вершины, в к-рую ведет [img: http://localhost:8080/file/010107-33.jpg] Слово [img: http://localhost:8080/file/010107-34.jpg] где [img: http://localhost:8080/file/010107-35.jpg] - буква из В, приписанная ребру [img: http://localhost:8080/file/010107-36.jpg] совпадает со значением [img: http://localhost:8080/file/010107-37.jpg] Если функция f реализуется конечным автоматом, то соответствующее информационное дерево может быть задано эффективно своим конечным поддеревом. На рис. 4 изображено поддерево информационного дерева, задающее поведение инициального автомата [img: http://localhost:8080/file/010107-38.jpg] (левые ребра, исходящие из вершин, соответствуют символу [img: http://localhost:8080/file/010107-39.jpg] правые - символу [img: http://localhost:8080/file/010107-40.jpg]). Описание поведения конечного автомата (акцептора) в терминах представимого события (сверхсобытия) может быть сделано с помощью регулярного выражения (см. Регулярное событие). Такие события могут быть также заданы как множества слов, порождаемых (выводимых) в нек-рой формальной системе (полу-Туэ грамматике и т. п.). Система полу-Туэ в этом случае задается четверкой [img: http://localhost:8080/file/010107-41.jpg] где [img: http://localhost:8080/file/010107-42.jpg] - конечные алфавиты, [img: http://localhost:8080/file/010107-43.jpg] - аксиом схема вида [img: http://localhost:8080/file/010107-44.jpg] и [img: http://localhost:8080/file/010107-45.jpg] - множество схем правил вывода вида [img: http://localhost:8080/file/010107-46.jpg] где [img: http://localhost:8080/file/010107-47.jpg] - переменная, принимающая значения из [img: http://localhost:8080/file/010107-48.jpg]. При этом, если [img: http://localhost:8080/file/010107-49.jpg] и [img: http://localhost:8080/file/010107-50.jpg] принадлежат [img: http://localhost:8080/file/010107-51.jpg] то [img: http://localhost:8080/file/010107-52.jpg]. Слово [img: http://localhost:8080/file/010107-53.jpg] выводимо в системе [img: http://localhost:8080/file/010107-54.jpg] если существует последовательность слов [img: http://localhost:8080/file/010107-55.jpg] [img: http://localhost:8080/file/010107-56.jpg] такая, что [img: http://localhost:8080/file/010107-57.jpg] получается из [img: http://localhost:8080/file/010107-58.jpg] [img: http://localhost:8080/file/010107-59.jpg] применением нек-рого правила из [img: http://localhost:8080/file/010107-60.jpg] не содержит правила [img: http://localhost:8080/file/010107-61.jpg] Аналогичный вид имеет грамматика, порождающая регулярное событие. Она задается четверкой [img: http://localhost:8080/file/010107-62.jpg] где [img: http://localhost:8080/file/010107-63.jpg] из [img: http://localhost:8080/file/010107-64.jpg] - аксиома, [img: http://localhost:8080/file/010107-65.jpg] - множество правил вида [img: http://localhost:8080/file/010107-66.jpg] либо [img: http://localhost:8080/file/010107-67.jpg] Слово [img: http://localhost:8080/file/010107-68.jpg] выводимо в Г, если в w имеются правила [img: http://localhost:8080/file/010107-69.jpg] Известны алгоритмы, позволяющие получать матрицу переходов автомата по формальным системам описанного типа. Так, событие, представимое в акцепторе [img: http://localhost:8080/file/010107-70.jpg] состоянием [img: http://localhost:8080/file/010107-71.jpg] может быть, напр., задано как множество слов, выводимых в системе полу-Туэ, к-рая имеет вид: [img: http://localhost:8080/file/010107-72.jpg] Существует ряд других А. с. з. Напр., переходная система [img: http://localhost:8080/file/010107-73.jpg] не обязательно конечная, может быть задана как алгебра [img: http://localhost:8080/file/010107-74.jpg] где [img: http://localhost:8080/file/010107-75.jpg] есть множество унарных операций на [img: http://localhost:8080/file/010107-76.jpg] таких, что [img: http://localhost:8080/file/010107-77.jpg] Так, переходную систему [img: http://localhost:8080/file/010107-78.jpg] можно рассматривать как алгебру [img: http://localhost:8080/file/010107-79.jpg] [img: http://localhost:8080/file/010107-80.jpg] Можно также рассматривать алгебру [img: http://localhost:8080/file/010107-81.jpg], где [img: http://localhost:8080/file/010107-82.jpg] - множество слов вида [img: http://localhost:8080/file/010107-83.jpg] - множество унарных операций на [img: http://localhost:8080/file/010107-84.jpg] таких, что [img: http://localhost:8080/file/010107-85.jpg] Алгебра [img: http://localhost:8080/file/010107-86.jpg] задается системой образующих Sи множеством определяющих соотношений [img: http://localhost:8080/file/010107-87.jpg] Такая алгебра задает автомат воооще говоря, частичный) [img: http://localhost:8080/file/010107-88.jpg] такой, что если [img: http://localhost:8080/file/010107-89.jpg] - соотношение из [img: http://localhost:8080/file/010107-90.jpg] Напр., переходную систему [img: http://localhost:8080/file/010107-91.jpg] можно задать системой образующих [img: http://localhost:8080/file/010107-92.jpg] и множеством определяющих соотношений [img: http://localhost:8080/file/010107-93.jpg] [img: http://localhost:8080/file/010107-94.jpg] При этом предполагается, что [img: http://localhost:8080/file/010107-95.jpg] Поведение автомата может быть описано средствами языка логики одноместных предикатов. При этом выбор класса формул, задающих конечные автоматы, осуществляется различными способами. Описание может быть неполным, тогда оно определяет нек-рый класс автоматов, поведение к-рых идентично с точностью до этого описания. Напр., "анкетный" подход связан с заданием класса автоматов с помощью фрагментов информационных деревьев, частичного определения функций j и y и т. п. Указанные А. с. з. могут быть использованы с соответствующими модификациями при макроподходе к поведению нек-рых обобщений конечных автоматов (недетерминированных, бесконечных и т. п., см. Автомат), Так, элементами таблицы [img: http://localhost:8080/file/010107-96.jpg] конечного недетерминированного автомата могут быть произвольные подмножества множества S. Поведение конечного недетерминированного акцептора описывается регулярным выражением, как и в детерминированном случае. Другими обобщениями конечных автоматов являются конечные автоматы вероятностные, автоматы над термами, мозаичные структуры и т. п. Задать вероятностный автомат [img: http://localhost:8080/file/010107-97.jpg] если известны алфавиты [img: http://localhost:8080/file/010107-98.jpg] [img: http://localhost:8080/file/010107-99.jpg] - значит при любых фиксированных iи [img: http://localhost:8080/file/010107-100.jpg] указать условную вероятностную меру | [img: http://localhost:8080/file/010107-101.jpg] на множестве всех пар [img: http://localhost:8080/file/010107-102.jpg] [img: http://localhost:8080/file/010107-103.jpg] Для этого обычно рассматривают систему квадратных матриц с неотрицательными элементами [img: http://localhost:8080/file/010107-104.jpg] такую, что каждая матрица [img: http://localhost:8080/file/010107-105.jpg] является стохастической. Мера [img: http://localhost:8080/file/010107-106.jpg] определяется так: [img: http://localhost:8080/file/010107-107.jpg] [img: http://localhost:8080/file/010107-108.jpg] Вероятностный автомат [img: http://localhost:8080/file/010107-109.jpg] рассматривается совместно с нек-рым начальным распределением вероятностей на множестве [img: http://localhost:8080/file/010107-110.jpg] [img: http://localhost:8080/file/010107-111.jpg] Иногда при задании вероятностных автоматов ограничиваются либо указанием матриц [img: http://localhost:8080/file/010107-112.jpg], либо указанием матриц [img: http://localhost:8080/file/010107-113.jpg] где [img: http://localhost:8080/file/010107-114.jpg] [img: http://localhost:8080/file/010107-115.jpg] Любая конечная Маркова цепь может рассматриваться как конечный вероятностный автомат, у к-рого матрицы [img: http://localhost:8080/file/010107-116.jpg] [img: http://localhost:8080/file/010107-117.jpg] совпадают. Ниже представлены система матриц, задающая нек-рый вероятностный автомат [img: http://localhost:8080/file/010107-118.jpg] [img: http://localhost:8080/file/010107-119.jpg] и матрицы [img: http://localhost:8080/file/010107-120.jpg] этого автомата: [img: http://localhost:8080/file/010107-121.jpg] Чтобы задать конечный автомат над термами [img: http://localhost:8080/file/010107-122.jpg] [img: http://localhost:8080/file/010107-123.jpg] когда известны алфавиты [img: http://localhost:8080/file/010107-124.jpg] [img: http://localhost:8080/file/010107-125.jpg] [img: http://localhost:8080/file/010107-126.jpg] необходимо, во-первых, указать отображение а множества Ав конечное множество неотрицательных целых чисел, причем так, чтобы существовал хотя бы один элемент [img: http://localhost:8080/file/010107-127.jpg] такой, что [img: http://localhost:8080/file/010107-128.jpg] а во-вторых, для всякого [img: http://localhost:8080/file/010107-129.jpg] требуется определить [img: http://localhost:8080/file/010107-130.jpg] -местную функцию [img: http://localhost:8080/file/010107-131.jpg] отображающую множество [img: http://localhost:8080/file/010107-132.jpg] Каждому элементу [img: http://localhost:8080/file/010107-133.jpg] такому, что [img: http://localhost:8080/file/010107-134.jpg] ставится в соответствие элемент [img: http://localhost:8080/file/010107-135.jpg] наз. начальным состоянием автомата. Напр., если [img: http://localhost:8080/file/010107-136.jpg] [img: http://localhost:8080/file/010107-137.jpg] то [img: http://localhost:8080/file/010107-138.jpg] функции [img: http://localhost:8080/file/010107-139.jpg] задают нек-рый автомат над термами [img: http://localhost:8080/file/010107-140.jpg] с начальным состоянием [img: http://localhost:8080/file/010107-141.jpg] Чтобы задать мозаичную структуру (бесконечное соединение переходных систем вида [img: http://localhost:8080/file/010107-142.jpg] где А [img: http://localhost:8080/file/010107-143.jpg], см. Автомат), необходимо для каждой целочисленной точки n-мерного пространства определить конечное упорядоченное множество целочисленных точек - ее окрестность. При этом входной алфавит Апереходной системы [img: http://localhost:8080/file/010107-144.jpg] помещенной в нек-рую точку, есть декартово произведение множеств состояний переходных систем, помещенных в точки ее окрестности. Напр., пусть [img: http://localhost:8080/file/010107-145.jpg] и для всякой целочисленной точки двумерного пространства [img: http://localhost:8080/file/010107-146.jpg] ее окрестность [img: http://localhost:8080/file/010107-147.jpg] есть упорядоченное множество [img: http://localhost:8080/file/010107-148.jpg] [img: http://localhost:8080/file/010107-149.jpg] Чтобы задать однородную двумерную мозаичную структуру, определяют функцию j следующим образом: [img: http://localhost:8080/file/010107-150.jpg] в остальных случаях. Входной алфавит Ав данном случае - декартово произведение [img: http://localhost:8080/file/010107-151.jpg] Микроподход. При микроподходе задать структурный автомат - значит описать элементы, из к-рых он построен, и схему их соединения. Описание может производиться на различных уровнях детализации. Часто ограничиваются рассмотрением так наз. канонической схемы построения автоматов; при этом элементы делят на две группы - функциональные элементы (автоматы с одним состоянием) и элементы памяти. Канонич. схема (рис. 5) состоит из двух функциональных блоков f и gс присоединенными к ним элементами памяти, в качестве к-рых используются автоматы Мура: [img: http://localhost:8080/file/010107-152.jpg] [img: http://localhost:8080/file/010107-153.jpg] Блоки [img: http://localhost:8080/file/010107-154.jpg] построены из функциональных элементов. При данном способе задания структуру этих блоков не описывают, а задают (напр., таблично) реализуемые ими вектор-функции: [img: http://localhost:8080/file/010107-155.jpg] [img: http://localhost:8080/file/010107-157.jpg] где [img: http://localhost:8080/file/010107-156.jpg] -, соответственно, входной и выходной алфавиты канонич. схемы. Эта схема задает структурный автомат [img: http://localhost:8080/file/010107-158.jpg], где [img: http://localhost:8080/file/010107-159.jpg] а функции [img: http://localhost:8080/file/010107-160.jpg] определяются следующим образом: [img: http://localhost:8080/file/010107-161.jpg] Важным примером структурных автоматов являются логич. сети (см. Автомат конечный). На рис. 6 представлена канонич. схема автомата [img: http://localhost:8080/file/010107-162.jpg] изоморфного автомату [img: http://localhost:8080/file/010107-163.jpg], диаграмма к-рого изображена на рис. 3, [img: http://localhost:8080/file/010107-164.jpg] Автомат [img: http://localhost:8080/file/010107-165.jpg] - автомат Мура такой, что [img: http://localhost:8080/file/010107-166.jpg] Для описания структурных автоматов часто используются канонические уравнения, т. е. системы вида: [img: http://localhost:8080/file/010107-167.jpg] где [img: http://localhost:8080/file/010107-168.jpg] - целочисленный параметр, [img: http://localhost:8080/file/010107-169.jpg] а функции [img: http://localhost:8080/file/010107-170.jpg] и переменные х r, [img: http://localhost:8080/file/010107-171.jpg] принимают значения из множества А. Этой системе соответствует канонич. схема, в к-рой все элементы памяти совпадают: [img: http://localhost:8080/file/010107-172.jpg] где [img: http://localhost:8080/file/010107-173.jpg] Функционирование автомата [img: http://localhost:8080/file/010107-174.jpg] содержательно может быть описано следующим образом. Пусть в момент времени t входу [img: http://localhost:8080/file/010107-175.jpg] приписана буква [img: http://localhost:8080/file/010107-176.jpg] тогда эта же буква будет приписана выходу [img: http://localhost:8080/file/010107-177.jpg] в момент [img: http://localhost:8080/file/010107-178.jpg] На рис. 6 представлен автомат [img: http://localhost:8080/file/010107-179.jpg] канонич. уравнения к-рого имеют вид: [img: http://localhost:8080/file/010107-180.jpg] В общем случае описание структурных автоматов связано с заданием набора элементарных автоматов и не-к-рого класса "правильно устроенных" схем (сетей), причем последние обычно определяются индуктивно.