![]() |
АВТОМАТОВ СПОСОБЫ ЗАДАНИЯРасстановка ударений: АВТОМА`ТОВ СПО`СОБЫ ЗАДА`НИЯ АВТОМАТОВ СПОСОБЫ ЗАДАНИЯ - варианты описания автоматов, их функционирования или поведения. А. с. з. зависят от подхода к определению понятия автомата. При макроподходе (см. Автомат конечный) описывается внешнее поведение автомата; при микроподходе задание должно содержать описание элементов, из к-рых строится автомат, и схемы их соединения. Ниже приводятся способы задания конечных автоматов.
Макроподход. В этом случае задать конечный автомат ![]() Рис. 1 ![]() Рис. 2
Диаграмма автомата (диаграмма переходов автомата) - это ориентированный граф G, вершинам к-рого взаимно однозначно соответствуют элементы S, а ребрам приписаны нек-рые множества пар вида (а, b), а ∈ А, b ∈ В. Из каждой вершины G исходит по крайней мере одно ребро; при этом множество ![]() Рис. 3 Матрица переходов используется для описания функционирования переходной системы 〈 A, S, φ 〉 (см. Автомат конечный). Она представляет собой (n × n) - матрицу P = ||Pij ||, элементами к-рой являются подмножества алфавита А (может быть, пустые) такие, что а ∈ Рij тогда и только тогда, когда φ (si, a) = sj и, следовательно, для всякого i = 1, 2, ..., n имеет место Pip ∩ Pir = ∅ при р ≠ r и ∩nj = 1 Pij = A. Чтобы распространить функцию φ на множество S × A* (А* - множество всех слов в алфавите А, включая пустое слово), рассматривают последовательность степеней матрицы Р. Умножение матрицы Р на себя производится по обычному алгоритму с использованием вместо операций умножения и сложения операций произведения (конкатенации) и объединения множеств слов. Если α ∈ А* - слово длины d и α ∈ Pij(d) где Pij(d) - элемент матрицы Pd, то φ (si, α) = sj . Так, матрица переходов Р переходной системы 〈 А0, S0, φ0 〉 и матрица Р2 имеют, соответственно, вид: ![]() С указанными А. с. з. связан ряд алгоритмов минимизации (приведения) и синтеза автоматов.
Для задания поведения инициального (не обязательно конечного) автомата ![]() Рис. 4 Описание поведения конечного автомата (акцептора) в терминах представимого события (сверхсобытия) может быть сделано с помощью регулярного выражения (см. Регулярное событие). Такие события могут быть также заданы как множества слов, порождаемых (выводимых) в нек-рой формальной системе (полу-Туэ грамматике и т. п.). Система полу-Туэ в этом случае задается четверкой Т = (A, S, ξ, ω), где A, S - конечные алфавиты, A ∩ S = ∅, ξ - аксиом схема вида s0 X и ω - множество схем правил вывода вида saX → s'X, r → r, где s, s', r ∈ S, а ∈ А и X - переменная, принимающая значения из А* . При этом, если saX → s'X и saX → s''X принадлежат ω, то s' = s''. Слово α ∈ А* выводимо в системе Т, если существует последовательность слов s0 α = w1, w2, ..., wn такая, что wi + 1 получается из wi, i = 1, ..., n - 1, применением нек-рого правила из ω, wn ∈ S и ω не содержит правила wn → wn . Аналогичный вид имеет грамматика, порождающая регулярное событие. Она задается четверкой Г = (А, S, s1, ω), где s1 из S - аксиома, ω - множество правил вида si → asj, либо si → а. Слово α = α1 α2 ...αn выводимо в Г, если в ω имеются правила s1 → α1 si2, si2 → α2 si3, ..., sin → αn . Известны алгоритмы, позволяющие получать матрицу переходов автомата по формальным системам описанного типа. Так, событие, представимое в акцепторе 〈 А0, S0, φ0, s1 〉 состоянием s2, может быть, напр., задано как множество слов, выводимых в системе полу-Туэ, к-рая имеет вид: ![]() Существует ряд других А. с. з. Напр., переходная система 〈 А, S, φ 〉, не обязательно конечная, может быть задана как алгебра 〈 S, Ф&$62;, где Ф = {φa |а ∈ A} есть множество унарных операций на S таких, что φa (s) = φ (а, s). Так, переходную систему 〈 А0, S0, φ0 〉 можно рассматривать как алгебру 〈 S0, {φa1, φa2} 〉, где φa1 (s1) = s1, φa1 (s2) = s2, φa2 (s2) = s1, φa1 (s1) = s1 . Можно также рассматривать алгебру 〈 S̃, Ф̃ 〉, где S̃ - множество слов вида sα, s ∈ S, α ∈ А*, и Ф̃ = {φ ̃a |a ∈ A} - множество унарных операций на S̃ таких, что φ̃a (sa) = sα a. Алгебра 〈 S̃, Ф̃ 〉 задается системой образующих S и множеством определяющих соотношений ω = {si αi = s'i α 'i, i = 1, 2...}. Такая алгебра задает автомат (вообще говоря, частичный) 〈 A, S, φ 〉 такой, что если si αi = s'i α 'i - соотношение из ω, то φ (si αi) = φ (s'i α 'i). Напр., переходную систему 〈 A0, S0, φ0 〉 можно задать системой образующих S0 и множеством определяющих соотношений ω = {s1 = s1 a1, s1 = s2 a2, s2 = s1 a2, s2 = s2 a1}. При этом предполагается, что φ (s1, Λ) = s1, φ (s2, Λ) = s2 . Поведение автомата может быть описано средствами языка логики одноместных предикатов. При этом выбор класса формул, задающих конечные автоматы, осуществляется различными способами. Описание может быть неполным, тогда оно определяет нек-рый класс автоматов, поведение к-рых идентично с точностью до этого описания. Напр., «анкетный» подход связан с заданием класса автоматов с помощью фрагментов информационных деревьев, частичного определения функций φ и ω и т. п. Указанные А. с. з. могут быть использованы с соответствующими модификациями при макроподходе к поведению нек-рых обобщений конечных автоматов (недетерминированных, бесконечных и т. п., см. Автомат). Так, элементами таблицы Tφ конечного недетерминированного автомата могут быть произвольные подмножества множества S. Поведение конечного недетерминированного акцептора описывается регулярным выражением, как и в детерминированном случае. Другими обобщениями конечных автоматов являются конечные автоматы вероятностные, автоматы над термами, мозаичные структуры и т. п. Задать вероятностный автомат 〈 A, S, B, μ 〉, если известны алфавиты A = {a1, ..., am}, В = {b1, ..., bk}, S = {s1, ..., sn), - значит при любых фиксированных i и j (l ≤ : i ≤ n, 1 ≤ j ≤ m) указать условную вероятностную меру μij (sr, bq) нa множестве всех пар (sr, bq), r = 1, ..., n, q = 1, ..., к. Для этого обычно рассматривают систему квадратных матриц с неотрицательными элементами ![]()
такую, что каждая матрица ![]()
Иногда при задании вероятностных автоматов ограничиваются либо указанием матриц Мj, либо указанием матриц ![]()
i = 1, ..., n, q = 1, ..., k, j = 1, ..., m. Любая конечная Маркова цепь может рассматриваться как конечный вероятностный автомат, у к-рого матрицы Мj, j = 1, ..., m, совпадают. Ниже представлены система матриц, задающая нек-рый вероятностный автомат ![]() Чтобы задать конечный автомат над термами 〈 A, S, σ, αa 〉, когда известны алфавиты А = {a1, ..., am}, S = {s1, ..., sn}, необходимо, во-первых, указать отображение σ множества А в конечное множество неотрицательных целых чисел, причем так, чтобы существовал хотя бы один элемент а ∈ А такой, что σ (a) = 0, а во-вторых, для всякого аi ∈ A, i = 1, ..., m, требуется определить σ (ai)-местную функцию αai, отображающую множество [S]σ (ai) = S ×... × S в S. Каждому элементу а ∈ А такому, что σ (а) = 0, ставится в соответствие элемент αa ∈ S, наз. начальным состоянием автомата. Напр., если А = {а1, а2}, S = {s1, s2}, σ (а1) = 0, σ (а2) = 2, αa1 = s1, αa2 (s1, s1) = s2, αa2 (s1, s2) = s1, αa2 (s2, s1) = s2, αa2 (s2, s2) = s2, то функции σ, αa1, αa2 задают нек-рый автомат над термами (А, S, σ, {αa1, αa2}) с начальным состоянием s1 . Чтобы задать мозаичную структуру (бесконечное соединение переходных систем вида 〈 A, S, φ 〉, где А = Sr, см. Автомат), необходимо для каждой целочисленной точки n-мерного пространства определить конечное упорядоченное множество целочисленных точек - ее окрестность. При этом входной алфавит А переходной системы 〈 A, S, φ 〉, помещенной в нек-рую точку, есть декартово произведение множеств состояний переходных систем, помещенных в точки ее окрестности. Напр., пусть S = {s1, s2} и для всякой целочисленной точки двумерного пространства (α, β) ее окрестность Dα, β есть упорядоченное множество {(α - 1, β), (α, β + 1), (α + 1, β)} - Чтобы задать однородную двумерную мозаичную структуру, определяют функцию φ следующим образом: φ (s1, s1) = s1, φ (s', s', s''') = s2 в остальных случаях. Входной алфавит А в данном случае - декартово произведение S × S × S.
Микроподход. При микроподходе задать структурный автомат - значит описать элементы, из к-рых он построен, и схему их соединения. Описание может производиться на различных уровнях детализации. Часто ограничиваются рассмотрением так наз. канонической схемы построения автоматов; при этом элементы делят на две группы - функциональные элементы (автоматы с одним состоянием) и элементы памяти. Канонич. схема (рис. 5) состоит из двух функциональных блоков f и g с присоединенными к ним элементами памяти, в качестве к-рых используются автоматы Мура: ![]() где An и Bm -, соответственно, входной и выходной алфавиты канонич. схемы. Эта схема задает структурный автомат 〈 Аn, S, Вm, φ, ψ 〉, где S = S1 ×... × Sl, а функции φ и ψ определяются следующим образом: ![]()
Важным примером структурных автоматов являются логич. сети (см. Автомат конечный). На рис. 6 представлена канонич. схема автомата 〈 А̃, S̃, В̃, φ̃, ψ̃ 〉, изоморфного автомату ![]() Рис. 5. ![]() Рис. 6. Для описания структурных автоматов часто используются канонические уравнения, т. е. системы вида: ![]()
где t = 1, 2,... - целочисленный параметр, s0 ∈ S, а функции fi, i = 1, ..., l, gi, i = 1, ..., m и переменные хr, r = 1, ..., n, принимают значения из множества А. Этой системе соответствует канонич. схема, в к-рой все элементы памяти совпадают: ![]() В общем случае описание структурных автоматов связано с заданием набора элементарных автоматов и нек-рого класса «правильно устроенных» схем (сетей), причем последние обычно определяются индуктивно. Лит. : [1] Автоматы. Сб. статей, пер. с англ., М., 1956; [2] Глушков В. М., Синтез цифровых автоматов, М., 1962. В. А. Буевич, С. В. Алешин. Источники:
|
![]()
|
|||
![]() |
|||||
© MATHEMLIB.RU, 2001-2021
При копировании материалов проекта обязательно ставить ссылку на страницу источник: http://mathemlib.ru/ 'Математическая библиотека' |