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

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

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

Контроль автомата при локальных перебросках дуг

Введение

Контрольные эксперименты с автоматами [1] обычно изучаются для достаточно обширных классов автоматов. Большинство таких классов можно рассматривать как результат последовательности специальных преобразований над дугами автомата-эталона типа переброски дуг – замены конца дуги в графе переходов автомата другим состоянием, или замены в отметке дуги одного выходного символа другим. В [2] рассматривались так называемые m-плотные классы, охватывающие широкий круг классов автоматов, возникающих при произвольных перебросках дуг или изменении их отметок, возможно, даже с увеличением числа состояний. Для таких классов необходимым условием, при котором эксперимент становится контрольным, является обход по всем дугам графа переходов автомата-эталона. Однако это условие обычно не является достаточным, что является одной из причин высокой сложности задачи распознавания свойства "быть контрольным экспериментом" относительно этих классов (в ряде случаев это NP-полная проблема [3]). Исключением является класс локально порожденных из эталона автоматов [4], для которого, при наложении ограничений на поведение эталона, контрольный эксперимент "почти" совпадает с обходом по всем дугам автомата-эталона. Это сразу же определяет и полиномиальность указанной задачи распознавания в этом случае. Поэтому интерес представляет поиск классов, достаточно богатых по разнообразию составляющих их автоматов, для которых "почти" обходы определяют контрольные эксперименты. "Почти" обходы характеризуются, в первую очередь, наименьшей сложностью среди контрольных экспериментов относительно m-плотных классов, то есть, в них прообраз каждой дуги исходного автомата встречается минимально возможное число раз по сравнению с контрольными экспериментами относительно других классов. Стоит заметить, что, например, в родственной задаче тестирования программных систем на основе графовых моделей чаще всего ограничиваются построением обхода по дугам соответствующих графов, хотя обход есть лишь необходимое условие для полноты проверки. В работе рассматриваются эксперименты для автоматов  относительно так называемых локально определенных классов [5], обладающих таким же свойством минимальной сложности, как и "почти" обходы. Целью настоящей работы является развернутое описание результатов, анонсированных в [5].

1. Контрольные эксперименты с автоматами

Под  автоматом  понимаем  автомат  Мили   ,  где  S, X, Y – алфавиты состояний, входов и выходов соответственно, а  – функции переходов и выходов. Функции автомата обычным образом распространяются на множество X* . Будем говорить, что вход-выходное слово w = (p,q) порождается состоянием s автомата A, если . С каждым состоянием s ассоциируется множество  всех вход-выходных слов, порождаемых этим состоянием. Автомат удобно задавать в виде графа переходов, вершинами которого являются состояния из S, а дугами – четверки (s, x, y, t) = u, где .  Пара (x, y) называется отметкой дуги u, s – началом дуги,  а  t – ее концом.  В дальнейшем будем отождествлять автомат  A  со множеством всех дуг его графа и писать , если u есть дуга автомата A. Множество всех дуг автомата будем обозначать также как UA. Если не оговорено противное, считаем, что автомат имеет хотя бы одну дугу. Состояние t называется достижимым из s, если  для некоторого .

Множество  W  вход-выходных слов назовем экспериментом автомата A, если  для некоторого состояния s автомата A.   W  будем называть также экспериментом, порождаемым автоматом в состоянии s, или просто порождаемым s.   Эксперимент W называется простым, если он состоит из одного вход-выходного слова, и кратным в противном случае. Эксперимент определяет множество путей в графе переходов автомата из состояния s, и если оно содержит (покрывает) все множество дуг графа переходов, то эксперимент называется обходом автомата из состояния s. Эксперимент называется полным, если он является обходом  из любого состояния, которое порождает этот эксперимент.

Эксперимент W называется контрольным относительно заданного класса F автоматов и автомата-эталона A, если из того, что W является экспериментом автомата B, следует, что B содержит подавтомат, эквивалентный A.  Класс F может задаваться различными способами, обычно неявно – указанием свойств входящих в него автоматов. Наиболее часто рассматривается класс Fn – класс всех автоматов с n состояниями в алфавите   или его подклассы. Обычно класс F выбирается так, что вместо эквивалентности рассматривается изоморфизм.

2. Локально определенные классы

Пусть  – некоторый автомат. Каждой паре  автомата А поставим в соответствие некоторое множество состояний O(s,x), полагая при этом, что состояния s и  принадлежат O(s,x), а само O(s,x) содержит, по крайней мере, два состояния.  Обозначим совокупность таких множеств, соответствующих всевозможным парам  , через O (A) и назовем ее локализацией A. Локально определенным (посредством локализации O (A) ) классом назовем класс LO(A) автоматов, образующихся из автомата А заменой в нем некоторой дуги (s,x,y,t) дугой (s,x,y,r), где r  принадлежит O(s,x), или множеством таких замен. В силу определения класса LO(A) можно считать, что все автоматы из этого класса имеют одно и то же множество состояний S.

