Неисправности автоматов, сохраняющие их поведение
Автор:О. М. Копытова
Источник: Переброска дуг Проблемы теоретической кибернетики 1 — Донецьк, ДонНТУ — 2011, с. 1-3.
Автор:О. М. Копытова
Источник: Переброска дуг Проблемы теоретической кибернетики 1 — Донецьк, ДонНТУ — 2011, с. 1-3.
Конечные автоматы широко используются для описания поведения различных устройств и систем, от управляющих и вычислительных до организационных. Изменения в их структуре и поведении при повреждающих воздействиях окружающей среды во многих случаях адекватно описываются преобразованиями графа переходов, задаваемыми перебросками его дуг [1]. Если при этом не меняются отметки дуг (пары вход-выходных символов), то такие переброски можно понимать как «неисправности» функции переходов автомата. Известно [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.В [2] сформулированы достаточные условия сохранения поведения автоматом при переброске двух дуг, и показано, что для любого натурального 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).
Лемма 1. Состояния s и t 1–эквивалентны.
Следствие 1. В автомате с двумя состояниями невозможно перебросить две дуги таким образом, чтобы полученный автомат был изоморфен исходному.
Лемма 2. (s, s′)∉ε, (t, t′)∉ε.
Теорема 3. Справедливы следующие утверждения:
1)на перебрасываемых дугах вход–выходные отметки совпадают: x′ = x′′, причём x′ есть начальная буква кратчайшего слова, различающего s и t;
2)состояния s и t, из которых перебрасываются дуги, различны.
Полученные необходимые условия сохранения автоматом поведения при перебросках двух дуг совместно с достаточными условиями из [3] позволяют выделять автоматы такой структуры, при которой возможна переброска, сохраняющая поведение автомата. Более того, на этой основе могут быть определены условия допустимой переброски 2k дуг. В этом случае множество M перебрасываемых дуг имеет четную мощность и разбивается на такие пары дуг, для каждой из которых найденные условия выполняются независимо.
Переброска k дуг. Пусть M′ множество перебрасываемых дуг в A, |M| = k ≥ 2, а M′ – множество переброшенных дуг в A′ и ˜М∪Мφ-1(М′). Обозначим через Aм и А˜м частичные автоматы, полученные из A в результате удаления всех дуг из множеств M и ˜М соответственно.
Утверждение 4. Если φ изоморфизм автомата A на A′, то φ – автоморфизм автомата А˜м.
Частичный автомат Ru с выделенным в нем состоянием u называется идентификатором состояния s автомата A, если при любом гомоморфизме φ автомата Ru в автомат A выполняется равенство φ(u) = s[1]. Частичный автомат 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 не пусто.
Одним из предельных случаев, когда неподвижны все состояния и группа Gм тривиальна, является следующий. Пусть λ1s множество вход – выходных слов длины 1, порожденных состоянием s автомата A, которое будем отождествлять с соответствующим ему частичным автоматом.
Следствие 3. Если для любого s ∈ A выполняется 1 λ1s ∈ IS(A), то при любой переброске непустого множества дуг автоматы A и A′ не изоморфны.
Полученные комбинаторно–алгебраические условия сохранения поведения при перебросках двух и более дуг позволяют выделить ряд структур автоматов, для которых это возможно. Например, можно указать графы переходов, содержащие в качестве неподвижного ядра сильно связные подавтоматы, а вне его – некоторое множество состояний и инцидентных им дуг, переброска которых не меняет поведения автомата. Это множество дуг определяет некоторую частичную симметрию исходного автомата, которая описывается определенной выше группой GM.