Устойчивость автоматов к неисправностям их функции переходов

Рассматривается задача сохранения поведения автомата при искажениях его структуры (графа переходов). Найдены условия, при которых: искаженный автомат эквивалентен исходному по поведению....

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2010
1. Verfasser:	Копытова, О.М.
Format:	Artikel
Sprache:	Russian
Veröffentlicht:	Інститут прикладної математики і механіки НАН України 2010
Schriftenreihe:	Труды Института прикладной математики и механики
Online Zugang:	http://dspace.nbuv.gov.ua/handle/123456789/123960
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Устойчивость автоматов к неисправностям их функции переходов / О.М. Копытова // Труды Института прикладной математики и механики НАН Украины. — Донецьк: ІПММ НАН України, 2010. — Т. 21. — С. 127-136. — Бібліогр.: 5 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-123960
record_format	dspace
spelling	irk-123456789-1239602017-09-16T03:03:39Z Устойчивость автоматов к неисправностям их функции переходов Копытова, О.М. Рассматривается задача сохранения поведения автомата при искажениях его структуры (графа переходов). Найдены условия, при которых: искаженный автомат эквивалентен исходному по поведению. Розглянуто задачу збереження поведінки автомата при спотвореннях його структури (графа переходів).Знайдено умови, за яких спотворений автомат за поведінкою є еквівалентним заданому автомату. The problem of automata behaviour saving is examined under the condition of distortions of its structure (transition graph). The terms at which the behavior of the distorted automata is equivalent to the behavior of the initial one are found. 2010 Article Устойчивость автоматов к неисправностям их функции переходов / О.М. Копытова // Труды Института прикладной математики и механики НАН Украины. — Донецьк: ІПММ НАН України, 2010. — Т. 21. — С. 127-136. — Бібліогр.: 5 назв. — рос. 1683-4720 http://dspace.nbuv.gov.ua/handle/123456789/123960 519.71 ru Труды Института прикладной математики и механики Інститут прикладної математики і механіки НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
description	Рассматривается задача сохранения поведения автомата при искажениях его структуры (графа переходов). Найдены условия, при которых: искаженный автомат эквивалентен исходному по поведению.
format	Article
author	Копытова, О.М.
spellingShingle	Копытова, О.М. Устойчивость автоматов к неисправностям их функции переходов Труды Института прикладной математики и механики
author_facet	Копытова, О.М.
author_sort	Копытова, О.М.
title	Устойчивость автоматов к неисправностям их функции переходов
title_short	Устойчивость автоматов к неисправностям их функции переходов
title_full	Устойчивость автоматов к неисправностям их функции переходов
title_fullStr	Устойчивость автоматов к неисправностям их функции переходов
title_full_unstemmed	Устойчивость автоматов к неисправностям их функции переходов
title_sort	устойчивость автоматов к неисправностям их функции переходов
publisher	Інститут прикладної математики і механіки НАН України
publishDate	2010
url	http://dspace.nbuv.gov.ua/handle/123456789/123960
citation_txt	Устойчивость автоматов к неисправностям их функции переходов / О.М. Копытова // Труды Института прикладной математики и механики НАН Украины. — Донецьк: ІПММ НАН України, 2010. — Т. 21. — С. 127-136. — Бібліогр.: 5 назв. — рос.
series	Труды Института прикладной математики и механики
work_keys_str_mv	AT kopytovaom ustojčivostʹavtomatovkneispravnostâmihfunkciiperehodov
first_indexed	2025-07-09T00:36:32Z
last_indexed	2025-07-09T00:36:32Z
_version_	1837127584568049664
fulltext	ISSN 1683-4720 Труды ИПММ НАН Украины. 2010. Том 21 УДК 519.71 c©2010. О.М.Копытова УСТОЙЧИВОСТЬ АВТОМАТОВ К НЕИСПРАВНОСТЯМ ИХ ФУНКЦИИ ПЕРЕХОДОВ Рассматривается задача сохранения поведения автомата при искажениях его структуры (графа переходов). Найдены условия, при которых искаженный автомат эквивалентен исходному по пове- дению. Ключевые слова: автомат, поведение, переброска дуг, изоморфизм, идентификаторы. 1. Введение.Модель конечного автомата широко используется для описания систем и процессов преобразования информации. При этом формально различные модели таких систем могут обладать одним и тем же поведением. Такие различ- ные модели могут возникать, например, в результате некоторых ”неисправностей” систем, которые тем не менее, не искажают правильное функционирование автома- та. Поэтому актуальной является задача анализа и сравнения поведения автоматов, соответствующих ”неисправностям” системы-эталона. В рамках автоматной модели эта задача изучается в теории экспериментов с автоматами, технической диагнос- тике, теории синтеза дискретных систем, где она является ключевой. В частности, эти вопросы становятся всё более актуальными в связи с широким внедрением раз- личных микроэлектронных систем и компонент критического применения и повы- шенными требованиями к достижению необходимого уровня безопасности [1]. В теории абстрактных автоматов контрольные и распознающие эксперименты традиционно строятся для случая класса всех автоматов с n состояниями или его подклассов, где n — число состояний автомата-эталона. Многие такие классы можно описать как результат порождения класса автоматов из заданного автомата с по- мощью операции переброски дуг в его графе переходов. Например, класс локально порожденных автоматов [2], классы автоматов, порождаемых константными неис- правностями в их схемной реализации, и ряд других можно описать указанным образом. Если при этом не меняются отметки дуг (пары вход-выходных символов), то такие переброски можно понимать как ”неисправности” функции переходов ав- томата. Однако в ряде случаев автоматы могут быть устойчивыми (по сохранению по- ведения) к искажениям структуры. В работе исследуется операция переброски дуг в графе переходов автомата Мили (”неисправности” функции переходов) и ее вли- яние на изменение поведения автомата. Известно [3], что в результате переброски ровно одной дуги в приведенном автомате получается автомат, не изоморфный ис- ходному, т.е. поведение ”неисправного” автомата в этом случае всегда отличается от поведения исправного. Таким образом, всякий приведенный автомат оказывает- ся неустойчивым к переброске ровно одной дуги. Для неприведенных атоматов это уже не так. 127 О.М.Копытова Представляет интерес задача изучения устойчивости приведенного автомата (в смысле сохранения поведения) при перебросках более, чем одной дуги. В работе изучается структура таких приведенных автоматов, которые устойчивы к неисправ- ностям их функции переходов. Найдены необходимые условия в терминах поведен- ческих и структурных свойств графа переходов автомата, при которых переброс- ка нескольких дуг в приведенном автомате приводит к автомату, эквивалентному исходному. Показано, что переброска с сохранением поведения допустима только для некоторых дуг, принадлежащих подграфам графа переходов, обладающих опре- деленной симметрией. 2. Формальная постановка задачи. Основные определения теории автоматов можно найти, например, в [4]. Под автоматом будем понимать автомат Мили A = (A,X, Y, δ, λ), где A,X, Y — алфавиты состояний, входов и выходов, соответственно, а δ, λ — функции переходов и выходов. Будем также рассматривать и частичные автоматы, у которых области определения функций переходов и выходов совпадают. Как обычно, будем обозначать автомат символом множества его состояний. Автомат A будем рассматривать также как множество дуг , где дуга — это четверка (s, x, y, t), если δ(s, x) = t, λ(s, x) = y. Функции δ и λ обычным образом распространяются на множество X∗ всех входных слов конечной длины. Два состояния a и b одного и того же автомата A или двух разных автоматов, со- ответственно A и B, называются эквивалентными, если для всякого входного слова p ∈ X∗ выполняется λ(a, p) = λ′(b, p), где λ′ - функция выходов автомата A или B. С каждым состоянием a связывается автоматное отображение λa множества вход- ных слов во множество выходных, определяемое равенством λa(p) = λ(a, p) для всех p ∈ X∗. Двойственным образом определяется множество µa всех вход-выходных слов автомата , оканчивающихся в состоянии a. Ограничение автоматного отображения на множество слов длины k обозначаем λk a. Автомат называется приведенным, если все его состояния попарно неэквивалентны. В дальнейшем будем рассматривать автоматы A и B, у которых входные и вы- ходные алфавиты совпадают, то есть A = (A,X, Y, δ, λ) и B = (B, X, Y, δ′, λ′ ). В этом случае, как обычно, отображение ϕ : A → B будет называться гомоморфиз- мом автомата A в автомат B, если для любых a ∈ A и x ∈ X : 1) ϕ(δ(a, x)) = δ(ϕ(a), x); 2) λ(a, x) = λ′(ϕ(a), x). Пусть e = (a, x, y, b) — дуга автомата A и e′ = (ϕ(a), x, y, ϕ(b)) — дуга автомата B, т.е. гомоморфизм ϕ индуцирует некоторое отображение множества дуг EA во множество дуг EB. Это отображение будем также обозначать ϕ и писать ϕ(e) = e′. Дуга e′ называется образом дуги e по гомоморфизму ϕ, а дуга e называется прообразом e′ по ϕ. Гомоморфизм ϕ называется полным, если каждая дуга из B имеет прообразом некоторую дугу из A. Полный взаимно однозначный гомоморфизм A на B называ- ется изоморфизмом, автоматы A и B называем изоморфными и обозначаем A = B. Взаимно однозначный гомоморфизм может быть не полным, в этом случае будем говорить об изоморфном вложении автомата A в B и писать A ⊆ B. Как обычно, 128 Устойчивость автоматов к неисправностям их функции переходов изоморфизм A на себя называем автоморфизмом. Пусть A = (A,X, Y, δ, λ) - приведенный автомат и e = (s, x′, y′, s1) — его дуга. Под переброской дуги e, например, в состояние s2 будем понимать замену этой дуги на дугу (s, x′, y′, s2). При s1 6= s2 переброску назовём нетривиальной. Далее, если не оговорено противное, рассматриваются нетривиальные переброски. Пусть автомат A′ получен из автомата A переброской некоторого множества дуг M ⊆ EA, среди ко- торых хотя бы одна переброска нетривиальная (такие множества перебросок также называем нетривиальными). Задача заключается в том, чтобы определить условия, при которых автомат A′ остается изоморфным исходному автомату A. 3. Пример сохранения поведения. Легко привести примеры, когда резуль- татом переброски в автомате двух дуг является новый автомат, не изоморфный исходному. Рассмотрим противоположный пример, когда переброска трёх дуг в при- веденном автомате приводит к автомату, изоморфному заданному (см. рис.1). Приведем пример, когда переброска трёх дуг в приведенном автомате также приводит к автомату, изоморфному заданному (см. рис.1). Автомат A′ является ре- зультатом переброски трёх дуг в автомате A: дуга (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 → 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′, т.е. автомат A′ также приведен и эквивалентен автомату A. В [5] были сформулированы достаточные условия сохранения поведения авто- матом при переброске двух дуг, и было показано, что для любого натурального k > 1 существует приведенный автомат, в котором найдется подмножество из k дуг, одновременная переброска которых приводит к изоморфному автомату. В настоящей работе основное внимание уделено получению необходимых усло- вий, при которых возможна переброска дуг в общем случае. Более детально иссле- дуются необходимые условия в случае переброски двух дуг. 4. Необходимые условия сохранения поведения. В дальнейшем нам пона- добятся понятия фрагмента автомата и идентификатора состояния, которые приве- дем, следуя [4]. Идентификатором состояния a автомата A (по поведению) называ- ется такая пара множеств вход-выходных слов Wa = (V1, V2), что V1 ⊆ µa, V2 ⊆ λa, и для любого другого состояния b 6= a хотя бы одно из этих включений не выполня- ется. Фрагментом автомата A называется всякий автомат R (в общем случае частич- ный), для которого существует гомоморфизм в A. Обозначим через Ru фрагмент автомата R с выделенным в этом фрагменте некоторым состоянием u. Используя понятие фрагмента, дадим более общее понятие идентификатора состояния автома- та. Фрагмент Ru называется идентификатором состояния a автомата A, если при любом гомоморфизме ϕ автомата Ru в автомат A выполняется равенство ϕ(u) = a. 129 О.М.Копытова Рис. 1. Пример изоморфизма автоматов при переброске трёх дуг 130 Устойчивость автоматов к неисправностям их функции переходов В [4] показано, что каждому идентификатору состояния Wa по поведению (как па- ре множеств вход-выходных слов) можно поставить в соответствие фрагмент (ча- стичный автомат), также являющийся идентификатором этого состояния. Такой идентификатор-фрагмент также будем называть идентификатором по поведению. Можно привести пример, показывающий, что не каждый идентификатор-фраг- мент является идентификатором по поведению. При исследовании отношения изо- морфизма автоматов важными являются структурные свойства графа переходов автомата. Назовём структурным идентификатором состояния a автомата A такой фраг- мент Ru, изоморфно вкладываемый в A, что при любом изоморфном вложении Ru в A состояние u отображается в a. Множество всех идентификаторов (как струк- турных, так и по поведению), состояния a в автомате A обозначим Ia(A). Пусть M — множество перебрасываемых дуг в A, M ′ — множество переброшен- ных дуг в A′ и M̃ = M ⋃ ϕ−1)(M ′). Обозначим через AM и AM̃ частичные автоматы, полученные из A в результате удаления всех дуг из множеств AM и AM̃ соответ- ственно. Тогда справедливо Утверждение 1. Если ϕ — изоморфизм A на A′, то ϕ — автоморфизм автомата AM̃ . Доказательство. Пусть ϕ — изоморфизм A на A′. Удалим из автомата A мно- жество дуг M̃ = M ⋃ ϕ−1(M ′), а из A′ — множество образов этих дуг ϕ(M̃) = ϕ(M) ⋃ M ′. Получим соответственно автоматы AM̃ и Aϕ(M̃). В силу построения этих автоматов ϕ является изоморфизмом AM̃ на Aϕ(M̃). Предположим, что ϕ не явля- ется автоморфизмом. Тогда в AM̃ существует дуга e = (a, x, y, b), образ которой в автомате Aϕ(M̃) — дуга e′ = (ϕ(a), x, y, ϕ(b)) отсутствует в AM̃ . Но это значит, что дуга e′ есть результат переброски, а такие дуги были выброшены из A′. Полученное противоречие завершает доказательство утверждения 1. ¤ Так как удаление дуг лишь сужает область определения функций δ и λ автомата A, то справедливо Утверждение 2. Для любого состояния a из A справедливо Ia(AM ) ⊆ Ia(A). Примеры показывают, что для произвольного изоморфизма ϕ из A в A′ мно- жества дуг M и ϕ−1(M ′) совпадают. Далее предполагается, что M = ϕ−1(M ′). Тогда M̃ = M ⋃ ϕ−1(M ′) = M и, значит, AM̃ = AM . Пусть ϕ — изоморфизм из утверждения 1 и для некоторых состояний s, t ∈ A, s 6= t выполняется равенство ϕ(s) = t. Тогда справедлива Лемма 1. Для любого фрагмента Ru такого, что существует гомоморфизм ψ фрагмента Ru в атомат AM , при котором ψ(u) = s, найдётся такой гомомор- физм ψ′ фрагмента Ru в AM , для которого ψ′(u) = t. Действительно, так как ψ — гомоморфизм, а ϕ — изоморфизм из утверждения 1, то ψ′ = ψ ◦ ϕ также гомоморфизм Ru в AM , причём ψ′(u) = ϕ(ψ(u)) = t. Из этой леммы следует, что Ru не является идентификатором ни состояния s, ни состояния t. 131 О.М.Копытова Следствие 1. Если ϕ — вышеуказанный изоморфизм, ϕ(s) = t и s 6= t, то Is(AM ) = It(AM ) = Ø. По утверждению 1 ϕ — автоморфизм автомата AM , а автоморфизм сохраняет идентификаторы. Поэтому Is(AM ) = It(AM ), но ни один фрагмент Ru по лемме 1 не является идентификатором s в AM . Следовательно, Is(AM ) = It(AM ) = Ø. Наличие идентификаторов в автомате AM позволяет определять те множества состояний автомата A, которые остаются неподвижными, т.е. переходят сами в себя, при любых изоморфизмах A в A′ (т.е. при всевозможных перебросках дуг из M , сохраняющих поведение A). Множество M ⊆ EA определяет автомат AM и множество его автоморфизмов GM . Множество GM с операцией суперпозиции является группой, т.е. для любых ϕ,ψ ∈ GM выполняется ϕ ◦ ψ ∈ GM и ϕ−1 ∈ GM . Теорема 1. Если автомат A′, полученный из A нетривиальной переброской дуг множества M , изоморфен A, то группа GM нетривиальна. Доказательство. Изоморфизм ϕ автомата A в A′ нетривиален в силу нетриви- альности множества перебросок дуг из M , т.е. для некоторого состояния s ϕ(s) = s′, где s 6= s′. По утверждению 1 ϕ — нетривиальный автоморфизм автомата AM , и, значит, группа GM также нетривиальна, так как содержит нетривиальную подгруп- пу, порождённую ϕ. ¤ Заметим, что в группе GM изоморфизмы автомата A в автоматы A′, получа- емые всевозможными перебросками дуг из множества M , определяют подмножество HM ⊆ GM автоморфизмов. Это множество HM и порождает некоторую нетриви- альную подгруппу группы GM . Укажем некоторые множества неподвижных точек, общие для всех автоморфиз- мов из группы GM , а, значит, и для изоморфизмов автомата A во всевозможные автоматы A′. Первое множество состояний определяется следствием 1. Во-первых, это мно- жество A1 тех состояний s ∈ A, для которых Is(AM ) 6= ∅. Во-вторых, это множество всех состояний, которые достижимы из тех s ∈ A1, для которых Is(AM ) 6= ∅. Это следует из того, что при автоморфизме состояния, достижимые из неподвижных точек, также неподвижны относительно данного автоморфизма. Второе множество составляют те состояния, для которых идентификаторами являются дуги из M . При перебросках дуг для любого состояния s сохраняется множество λ1 s. Поэтому справедливо Следствие 2. Если для любого s ∈ A выполняется λ1 s ∈ Is(A), то при любой переброске непустого множества дуг автоматы A и A′ не изоморфны. 5. Переброска двух дуг. Пусть теперь автомат A′ является результатом пере- броски некоторых двух различных дуг в автомате A. Пусть, например, в автомате A′ дуга (s, x′, y′, s1) заменена дугой (s, x′, y′, s2), а дуга (t, x′′, y′′, t1) заменена дугой (t, x′′, y′′, t2). Обозначим через ε отношение эквивалентности на множестве состояний A. Со- 132 Устойчивость автоматов к неисправностям их функции переходов стояния a и b автомата A называются k-эквивалентными [4], если для всякого вход- ного слова p длины k выполняется равенство λ(a, p) = λ(b, p). Отношение k-экви- валентности обозначим через εk, а класс k-эквивалентности, содержащий некоторое состояние r, — через εk(r). Если k — минимальная длина такого слова p, для кото- рого λ(a, p) 6= λ(b, p), то состояния a и b автомата A называются k-различимыми. Состояния автомата A′ будем помечать штрихом, а обозначения для функций переходов и выходов оставим без изменения. Одноименные состояния вида (r, r′) автоматов A и A′, соответственно, назовем двойственными состояниями. Пусть A и A′ изоморфны, а n — множество состояний автомата A. При доказательстве последующих утверждений будем пользоваться приёмом по- строения Pk-таблиц [3] для автомата B = A ⋃ A′, полученного приписыванием ав- томата A′ к автомату A. Из правил построения Pk-таблиц следует, что с ростом k каждый класс в таблице Pk будет состоять из пар двойственных состояний до тех пор, пока не распадётся хотя бы одна из пар (s, s′) или (t, t′). Отсюда вытекает Лемма 2. Если (s, s′) ∈ εi и (t, t′) ∈ εi для некоторого i > 1, то для любого состояния r 6= s, t выполняется (r, r′) ∈ εi. Лемма 3. Состояния s и t 1-эквивалентны. Доказательство. Предположим противное. Построим Pk-таблицы для автома- та В=A ⋃ A′ и рассмотрим как с ростом k = 1, 2, ... распадаются классы εk(s) и εk(t). Заметим, что в силу изоморфизма автоматов A′ и A, каждый класс в Pk- таблицах автомата B должен содержать чётное число состояний — одинаковое число штрихованных и нештрихованных состояний. Так как значения функций выходов автоматов A и A′ одинаковы, то в таблице P1 каждый класс эквивалентности состоит из пар двойственных состояний. Отсюда (s, s′) ∈ ε1, (t, t′) ∈ ε1, но в силу исходного предположения, (s, t) /∈ ε1. По лемме 2 (r, r′) ∈ ε1 для любого r 6= s, t. Пара (s, s′) по любому x 6= x′ переходит в па- ру двойственных состояний, и только для x′ это не так, поскольку δ(s, x′) = s1, а δ(s′, x′) = s′2. Поэтому пара (s, s′) распадется сразу после того, как распадется пара (s1, s ′ 2). Аналогичные рассуждения справедливы и для пары (t, t′). Так как A приве- ден, то состояния (s1, s2) являются i-различимыми, а состояния (t1, t2) j-различимы для некоторых i и j, где 1 ≤ i ≤ n− 1, 1 ≤ j ≤ n− 1. При этом, возможно, что i = j. Выберем l = min(i, j). Пусть для определённости l = i. Тогда (s, s′) ∈ εi, (t, t′) ∈ εi и по лемме 2 (r, r′) ∈ εi для любого r ∈ A, т.е. в таблице Pi все клас- сы, по-прежнему, состоят из пар двойственных состояний. При этом (s1, s ′ 1) ∈ εi, (s2, s ′ 2) ∈ εi, но (s1, s2) /∈ εi и, значит, (s1, s ′ 2) /∈ εi. Рассмотрим как распадается класс εi(s) на следующем (i + 1)-ом шаге. В таблице Pi этот класс состоит из пары (s, s′) и, возможно, других пар вида (r, r′). Заметим, что каждая такая пара (r, r′) по любому x переходит опять в пару двойственных, а, значит, i-эквивалентных со- стояний, откуда следует, что (r, r′) ∈ εi+1. Поскольку δ(s, x′) = s1, δ(s′, x′) = s′2 и (s1, s ′ 2) /∈ εi, то (s, s′) /∈ εi+1. Из построения Pi+1-таблицы следует, что класс состо- яний εi+1(s) содержит само s и, возможно, пары вида (r, r′). Но тогда этот класс содержит нечётное число состояний, а это значит, что A и A′ не изоморфны. Случай 133 О.М.Копытова l = j рассматривается аналогично. Полученное противоречие доказывает лемму. ¤ Поскольку при n = 2 состояния s и t не являются 1-эквивалентными, то из леммы 3 вытекает Следствие 3. В автомате с двумя состояниями невозможно перебросить две дуги таким образом, чтобы полученный автомат был изоморфен исходному. Лемма 4. (s, s′) /∈ ε, (t, t′) /∈ ε. Доказательство. При доказательстве леммы 3 было показано, что существует такое i, 1 ≤ i ≤ n− 1, что (s, s′) /∈ εi+1. Отсюда (s, s′) /∈ ε. Аналогично, (t, t′) /∈ ε.¤ Лемма 5. Существует минимальное k > 1 такое, что состояния s, s′, t, t′ являются (k − 1)-эквивавлентными, (s, t) /∈ εk, (s, t′) ∈ εk, (s′, t) ∈ εk и для всех состояний r 6= s, t справедливо (r, r′) ∈ εk. Доказательство. Из леммы 4 следует, что существует минимальное k1 такое, что (s, s′) /∈ εk1 или (t, t′) /∈ εk1 , или одновременно (s, s′) /∈ εk1 и (t, t′) /∈ εk1 . Так как (s, s′) ∈ εk1−1 и (t, t′) ∈ εk1−1, то по лемме 2 (r, r′) ∈ εk1−1 для любого r ∈ A. При этом каждая пара (r, r′), за исключением пар (s, s′) и (t, t′), по любому x опять переходит в пару двойственных состояний. Поэтому из построения Pk1 следует, что для всех состояний r 6= s, t, справедливо (r, r′) ∈ εk1 . С другой стороны, в силу приведенности автомата A, существует минимальное k2, при котором (s, t) /∈ εk2 . Покажем, что k1 = k2. Предположим, что k1 6= k2. Рассмотрим два случая: k2 < k1 и k1 < k2. 1. k2 < k1. Тогда (s, s′) ∈ εk2 и (t, t′) ∈ εk2 , но (s, t) /∈ εk2 . По вышесказанно- му, хотя бы одна из пар (s, s′) или (t, t′) k1-различима, и при этом (r, r′) ∈ εk1 для всех r 6= s, t. Пусть для определенности (s, s′) /∈ εk1 . Тогда в таблице Pk1 класс εk1(s) состоит из состояния s и, возможно, пар вида (r, r′), т.е. содержит нечётное число состояний. Но тогда автоматы A и A′ не изоморфны. Случай (t, t′) /∈ εk1 рассматривается аналогично. 2. k1 < k2. Пусть для определённости (s, s′) /∈ εk1 (случай (t, t′) /∈ εk1 аналогичен данному). Возможны следующие два случая: a) (t, t′) ∈ εk1 . Так как (s, s′) ∈ εk1−1 и (t, t′) ∈ εk1−1, то по лемме 2 все классы (k1 − 1)-эквивалентности состоят из пар двойственных состояний. Поскольку все пары (r, r′), отличные от (s, s′) и (t, t′), по всем x переходят опять в пары двойствен- ных состояний, получаем, что (r, r′) ∈ εk1 . Кроме того, (t, t′) ∈ εk1 . Таким образом, в таблице Pk1 все состояния, кроме s и s′, входят в классы k1-эквивалентности попарно с двойственными им. Но тогда класс εk1(s), равно как и класс εk1(s ′), содержат нечётное число состояний, откуда следует, что A и A′ не изоморфны; б) (t, t′) /∈ εk1 . Поскольку k1 < k2, то (s, t) ∈ εk1 . Рассуждая аналогично п.а), приходим к выводу, что в таблице Pk1 все состояния, отличные от s и t, входят в классы k1-эквивалентности двойственными парами. При этом пары (s′, t′) и (s, t) принадлежат разным классам k1-эквивалентности. Отсюда следует, что класс εk1(s) содержит нештрихованных состояний больше, чем штрихованных. Следовательно, A и A′ не изоморфны. Полученное противоречие доказывает, что k1 = k2. Другими словами, пары со- 134 Устойчивость автоматов к неисправностям их функции переходов стояний (s, t), (s, s′) и (t, t′) являются k-различимыми, где k = k1 = k2. Нетрудно ви- деть, что единственный способ разбиения класса k1-эквивалентности, содержащего s, s′, t, t′, не нарушающий изоморфизма A и A′, следующий: (s, t′) ∈ εk и (s′, t) ∈ εk. Лемма доказана.¤ Теорема 2. Справедливы следующие утверждения: 1)на перебрасываемых дугах отметки входных символов совпадают: x′ = x′′, причём x′ есть начальная буква кратчайшего слова, различающего s и t; 2)на перебрасываемых дугах отметки выходных символов совпадают: y′ = y′′; 3)состояния s и t, из которых перебрасываются дуги, различны. Доказательство. Докажем утверждение 1). По лемме 5 существует минималь- ное k такое, что класс (k − 1)-эквивалентности, содержащий s, s′, t, t′, разбивает- ся в таблице Pk на два класса, содержащих, соответственно, пары (s, t′) и (t, s′). Пусть p = x1x2...xk — слово минимальной длины k, различающее s и t. Обозна- чим u = δ(s, x1) и v = δ(t, x1). Так как x1 — начальная буква кратчайшего слова, различающего s и t, то (u, v) /∈ εk−1. Покажем, что x1 = x′ = x′′. Предположим противное. Возможны два случая: 1) x1 6= x′, x′′ и 2) x1 = x′ 6= x′′ либо x1 = x′′ 6= x′. Рассмотрим каждый из них. Пусть x1 6= x′, x′′ . В силу леммы 5 для всех i < k в таблице Pi любой класс состоит из пар вида (r, r′). Поэтому (u, u′) ∈ εk−1, (v, v′) ∈ εk−1. Учитывая, что (u, v) /∈ εk−1, получаем, что (u, v′) /∈ εk−1. Но тогда (s, t′) /∈ εk, что противоречит лемме 5. Пусть теперь x1 = x′ 6= x′′ или x1 = x′′ 6= x′. Предположим для определённости, что x1 = x′ 6= x′′ . Тогда u = δ(s, x1) = δ(s, x′) = s1. По лемме 5 (s, t) ∈ εk−1, но (s, t) /∈ εk. По вышесказанному (u, v) /∈ εk−1 , т.е. (s1, v) /∈ εk−1. При этом (s1, v) ∈ εk−2, так как в противном случае состояния s и t были бы (k − 1)-различимы. В силу леммы 5 состояния s1, s ′ 1, v, v′ (k − 2)-эквивалентны, причем (s1, s ′ 1) ∈ εk−1 и (v, v′) ∈ εk−1. Следовательно, (s1, v ′) /∈ εk−1. Но тогда (s, t′) /∈ εk, что противоречит лемме 5. Случай x1 = x′′ 6= x′ рассматривается аналогично. Итак, в обоих случаях пришли к противоречию. Следовательно, x1 = x′ = x′′. Докажем утверждение 2). По лемме 3 λ(s, x) = λ(t, x) для любого x ∈ X. По доказанному утверждению 1) x′ = x′′. Отсюда y′ = λ(s, x′) = λ(t, x′) = y′′. Докажем утверждение 3). Из утверждений 1) и 2) следует, что обе перебрасы- ваемые дуги должны иметь одну и ту же вход-выходную отметку. Поскольку из одного и того же состояния нельзя перебросить две различные дуги с одинаковыми вход-выходными отметками, то утверждение 3) справедливо. Теорема доказана.¤ 6. Заключение. Полученные необходимые условия сохранения автоматом по- ведения при перебросках дуг совместно с достаточными условиями из [5] дают опре- делённый инструментарий, позволяющий исследовать поведение такого рода авто- матов. Условия допустимой переброски для двух дуг могут быть расширены на пере- броску 2k дуг в случае, когда множество M может быть разбито на двухэлементные классы дуг, для каждого из которых независимо выполняются найденные условия. 135 О.М.Копытова Найденные структуры (рис.1) показывают, что переброски осуществляются для дуг, исходящих из состояний, лежащих вне сильно связных подавтоматов исходного автомата. При этом структура графа переходов обладает своего рода частичной симметрией, которая проявляется при удалении перебрасываемых дуг и описывается группой автоморфизмов, указанной в теореме 1. 1. Малиновский М.Л. Синтез безопасных автоматов с функциональной деградацией // Управля- ющие системы и машины. – 2010. – №1. – С.84-91. 2. Копытова О.М., Козловский В.А. Контрольные эксперименты в локально порожденных клас- сах // Материалы IX Международного семинара ”Дискретная математика и ее приложения”. – М: МГУ. – 2007. – C.322-324. 3. Грунский И. С., Копытова О. М. О структуре контрольного эксперимента для определенно- диагностируемого автомата // Теория управляющих систем. – К: Наукова думка. – 1987. – С.40-54. 4. Грунский И.С., Козловский В.А. Синтез и идентификация автоматов. – К: Наукова думка. – 2004. – 245с. 5. Копытова О.М. О структуре автоматов, сохраняющих поведение при перебросках дуг // Тру- ды VIII Международной конференции ”Дискретные модели в теории управляющих систем”. – М: Макс-Пресс. – 2009. – С.155-159. O.M. Kopytova Stability of automata to their transition function faults. The problem of automata behaviour saving is examined under the condition of distortions of its structure (transition graph). The terms at which the behavior of the distorted automata is equivalent to the behavior of the initial one are found. Keywords: automata, behavior, arc transfer, isomorphism, identifiers. О.М.Копитова Стiйкiсть автоматiв до несправностей їх функцiї переходiв. Розглянуто задачу збереження поведiнки автомата при спотвореннях його структури (графа пе- реходiв).Знайдено умови, за яких спотворений автомат за поведiнкою є еквiвалентним заданому автомату. Ключовi слова: автомат, поведiнка, перекид дуг, iзоморфiзм, iдентифiкатори. Донецкий национальный технический университет omkop@list.ru Получено 30.11.10 136

Устойчивость автоматов к неисправностям их функции переходов

Institution

Ähnliche Einträge