УДК 519.71

Математика/5. Математическое моделирование

к.ф.-м.н. Копытова О.М.

Донецкий национальный технический университет, Украина

Структура автоматов, устойчивых к переброскам дуг

Введение

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

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

Однако в ряде случаев автомат может оказаться устойчивыми к искажениям его структуры, сохранив своё. поведение. В настоящей работе продолжается исследование операции переброски дуг в графе переходов автомата Мили и ее влияния на изменение поведения автомата. Известно [3], что в результате переброски ровно одной дуги в приведенном автомате или при изменении её выходной отметки получается автомат, не изоморфный исходному. В [4] сформулированы достаточные условия сохранения поведения автоматом при переброске двух дуг, и показано, что для любого натурального k > 1 существует приведенный автомат, в котором найдется подмножество из k дуг, одновременная  переброска  которых  приводит  к изоморфному  автомату. В [5] найдены необходимые условия сохранения поведения автоматом при переброске двух дуг.

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

Формальная постановка задачи

Основные определения теории автоматов можно найти, например, в [6].

Под автоматом будем понимать автомат Мили A = (A, X, Y, d, l ), где A, X, Y - алфавиты состояний, входов и выходов соответственно, а d, l − функции переходов и выходов. Будем также рассматривать и частичные автоматы, у которых области определения функций переходов и выходов совпадают. Как обычно, будем обозначать автомат символом множества его состояний. Автомат A будем рассматривать также как множество дуг ЕА, где дуга − это четверка (s,x,y,t), если d (s,x) = t, l (s,x) = y. Функции  d  и  l  обычным образом распространяются на множество  X*  всех входных слов конечной длины.

Два состояния a и b одного и того же автомата A или двух разных автоматов, соответственно A и B, называются эквивалентными, если для всякого входного слова рÎX* выполняется l ( а, р ) = l' ( b, р ), где  l' − функция выходов автомата A или B. С каждым состоянием а связывается автоматное отображение lа  множества входных слов во множество выходных, определяемое равенством  lа ( р ) = l ( а, р ) для всех р Î X*. Двойственным образом определяется множество μа всех вход-выходных слов автомата А, оканчивающихся в состоянии а. Ограничение автоматного отображения на множество слов длины k  обозначаем  lAk. Автомат называется приведенным, если все его состояния попарно неэквивалентны.

В дальнейшем  будем  рассматривать  автоматы  A и  В,  у  которых входные  и  выходные  алфавиты  совпадают,  то  есть   A = ( A, X, Y, d, l )   и   B = ( B, X, Y, d', l' ).  В этом случае, как обычно, отображение φ : A → B будет называться гомоморфизмом автомата A в автомат B, если для любых  aÎ A  и  xÎ X  выполняются оотношения:

1) φ ( d ( а, х ) ) = d  ( φ (а), х );

2) l ( а, х ) = l' ( φ (а), х ).

Пусть е = ( a, x, y, b ) − дуга автомата А  и  е' =( φ (a), x, y, φ (b) ) − дуга автомата  В, т.е. гомоморфизм φ индуцирует некоторое отображение множества дуг ЕА  во множество дуг ЕВ. Это отображение будем также обозначать  φ  и писать  φ(е) = е'. Дуга  е' называется образом дуги  е  по гомоморфизму φ,  а дуга е называется прообразом  е'  по  φ.

Гомоморфизм φ называется полным, если каждая дуга из В имеет прообразом некоторую дугу из А. Полный взаимно однозначный гомо­морфизм А на В называется изоморфизмом, автоматы А  и  В  называем изоморфными и обозначаем А = В. Взаимно однозначный гомо­морфизм может быть не полным, в этом случае будем говорить об изоморфном вложении автомата А  в  В  и писать  А Í В. Как обычно, изоморфизм А на себя называем автоморфизмом.

Пусть A = ( A, X, Y, d, l ) - приведенный автомат и  е=( s, x', y', s1 ) − его дуга.  Под переброской дуги е, например, в состояние s2 будем понимать замену этой дуги на дугу ( s, x', y', s2 ). При  s1≠s2  переброску назовём нетривиальной. Далее, если не оговорено противное, рассматриваются нетривиальные переброски. Пусть автомат  А'  получен из автомата  А  переброской некоторого множества  дуг М Í ЕА, среди которых хотя бы одна переброска нетривиальная (такие множества перебросок также называем нетривиальными). Задача заключается в том, чтобы определить условия, при которых автомат  А'  остается изоморфным исходному автомату  A.

