Автор:О.М. Копытова
Источник: Материалы XVI Международной конференции «Проблемы теоретической кибернетики» (20-25 июня 2011 г.), Россия. Нижний Новгород. Изд-во Нижегородского госуниверситета, 2011 – с. 222 – 225.
Копытова О.М. Неисправности автоматов, сохраняющие их поведениеРассматривается задача сохранения поведения автомата при искажениях его структуры (графа переходов). Найдены условия, при которых искаженный автомат эквивалентен исходному по поведению.
Конечные автоматы широко используются для описания поведения различных устройств и систем, от управляющих и вычислительных до организационных. Изменения в их структуре и поведении при повреждающих воздействиях окружающей среды во многих случаях адекватно описываются преобразованиями графа переходов, задаваемыми перебросками его дуг. Если при этом не меняются отметки дуг (пары вход-выходных символов), то такие переброски можно понимать как ”неисправности” функции переходов автомата. Известно [2], что в результате переброски ровно одной дуги в приведенном автомате получается автомат, не изоморфный исходному, т.е. поведение неисправного автомата в этом случае всегда отличается от поведения исправного. Таким образом, всякий приведенный автомат оказывается неустойчивым к переброске ровно одной дуги. Однако в ряде случаев автомат может быть устойчивым (по сохранению поведения) при перебросках более, чем одной дуги. В работе исследуются условия, при которых переброска k дуг в приведенном автомате, где k>1, не изменяет его поведения. Найдены необходимые условия в терминах поведенческих и структурных свойств графа переходов автомата, при которых переброска нескольких дуг в приведенном автомате приводит к автомату, эквивалентному исходному. Показано, что переброска с сохранением поведения допустима только для некоторых дуг, удаление которых из графа переходов автомата приводит к его подграфу, обладающему определенной симметрией.
Пусть A = (A, X, Y, δ, λ) — приведенный автомат Мили, где A, X, Y — алфавиты состояний, входов и выходов соответственно, а δ, λ — функции переходов и выходов. Автомат A будем также рассматривать как множество дуг EA, где дуга — это четверка (s, x, y, t), если δ(s, x) = t, λ(s, x) = y. Пусть e = (s, x′ , y′ , s1) — дуга автомата A. Под переброской дуги e, например, в состояние s2 будем понимать замену этой дуги дугой (s, x′ , y′ , s2). При s1 ≠ s2 переброску назовём нетривиальной. Далее, если не оговорено противное, рассматриваются нетривиальные переброски. Пусть автомат A′ получен из автомата A переброской некоторого множества дуг M ⊆ EA, среди которых хотя бы одна переброска нетривиальная (такие множества перебросок также называем нетривиальными). Задача заключается в том, чтобы определить условия, при которых автомат A` остается изоморфным исходному автомату A.
Cформулированы достаточные условия сохранения поведения автоматом при переброске двух дуг, и показано, что для любого натурального k > 1 существует приведенный автомат, в котором найдется подмножество из k дуг, одновременная переброска которых приводит к изоморфному автомату. В настоящей работе основное внимание направлено на получение необходимых условий, при которых возможна переброска дуг в общем случае.
Переброска двух дуг. Пусть автомат A′ является результатом переброски некоторых двух различных дуг в автомате A, например, в автомате A′ дуга (s, x′ , y′ , s1) заменена дугой (s, x′ , y′ , s2), а дуга (t, x′′, y′′, t1) заменена дугой (t, x′′, y′′, t2). Обозначим через ε отношение эквивалентности на множестве состояний прямой суммы автоматов A и A′ (состояние s в автомате A′ переименовывается в s ′ ). Состояния a и b автомата A называются k-эквивалентными, если для всякого входного слова p длины k выполняется равенство λ(a, p) = λ(b, p).
Полученные необходимые условия сохранения автоматом поведения при перебросках двух дуг совместно с достаточными условиями из позволяют выделять автоматы такой структуры, при которой возможна переброска, сохраняющая поведение автомата. Более того, на этой основе могут быть определены условия допустимой переброски 2k дуг. В этом случае множество M перебрасываемых дуг имеет четную мощность и разбивается на такие пары дуг, для каждой из которых найденные условия выполняются независимо.
Переброска k дуг. Пусть M — множество перебрасываемых дуг в A, |M| = k > 2, а M′ — множество переброшенных дуг в A′ и M = M∪φ-1 (M′). Обозначим через AM и AM′ частичные автоматы, полученные из A в результате удаления всех дуг из множеств M и M′ соответственно. Утверждение 4. Если φ — изоморфизм автомата A на A′ , то φ — автоморфизм автомата AM′. Частичный автомат Ru с выделенным в нем состоянием u называется идентификатором состояния s автомата A, если при любом гомоморфизме φ автомата Ru в автомат A выполняется равенство φ(u) = s].
Частичный автомат Ru назовем структурным идентификатором состояния s, если последнее равенство выполняется при любом изоморфном вложении Ru в A. Множество всех идентификаторов состояния s в автомате A, включая и структурные, обозначим Is(A).
Утверждение 5. Для любого состояния s из A справедливо Is(AM) ⊆ Is(A). Следствие 2. Если φ — изоморфизм автомата A на A′ , φ(s) = t и s ≠ t, то Is(AM) = It(AM) = ∅.
Наличие идентификаторов в автомате AM позволяет определить множество состояний автомата A, которые остаются неподвижными при любых изоморфизмах A в A′ (т.е. при всевозможных перебросках дуг из M, сохраняющих поведение A).
Множество автоморфизмов автомата AM вместе с операцией их суперпозиции является группой. Обозначим ее GM. Теорема 6. Если автомат A′ , полученный из A нетривиальной переброской дуг множества M, изоморфен A, то группа GM нетривиальна. Группа GM определяет некоторое множество неподвижных состояний. В частности, из утверждения 6 и следствия 2 следует, что такими будут все те состояния автомата A, для которых множество идентификаторов в автомате AM не пусто. Одним из предельных случаев, когда неподвижны все состояния и группа GM тривиальна, является следующий. Пусть λ1s — множество вход-выходных слов длины 1, порожденных состоянием s автомата A, которое будем отождествлять с соответствующим ему частичным автоматом. Следствие 3. Если для любого s ∈ A выполняется λ 1s ∈ Is(A), то при любой переброске непустого множества дуг автоматы A и A′ не изоморфны.
Полученные комбинаторно-алгебраические условия сохранения поведения при перебросках двух и более дуг позволяют выделить ряд структур автоматов, для которых это возможно. Например, можно указать графы переходов, содержащие в качестве неподвижного ядра сильно связные подавтоматы, а вне его — некоторое множество состояний и инцидентных им дуг, переброска которых не меняет поведения автомата. Это множество дуг определяет некоторую частичную симметрию исходного автомата, которая описывается определенной выше группой GM.