Скелетные автоматы | ПДМ. 2011. № 2(12).

Скелетные автоматы

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

Skeleton automata.pdf Под автоматом понимается тройка A = (S, X, 8), где S и X - конечные непустыемножества (соответственно множество состояний и множество входных сигналов), а8 : S х X ^ S - отображение, называемое функцией переходов. Запись 8(s, x) = s' дляs,s' G S, x G X означает, что автомат A, находящийся в состоянии s, под действи-ем входного сигнала x переходит в следующий момент дискретного времени в со-стояние s'. Функция переходов естественным образом продолжается на множествоS х X*, где X* - совокупность всех конечных слов над алфавитом X: по определе-нию, 8(s,e) = s для любого s G S и пустого слова e, и 8(s,px) = 8(8(s,p),x) для любыхs S, x X, p X*.Автомату A сопоставляется диаграмма - мультиграф G(A), вершинами которогоявляются элементы множества S и дуги помечены элементами из X: из вершины sв вершину s' ведет дуга с меткой x, если 8(s,x) = s'. Другим объектом, связаннымс автоматом A, является матрица переходов M(A) -матрица размерности m х m,где m = | S| , элементами которой являются подмножества множества X, при этом[M(A)]i,j = {x G X : 8(si,x) = s , }.Говорят, что состояние s' достижимо в автомате A из состояния s, если существу-ет входное слово p G X*, такое, что 8(s,p) = s'. В этом случае пишут (s,s') G т, итак определенное отношение т С S х S называют отношением достижимости в ав-томате A. Понятно, что т рефлексивно и транзитивно, т. е. является квазипорядком.Его симметричная часть а = т П т - 1 называется отношением взаимной достижимостив автомате A. Классы эквивалентности а называют слоями автомата A. В [1] было вве-дено понятие каркаса автомата. Каркас автомата A - это упорядоченное множество(F(A), элементами которого являются слои автомата A, а порядком на множе-стве слоев F(A) = S/а - отношение, обратное отношению достижимости т, именноa(s') ^ a(s) (s',s) G т - 1 ^^ (s,s') G т. Очевидно, что для любого автомата Aвыполняются неравенства 1 ^ |F(A)| ^ |S|. Если |F(A)| = 1, т.е. отношение а уни-версально, a = S х S, автомат A называется сильносвязным. Если же |F(A)| = |S|,т. е. отношение а тождественно, а = А, автомат A называется скелетным. В скелетномавтомате отношение достижимости т является порядком на множестве состояний S.Поскольку в скелетном автомате A все слои одноэлементны, можно считать, чтов этом случае каркасом является множество S, упорядоченное обратной достижимо--1 стью т , так что S ^\ S / означает, что состояние S/ достижимо из состояния S.Нумерацией состояний автомата называется биективное отображение множестваего состояний S на начальный отрезок [1,m] натурального ряда. Нумерация, по опре-делению, является правильной, если (si,sj) . т i ^ j, т.е. если состояния, дости-жимые из данного состояния, имеют меньшие, чем у него, номера.Теорема 1. В автомате A существует правильная нумерация состояний тогда итолько тогда, когда A - скелетный автомат.Доказательство. Пусть в автомате A существует правильная нумерация со-стояний, но A не является скелетным, т. е. а = А. Тогда в A найдутся два различныхвзаимно достижимых состояния, скажем si и Sj. Так как (si,sj) . т, то i > j, а таккак (Sj, Si) . т, то j > i, что невозможно. Значит, а = А и A - скелетный автомат.Пусть теперь, напротив, дан скелетный автомат A и нужно правильно пронумеро-вать его состояния. Построим диаграмму каркаса F(A), отождествляя его элементыс соответствующими состояниями автомата A. Под высотой элемента S в каркасе F(A)понимается наибольшая из длин убывающих цепей, начинающихся с S. Диаграммустроим следующим образом: если / - наибольшая из высот элементов в каркасе, тона / + 1 горизонталях, пронумерованных снизу вверх числами 0,1,... ,/, расположимэлементы каркаса в соответствии с их высотами, а затем, двигаясь снизу вверх, будемсоединять прямолинейными отрезками каждый элемент S с его нижними соседями(т. е. с теми элементами, за которыми S непосредственно следует в смысле порядкав F(A)). Построив диаграмму каркаса F(A), пронумеруем его элементы (т.е. состоя-ния автомата A) слева направо и снизу вверх. Состояние S' достижимо из состояния Sв точности тогда, когда в диаграмме каркаса F(A) есть восходящая ломаная от S' к S.Но это означает, что в построенной нумерации S имеет больший номер, чем S', т. е.нумерация- правильная. Подмножество S' С S называется устойчивым в автомате A, если 8 ( S , X ) . S' длялюбых S . S' и x . X. Если S' устойчиво в A, то, ограничивая функцию переходов 8 наS' х X, получают подавтомат A' = (S',X, 8). Совокупность SubA всех подавтоматовавтомата A, упорядоченная отношением A i ^ A2 ^^ Si С S2, где Ai = (Si,X, 8),i = 1, 2, является дистрибутивной решеткой. Это - решетка подавтоматов автомата A.Известно (см. [1]), что для каждого автомата A существует автомат B с двумявходными сигналами, такой, что SubA = SubB, и что не всегда найдется автономный(т. е. с | X| = 1) автомат B с такой же, как у A, решеткой подавтоматов. Минимизациюпо числу состояний дает следующее предложение.Теорема 2. Пусть A = (S, X, 8) и B = (T, Y, Y) -автоматы, такие, чтоSubA = SubB. Тогда |T| ^ |F(A)|. При этом существует скелетный автомат B, та-кой, что SubA = SubB и |T| = |F(A)|.Доказательство. Как показано в [2], SubA = SubB тогда и только тогда, когдаF(A) = F(B). Так как |F(A)| ^ |S|, то |T| ^ |F(B)| = |F(A)|. Определим автоматB = (T,Y,Y) следующим образом. Положим T = F(A). Ветвлением элемента aв конечном упорядоченном множестве называется количество b(a) его нижних со-седей. Пусть в каркасе F(A) наибольшее из ветвлений элементов равно t. ВозьмемY = {y1, y2, , yt}. Построим диаграмму переходов автомата B. Ее вершинами бу-дут элементы каркаса F(A). Все ребра диаграммы каркаса F(A) ориентируем сверхувниз. Пусть для a(s) G F(A) будет b(a(s)) = k. Присвоим дугам, исходящим из a(s),последовательно слева направо метки y1,y2, . Если k < t, то вершине a(s) соот-несем еще t - k петель с метками , yfc+2, , yt. Проделав это для каждой вершины,получим мультиграф, из любой вершины которого исходят t дуг с метками из Y. Этои есть диаграмма переходов автомата B. Очевидно, что этот автомат скелетный и чтоF(B) = F(A). Из последнего равенства следует, что SubA = SubB и |T| = |F(A)|. Доказанная теорема соотносится со следующими известными фактами: для любогоавтомата A существуют сильносвязные (т. е. с универсальным отношением а) автома-ты B и C, такие, что у A и B изоморфны решетки конгруэнций (ConA = ConB), у Aи C изоморфны группы автоморфизмов (AutA = AutC). Теорема 2 показывает, чтодля любого автомата A существует скелетный (т. е. с тождественным отношением а)автомат B с такой же, как у A, решеткой подавтоматов (SubA = SubB).Пусть K - некоторый класс автоматов и A G K. Как можно путем в том или иномсмысле минимальных изменений в структуре автомата A получить из него автомат A'из класса K? В числе допустимых приемов реконструкции автомата можно рассмат-ривать, например, отождествление некоторых вершин (факторизация), введение до-полнительных состояний и/или входных сигналов (расширения), перенаправление дугдиаграммы переходов, удаление дуг (замена их петлями) и т. п.Напомним, что конгруэнцией автомата A = (S, X, 8) называется эквивалентность 9на множестве его состояний, согласованная с функцией переходов в том смысле, что(Vs, s' G S)(x G X)((s,s') G 9 (8(s,x),8(s',x)) G 9). Если 9 G ConA, то фак-тор-автомат автомата A по конгруэнции 9 определяется как A/9 = (S/9,X, 8), где8(9(s), x) = 9(8(s, x)) для любых s S, x X.Одной из задач об оптимальных реконструкциях автоматов является построениедля данного автомата сильносвязного фактор-автомата с наибольшим возможным чис-лом состояний. Частный случай - факторизация на максимальный по числу состоянийциклический автомат - рассматривался в [3] (циклический автомат - это такой авто-мат, в котором все входные сигналы действуют одинаково и все состояния образуютпри этом цикл). В этом контексте покажем, как путем удаления минимального числадуг в диаграмме G(A) получить из данного автомата A скелетный автомат.Из теоремы 1 непосредственно вытекаетСледствие 1. Автомат A тогда и только тогда является скелетным, когда принекоторой нумерации его состояний матрица переходов M(A) будет нижней треуголь-ной матрицей.Доказательство. То, что матрица M(A) является нижней треугольной мат-рицей, равносильно тому, что соответствующая нумерация состояний автомата - пра-вильная. Прямолинейный подход к решению рассматриваемой задачи состоит в том, чтобыдля каждой из m! возможных нумераций состояний автомата A взять в соответству-ющей матрице M(A) множество |J [M(A)]i, С X, выбрать один из вариантов, при ко-i > jтором это множество будет минимальным по мощности, и построить матрицу M'(A),полагая [M'(A)]i, = [M(A)], при i > j и [M'(A)]ii = (J [M(A)],. Автомат A' с матри-j > iцей переходов M'(A) является скелетным, и он получен путем удаления из диаграм-мы G(A) минимально возможного числа дуг.Понятно, что предложенный способ ни в коей мере не является оптимальным дляисполнения. Более эффективный способ дает обращение к известной в теории гра-фов проблеме расконтуривания. Действуя в этом русле, удалим в диаграмме перехо-дов G(A) все метки дуг. Далее к полученному мультиграфу применим модификациюкакой-либо процедуры удаления в графе минимального числа дуг, приводящей к бес-контурному графу (см., например, [4]). Затем в G(A) каждую удаленную дугу заме-ним петлей в начале этой дуги и восстановим все метки дуг. Полученный мультиграфс помеченными дугами является диаграммой переходов скелетного автомата, дающегорешение задачи.

Ключевые слова

subautomata lattice, regular enumeration of states, skeleton automaton, strongly connected automaton, automaton, решетка подавтоматов, правильная нумерация состояний, скелетный автомат, сильносвязный автомат, автомат

Авторы

ФИООрганизацияДополнительноE-mail
Салий Вячеслав НиколаевичСаратовский государственный университет им. Н. Г. Чернышевскогопрофессор, кандидат физико-математических наук, заведующий кафедройSaliiVN@info.sgu.ru
Всего: 1

Ссылки

Gill F. and Flexer R. Periodic decomposition of sequential machines // J. Assoc. Comput. Mach. 1967. V. 15. P. 666-676.
Верзаков Г. Ф., Киншт Н. В., Рабинович В. И., Тимонен А. Г. Введение в техническую диагностику. М.: Энергия, 1968. 224 с.
Салий В. Н. Каркас автомата // Прикладная дискретная математика. 2010. №1(7). С.63-67.
Богомолов А. М., Салий В. Н. Алгебраические основы теории дискретных систем. М.: Наука, 1997. 368 с.
 Скелетные автоматы | ПДМ. 2011. № 2(12).

Скелетные автоматы | ПДМ. 2011. № 2(12).

Полнотекстовая версия