Пример сохранения поведения

Легко привести примеры, когда результатом переброски в автомате двух дуг и более является новый автомат, не изоморфный исходному. В [5] приведен противоположный пример, когда переброска двух дуг в приведенном автомате приводит к автомату, изоморфному заданному. Приведем пример, когда переброска трёх дуг в приведен­ном автомате также приводит к автомату, изоморфному заданному  (см. рис.1). Автомат А' является результатом переброски трёх дуг в автомате А: дуга (s, 0, 0, 11) перебрасывается в состояние 12, т.е. заменяется дугой (s, 0, 0, 12), дуга (t, 0, 0, 12) перебрасывается в состояние 13, т.е. заменяется дугой (t, 0, 0, 13), а дуга (u, 0, 0, 13) перебрасывается в состояние 11, т.е. заменяется дугой (u, 0, 0, 11). Легко видеть, что отображение φ: A → А', такое, что: φ(1) = 1;  φ(2) = 3;  φ(3) = 4;   φ(4) = 2;   φ(5) = 6;   φ(6) = 7;   φ(7) = 5;   φ(8) = 9;  φ(9) = 10, φ(10) = 8, φ(s) = t;   φ(t) = u;   φ(u) = s; φ(11) = 11;  φ(12) = 12;  φ(13) = 13,  реализует изоморфизм автомата A на автомат А',  т.е. автомат  А' также приведен и эквивалентен автомату  A.

В настоящей работе основное внимание уделено получению необходимых условий, при которых возможна переброска дуг с сохранением поведения  в общем случае.

 

Необходимые условия сохранения поведения

В дальнейшем нам понадобятся понятия фрагмента автомата и идентификатора состояния, которые приведем, следуя [6]. 

Идентификатором состояния а  автомата А (по поведению) называется такая  пара множеств  вход-выходных слов Wа = ( V1,  V2 ), что V1  Í  μа, V2  Í la,  и для любого другого состояния   b ≠ a   хотя бы одно из этих включений не выполняется.

Фрагментом автомата  А  называется всякий автомат R (в общем случае частичный), для которого существует гомоморфизм  в  А. Обозначим через Ru фрагмент автомата с выделенным в этом фрагменте некоторым состоянием  u. Используя понятие фрагмента, дадим более общее понятие идентификатора состояния автомата.

Фрагмент Ru называется идентификатором состояния а автомата А, если при любом гомоморфизме  φ  автомата  Ru   в  А  выполняется равенство φ ( u ) = a. В [6] показано, что каждому идентификатору состояния Wа  по поведению (как паре множеств вход-выходных слов) можно поставить в соответствие фрагмент (частичный автомат), также являющийся  идентификатором этого состояния. Такой идентификатор-фрагмент также будем называть идентификатором по поведению.

Можно привести пример, показывающий, что не каждый идентификатор-фрагмент является идентификатором по поведению. При исследовании отношения изоморфизма автоматов важными являются  структурные свойства графа переходов автомата.

Назовём структурным идентификатором состояния а автомата А такой фрагмент Ru, изоморфно вкладываемый  в   А,  что  при любом изоморфном вложении  Ru   в   А   состояние  u  отображается в а. Множество всех идентификаторов, как структурных так и по поведению, состояния а  в автомате А обозначим Iа (А).

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

Утверждение 1. Если  М Í ЕА   и  φ − изоморфизм  А  на  А',  то φ  − автоморфизм автомата   АМ .

Это сразу же следует из того, что удаление дуг лишь сужает область определения функций  d  и  l  автомата А, не нарушая свойства  φ  быть гомоморфизмом. Отсюда же следует и

Утверждение 2.  Для  любого  состояния  а  из  А  справедливо  включение Iа ( AM ) Í  Iа ( A ).

Пусть φ  − изоморфизм из утверждения 1 и для некоторых различных состояний   s, t Î A    выполняется  равенство  φ ( s ) = t.  Тогда справедлива

Лемма 1. Для любого  фрагмента  Ru   такого, что существует гомоморфизм ψ фрагмента Ru    в   АМ,   при котором   ψ ( u ) = s,  найдётся гомоморфизм  ψ'     Ru    в   АМ, для которого ψ' ( u ) = t.

Действительно, так как ψ − гомоморфизм, а φ − изоморфизм из утверждения 1,  то  ψ' = ψ◦φ  также гомоморфизм Ru    в   АМ,   причём  ψ' ( u ) = φ ( ψ ( u ) ) = t.  