Пусть W – эксперимент автомата  A.  Дугу u=(s, x, y, t)  автомата  А назовем подтвержденной в эксперименте W, если она покрывается этим экспериментом из любого состояния, порождающего W, и найдется хотя бы одна такая дуга (t, x1, y1, r), что  (x, y)(x1, y1) есть подслово некоторого слова эксперимента W.

Локально диагностируемым (по локализации O (A) ) назовем автомат, в котором для любой пары (s,x) из   и для любых различных r, t из O(s,x)  верно неравенство  для  любого  х'  из  X.  Заметим, что в общем случае, как показывают примеры, локально диагностируемый автомат может быть неприведенным. Далее, если не оговорено противное, рассматриваем локально диагностируемые автоматы.

В дальнейшем нам понадобится понятие начального идентификатора состояния [3]. Начальным идентификатором состояния s называется такое порождаемое им множество   вход-выходных слов, которое не порождается никаким другим состоянием автомата. Высота идентификатора есть наибольшая из длин входящих в него слов. Если идентификатор состоит из одного слова, он называется простым. Множество всех состояний автомата A, имеющих начальные идентификаторы высоты 1, обозначим как , множество всех начальных идентификаторов автомата высоты 1  –  как  .

Далее полагаем, что автомат-эталон A  имеет непустое множество , и все состояния автомата-эталона достижимы из состояний этого множества.

Пусть в эксперименте W  автомата   A  для некоторого  состояния  s  из   найдется такое множество слов {(px1p1,qy1q1), (px2p2,qy2q2), ... } с одним и тем же начальным отрезком (p,q), возможно, пустым, что множество вход-выходных слов длины 1  {(x1,y1), (x2,y2), ... } содержит хотя бы один начальный идентификатор высоты 1 состояния s. Множество всех таких начальных отрезков (p,q)  обозначим .

Теорема. Если эксперимент W автомата А полный, в нем подтверждена каждая дуга автомата А,  и   содержит пустое слово,  то W является контрольным экспериментом локально диагностируемого автомата А относительно локально определенного класса LO(A).

Доказательство. При перебросках дуг сохраняются все идентификаторы высоты 1. Пусть эксперимент W порождается  состоянием s  автомата А. Если W  порождается другим автоматом В из  LO(A), то этот эксперимент порождается именно состоянием s автомата В в силу того, что   содержит пустое слово. Пусть (p,q) – некоторое слово из эксперимента W, где  р = х1 х2 ... хk ,  q = y1 y2  ...  yk .  Так как В является локально диагностируемым, то , . Пусть для начального отрезка рi = х1 х2 ... хi  слова р справедливы равенства , . Тогда из вышесказанного следует, что ,  . Это значит, что последовательность дуг автомата А,  определяемая любым словом (р, q)  из  эксперимента W, совпадает с аналогичной последовательностью дуг автомата В.  Эксперимент W полный, т.е. покрывает все дуги автомата А. В нем каждая дуга подтверждена, т.е. множество всех дуг, определяемых всеми словами эксперимента W,  совпадет со всем множеством дуг автомата А.  Но тогда и множество дуг автомата В,   определяемых всеми словами эксперимента W, будет таким же. Это означает,  что  W  –  контрольный эксперимент автомата  А  относительно  класса   LO(A). Теорема доказана.

Если эксперимент простой, то условия теоремы требуют, чтобы эксперимент порождался состоянием s, обладающим простым начальным идентификатором длины 1. Отсюда и из оценок длины обходов автоматных графов вытекает

Следствие. Длина минимального простого контрольного эксперимента для (A, LO(A))  не  меньше     и  не  больше , где n, m – число состояний и входов автомата  A  соответственно,  причем нижняя оценка достижима.

Доказательство. Длина минимального обхода графа переходов автоматов, как известно, не меньше mn и не больше . Дополнительное слово длины 1 необходимо для подтверждения последней пройденной в эксперименте дуги, и, возможно, слово длины, не больше (n-1) потребуется для того, чтобы достичь указанное состояние s из заданного начального состояния.  Поэтому нижняя оценка достижима.

Заключение

Так как локально определенные классы являются m-плотными, то из полученных оценок длины простых экспериментов  следует, что в общем случае для m-плотных классов, получаемых произвольными перебросками дуг, нижние оценки длины контрольных экспериментов не могут быть улучшены по порядку.

Литература

1.     Bhattacharyya A. Checking experiments on sequential machines.- New York: J. Wiley and Sons, 1989. – 155 с.

2.     Козловский В.А., Копытова О.М. Представления автоматов относительно m-плотных классов.// Матер. VIII Межд. семинара "Дискретная математика и ее приложения" (Москва, 2 – 6 февраля 2004 г.) . – М.:Изд.-во МГУ. – С. 277 – 280.

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

4.     Козловский В.А. Локальные неисправности автомата и их обнаружение.// Математические вопросы кибернетики (под ред. С.В.Яблонского). –  М.:Наука, 1991, вып. 3. –  С.167 – 186.

5.  Козловский В.А., Копытова О.М. Условия контроля автоматов «почти» обходами // Новые информационные технологии в исследовании сложных структур: Тезисы докладов Седьмой Российской конференции с международным участием. – Томск: Изд-во НТЛ, 2008. – с.51.