Из этой леммы следует, что Ru  не является идентификатором ни состояния s  ни состояния t.

Следствие 1.  Если  φ  − вышеуказанный изоморфизм,   φ ( s ) = t    и    s ≠ t,  то  Is  ( AM ) =  It  ( AM ) = Æ.

По утверждению 1    φ  − автоморфизм автомата АМ, а автоморфизм сохраняет  идентификаторы. Поэтому Is  ( AM ) = It  ( AM ),  но  ни  один  фрагмент   Ru     по  лемме  1  не  является  идентификатором   s   в   AM.    Следовательно,    Is ( AM )  =  It ( AM ) = Æ.

Наличие идентификаторов в автомате AM позволяет определять те множества состояний автомата А, которые остаются неподвижными, т.е. переходят сами в себя, при любых изоморфизмах  А в А'  (т.е. при всевозможных перебросках дуг из М, сохраняющих поведение А). 

Множество М Í ЕА  определяет автомат АМ  и множество его автоморфизмов GM.   Множество   GM   с операцией суперпозиции является группой,  т.е. для любых   φ,  ψÎ GM        φ◦ψ Î GM     и      φ-1  Î GM . 

Теорема 1.  Если автомат А',  полученный из А нетривиальной переброской дуг множества  М,  изоморфен  А,  то группа  GM  нетривиальна.

Доказательство. Изоморфизм φ автомата  А  в  А'  нетривиален в силу нетривиальности множества перебросок дуг из М, т.е. для некоторого состояния s  φ(s) = s', где s ≠ s'.  По утверждению 1   φ  − нетривиальный автоморфизм автомата  АМ,  и,  значит,  GM также нетривиальна, так как содержит нетривиальную подгруппу, порождённую  φ.

Заметим, что в GM изоморфизмы автомата А в автоматы А', получаемые всевозможными перебросками дуг из множества М, определяют подмножество   HM  Í  GM   автоморфизмов. Это множество  HM  и  порождает некоторую нетривиальную подгруппу группы GM.

Укажем некоторые множества неподвижных точек, общие для всех автоморфизмов из группы GM, а, значит, и для изоморфизмов А  во всевозможные автоматы  А'.

Первое множество состояний определяется следствием 1. Во-первых, это множество A1 тех состояний sÎ A, для которых  Is ( AM ) ≠ Æ. Во-вторых, это множество  всех  состояний,  которые  достижимы  из  тех  sÎ A,  для которых  Is ( AM ) ≠ Æ.  Это следует из того, что при автоморфизме состояния, достижимые из неподвижных точек, также неподвижны относительно данного автоморфизма.

Второе множество составляют те состояния, для которых идентификаторами являются дуги из  М.

При перебросках дуг для любого состояния s сохраняется множество l1s. Поэтому справедливо

Следствие 2. Если для любого  sÎ A    l1sÎ Is ( A ), то при любой переброске  непустого  множества  дуг  автоматы   А   и  А'   не изоморфны.

 

Заключение

Полученные необходимые условия сохранения автоматом поведения при перебросках дуг совместно с достаточными условиями из [4] дают определённый инструментарий, позволяющий исследовать поведение такого рода автоматов.

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

Список литературы

1.       Малиновский М.Л. Синтез безопасных автоматов с функциональной деградацией. Управляющие системы и машины, 2010, №1, с. 84 − 91.

2.       Копытова О.М., Козловский В.А. Контрольные эксперименты в локально порожденных классах. Материалы IX Международного семинара "Дискретная математика и ее приложения". Москва: МГУ, 2007, с. 322 − 324.

3.       Грунский И. С., Копытова О. М. О структуре контрольного эксперимента для определенно-диагностируемого автомата. Теория управляющих систем,  Киев: Наукова думка, 1987, с. 40 − 54.

4.       Копытова О.М. О структуре автоматов, сохраняющих поведение при перебросках дуг. Труды VIII Международной конференции "Дискретные модели в теории управляющих систем". Москва: Макс-Пресс, 2009, с. 155 − 159.

5.       Копытова О.М. О возможности сохранения поведения автомата при перебросках дуг // Материалы VI Международной научно-практической конференции «Новости научной мысли - 2010» (27.10 – 05.11.2010), Чехия. Прага. Издательский дом "Образование и наука", 2010 – с. 41– 46.

6.       Грунский И.С., Козловский В.А. Синтез и идентификация автоматов. Киев: Наукова думка, 2004.