В статье исследуются различающие эксперименты с недетерминированными неинициальными автоматами. Показывается, как построить безусловный различающий эксперимент для множества начальных состояний, если множество начальных состояний является разделимым, т.е. существует входная последовательность, на которую множества выходных реакций в любых двух различных начальных состояниях не пересекаются. Кроме того, предлагается алгоритм построения условного эксперимента для множества начальных состояний, и устанавливаются свойства множества начальных состояний для существования такого эксперимента.
Distinguishing experiments with nondeterministic non-initialized finite state machines.pdf В последнее время появляется все больше исследований, посвященных неде-терминированным автоматам. В частности, недетерминированные автоматы на-ходят применение при разработке выигрышных стратегий в логических играх икриптографии, активно используются при синтезе и анализе дискретных системуправления, в частности при оптимизации дискретных систем и синтезе прове-ряющих и диагностических тестов для них. Однако большинство отношений со-вместимости и различимости между недетерминированными автоматами введенодля инициальных автоматов.В ряде приложений требуется различить несколько состояний автомата (не-сколько автоматов) простым безусловным или условным экспериментом. Извест-ны необходимые и достаточные условия существования таких экспериментов длядвух состояний заданного автомата (двух заданных инициальных автоматов).В данной работе мы устанавливаем необходимые и достаточные условия сущест-вования таких экспериментов для подмножества состояний автомата любой мощ-ности, на основе которых можно установить необходимые и достаточные условияразличимости конечного числа (неинициальных) полностью определенных авто-матов простым безусловным и условным экспериментами.1. Недетерминированные автоматыКонечным автоматом, или просто автоматом, далее называется пятеркаS = (S, I, O, hS, S), где S - конечное непустое множество состояний с выделеннымнепустым подмножеством S начальных состояний, I и O - конечные входной ивыходной алфавиты и hS S I O S - отношение или множество переходов.Если множество S совпадает с множеством всех состояний автомата, то для обо-значения такого автомата мы будем использовать четверку S = (S, I, O, hS). Чет-верка (s, i, o, s) hS описывает переход в автомате S из состояния s в состоя-ние s под действием входного символа i с выходным символом o. Если множест-во S содержит только одно состояние, то автомат называется инициальным авто-матом, в противном случае автомат называется неинициальным. Автомат называ-ется полностью определенным, если для каждой пары (s, i) S I существуетхотя бы одна пара (o, s) O S, такая, что (s, i, o, s) hS; в противном слу-чае автомат называется частично определенным или частичным. В данной работемы рассматриваем только полностью определенные автоматы. Автомат называет-ся наблюдаемым, если для каждой тройки (s, i, o) S I O существует толь-ко одно состояние s S, такое, что (s, i, o, s) hS; в противном случае авто-мат называется ненаблюдаемым. В данной работе мы рассматриваем только на-блюдаемые автоматы. Автомат называется детерминированным, если для каждойпары (s, i) S I существует не более чем одна пара (o, s) O S, такая, что(s, i, o, s) hS; в противном случае автомат называется недетерминирован-ным. В общем случае в недетерминированном автомате в текущем состоянии дляданного входного символа может существовать более одного перехода. Для не-инициального автомата S = (S, I, O, hS, S') далее через S/sj обозначается иници-альный автомат (S, I, O, hS, sj). Пусть S = (S, I, O, hS, s0) и P = (P, I, O, hP, p0) - ини-циальные автоматы. Пересечением S P автоматов S и P [1] называется наи-больший связный подавтомат автомата Q = (S P, I, O, hQ, s0p0), в котором (sp, i, o,sp) hQ (s, i, o, s) hS & (p, i, o, p) hP.Отношение переходов естественным образом распространяется на входные ивыходные последовательности. Пусть s S и i1 ... ik I* - непустая последова-тельность входных символов. Четверка (s, i1 ... ik, o1 ... ok, s) hS, где o1...ok O*,- последовательность из выходных символов, если существует последователь-ность состояний s1, ..., sk+1 S такая, что s1 = s, sk+1 = s и для каждого j = 1, ..., kсправедливо (sj, ij, oj, sj+1) hS. Наличие четверки (s, i1 ... ik, o1 ... ok, s) в множест-ве hS означает, что автоматв каждом состоянии на всех входных последовательностях. Функция переходовописывает множество состояний, в которые автомат может перейти из состояния sпод действием входной последовательности . Функция выходов описывает мно-жество выходных последовательностей, которые могут появиться на выходе ав-томата в этом случае. Таким образом, функции переходов и выходов отображаютдекартово произведение S I в множества подмножеств множеств S и O* соответ-ственно, и для любых s S, b S и I* справедливо next_state(s, ) s, если и только если O* [(s, , , s) hS], next_state(b, ) = s b next_state(s, ).Далее мы распространяем хорошо известные бинарные отношения на множе-стве состояний автомата [1] на отношения между подмножествами состояний.Состояние s полностью определенного автомата S = (S, I, O, hS, S) и состояниеp полностью определенного автомата P = (P, I, O, hP, P) называются эквивалент-ными, если для любой входной последовательности имеет местоout(s, ) = out(p, ). Подмножества состояний m автомата S и b автомата P назы-ваются эквивалентными, если для любой входной последовательности имеетместо out(m, ) = out(b, ). Автоматы S и P эквивалентны, если для каждого со-стояния множества S в множестве P существует эквивалентное состояние, и об-ратно. Автоматы S и P слабо эквивалентны, если множества S и P эквивалентны.Известно [2], что для любого недетерминированного автомата S существует экви-валентный наблюдаемый автомат. Наблюдаемая форма строится на основе детер-минизации соответствующего полуавтомата. Кроме того, известно [3], что дляполностью определенного автомата S = (S, I, O, hS, S) можно построить слабо эк-вивалентный инициальный наблюдаемый автомат, т.е. такой автомат Q, что пара/ есть входо-выходная последовательность автомата Q в начальном состоянии,если и только если / есть входо-выходная последовательность автомата S в од-ном из состояний множества S.Подмножество состояний m автомата S называется разделимым, если сущест-вует входная последовательность , которая является разделяющей последова-тельностью для любых двух различных состояний s1 и s2 множества m, т.е. спра-ведливо out(s1, ) out(s2, ) = ∅. Отметим, что в общем случае последователь-ность должна разделять любые два непересекающихся подмножества состояниймножества m, однако в данной статье мы рассматриваем только наблюдаемые ав-томаты, поэтому введенное определение корректно. Если состояния разделимогомножества m разделимы одним входным символом, то множество m также назы-вать 1-условно-различимым множеством.Пусть определены все максимальные (k - 1)-условно-различимые подмноже-ства, k > 0. Будем говорить, что m есть k-условно-различимое множество состоя-ний, k > 1, если m есть (k - 1)-условно-различимое множество или существуетвходной символ i I, такой, что для любого o O множество i/o-преемников со-стояний из m пусто, содержит одно состояние или является (k - 1)-условно-различимым множеством, причем в последних двух случаях любые два различныесостояния из m не могут обладать одним и тем же i/o-преемником. Множество mназывается условно-различимым, если m есть k-условно-различимое множестводля некоторого k.2. Различающие эксперименты с недетерминированными автоматамиКак обычно, под различающим экспериментом с (недетерминированным) пол-ностью определенным автоматом понимается эксперимент, позволяющий опреде-лить состояние автомата до эксперимента. В предыдущем разделе были введеныдва понятия различимости для подмножеств состояний автомата S. В работах [4,5] установлены необходимые и достаточные условия для различимости пары на-чальных состояний безусловным и условным экспериментами, и в этой работе мырасширяем эти результаты на произвольное множество начальных состояний не-детерминированного автомата.2 . 1 Б е з у с л о в н ы е р а з л и ч а ю щ и е э к с п е р и м е н т ыДля построения входной последовательности, разделяющей состояния разде-лимого множества состояний, можно воспользоваться следующим алгоритмом:Алгоритм 1. Построение разделяющей последовательности для множестваначальных состоянийВход: Полностью определенный наблюдаемый автомат S = (S, I, O, hS, S').Выход: Входная последовательность, разделяющая состояния множества S',если S' - разделимое подмножество, или ответ «S' не является разделимым».Шаг 1. Строим усеченноемножеством P, которое не содержит одноэлементных множеств, помечен после-довательностью , то множество P содержит все пары состояний автомата S, та-кие, что для каждой пары из P существует входо-выходная последовательность/, по которой эта пара достижима из некоторой пары начальных состояний. По-этому, если существует входной символ i, который разделяет каждую пару со-стояний в множестве P, последовательность разделяет каждую пару различныхначальных состояний. Таким образом, если алгоритм 1 доставляет разделяющуюпоследовательность, то S' является разделимым множеством. Предположим, что для разделимого множества S' с кратчайшей разделяю-щей последовательностью i все пути в алгоритме 1 заканчиваются с использова-нием правил 2 и 3. Соответственно последовательность не помечает ни одинпуть из корня дерева (иначе бы некоторый путь в дереве заканчивался с примене-нием правила 1). Рассмотрим самый длинный префикс последовательности , = i, который помечает путь из корня дерева в некоторую терминальную вер-шину. Этот путь не может заканчиваться с применением правила 3, так как в этомслучае любое продолжение не является разделяющей последовательностью.Пусть путь, помеченный последовательностью , заканчивается в вершине на k-муровне, k > 0, с множеством P пар состояний с применением правила 2. Последнееозначает, что существует другой путь в дереве, помеченный последовательностью, в некоторую вершину на j-м уровне j, j < k, помеченную множеством R P.Поскольку последовательность i разделяет все пары множества P, то i разделяети все пары подмножества R, т.е. последовательность i, которая короче последо-вательности i, является разделяющей для множества S', что противоречит тому,что i была выбрана как кратчайшая последовательность с таким свойством.Пример. Рассмотрим автомат S = ({1, 2, 3, 4}, {a, b}, {0, 1}, hS, {1, 2, 3}), пред-ставленный на рис. 1, на котором также приведено усеченное по алгоритму 1 де-рево преемников для этого автомата. Поскольку все пути в этом дереве заканчи-ваются с применением правил 2 и 3, множество {1, 2, 3} не является разделимыми, следовательно, начальные состояния автомата S неразличимы безусловнымэкспериментом.1 23 4a/1a/0b/1a/1 b/1b/0 a/1a/0a/0b/01,2,1,3,2,33,2,2,4,2,2 1,33,2,2,4 1,32,2 2,2a ba ba bРис. 1. Автомат, начальные состояния которого не различимыбезусловным экспериментом, и его усеченное дерево преемниковЗаметим, что для наблюдаемого автомата S = (S, I, O, h, S') с n состояниями иm начальными состояниями длина кратчайшей разделяющей последовательностине превосходит величины 2 2Cn2 −Cm2 . Причиной является тот факт, что длина разде-ляющей последовательности ограничивается длиной пути в усеченном деревепреемников, которая, в свою очередь, согласно правилу 2, не превосходит числамножеств, не содержащих множество всех пар различных начальных состояний.Число таких подмножеств пар состояний равно 2 2 2Cn−Cm. Как известно [4], для ав-томата с n состояниями, два из которых являются начальными, для любого n ≥ 2можно построить автомат, в котором кратчайшая входная последовательность,разделяющая начальные состояния, имеет длину212 4n −, и, таким образом, безус-ловные различающие эксперименты с неинициальными автоматами имеют экспо-ненциальную сложность.Если множество начальных состояний неинициального автомата не являетсяразделимым, то в ряде случаев состояния этого множества можно различить по-средством условного эксперимента.2 . 2 У с л о в н ы е р а з л и ч а ю щ и е э к с п е р и м е н т ыс н е д е т е р м и н и р о в а н н ы м и а в т о м а т а м иВ этом разделе мы показываем, что состояния множества m различимы услов-ным экспериментом, если m является условно-различимым множеством, т.е. еслисуществует такое целое неотрицательное число k, что m есть k-условно-различимое множество состояний. Поскольку число состояний n автомата S ко-нечно, то число k не превышает 2n - 1, т.е. проверка множества начальных состоя-ний автомата на различимость может быть осуществлена конструктивно, за ко-нечное число шагов.Частичный наблюдаемый автомат R = (R, I, O, TR, r0) со специальными состоя-ниями 1, …, k называется различающим для автомата S = (S, I, O, h, S'), есливыполняются следующие условия:1. Граф переходов автомата R ациклический.2. Состояния 1, …, k тупиковые.3. Если r ∉ {1, …, k}, то в состоянии r определен переход в точности по од-ному входному символу i.4. Для любого j = 1, …k все тупиковые состояния пересечения S/sj R являют-ся парами вида (s, j), s S, и для любого нетупикового состояния sr пересеченияS/sj R и входного символа i, по которому определен переход в состоянии r ав-томата R, пересечение S/sj R в состоянии sr содержит каждую входо-выходнуюпару i/o автомата S в состояния s.По определению различающего автомата справедливо следующее утверждение.Предложение 1. Начальные состояния автомата различимы условным экспе-риментом, если и только если для автомата S = (S, I, O, h, S') существует разли-чающий автомат.Действительно, свойства 1 - 3 определяют условный эксперимент с автоматомS, а свойство 4 является необходимым и достаточным для того, чтобы такой экс-перимент различал начальные состояния автомата S. В работе [4] показано, как построить r-различающий автомат для двух наблю-даемых инициальных автоматов, которые являются r-различимыми. Ниже мыпредлагаем алгоритм построения такого различающего автомата для случая, когдаавтомат имеет k начальных состояний, k ≥ 2.Алгоритм 2. Построение различающего автомата для произвольного множе-ства начальных состояний.Вход: Полностью определенный наблюдаемый автомат S = (S, I, O, h, S'), |S'| = k.Выход: Автомат R, различающий состояния множества S', если S' - условно-различимое множество, или сообщение о том, что S' не является условно-различимым множеством.Строим автомат R = (R, I, O, hR, r0): состояниями автомата R являются не-пустые подмножества состояний автомата S и состояния 1, …, k; начальное со-стояние r0 автомата R есть подмножество S'R: = {S', 1, …, k}; hR : = ∅; k: = 1;Шаг 1. Если в автомате не существует ни одного разделимого множествамощности 2,то выдать сообщение «S' не является условно-различимым под-множеством» и ENDИначе найти все k-условно-различимые подмножества.Шаг 2. Если S' является k-условно-различимым множеством, тодля каждого j- условно-различимого подмножества P (j > 1)определить входной символ i I, такой, что для любого o Oмножество i/o-преемников состояний из P пусто, содержит односостояние или является (j - 1)-условно-различимым множест-вом P, причем любые два различные состояния из P не обла-дают одним и тем же i/o-преемником;добавить в R каждый переход (P, i, o, P), |P| > 1;Для каждого начального состояния sj S'построить пересечение S/sj R;Для каждого состояния (s, P) пересечения S/sj R, дости-жимого из начального состояния по некоторой входо-выходной последовательностиЕсли (s, P) - тупиковое состояние пересечения,определить входной символ is I, такой, что для лю-бого o O в автомате R множество i/o-преемниковсостояний из P пусто или содержит одно состояние;Иначе, обозначить через is входной символ, по которомуопределен переход из состояния (s, P)Для каждой входо-выходной пары is/o в состоянии s,по которой нет перехода в состоянии (s, P) пересече-ния S/sj R добавить в R переход (P, is, o, j);Удалить из R состояния, недостижимые из начального состоянияENDЕсли все k-условно-различимые подмножества являются (k - 1)-условно-различимыми, то выдать сообщение «S' не является условно-различимым подмножеством» и ENDИначе, увеличить k на 1, и перейти на Шаг 1. Теорема 2. Алгоритм 2 доставляет автомат R, различающий состояния множе-ства S', если и только если S' - условно-различимое множество.Действительно, если S' есть условно-различимое множество, т.е. S' есть k-условно-различимое множество для некоторого k, алгоритм 2 строит автомат R,который переходит в тупиковое состояние j, если и только если начальное со-стояние автомата S есть sj (шаг 2). С другой стороны, если S' не является условно-различимым множеством, то алгоритм 2 формирует соответствующее сообщение,и автомат R не строится. По правилам построения различающего автомата можно показать, что подобноавтомату с двумя начальными состояниями [5], если множество S' не является k-условно-различимым для некоторого k, то для автомата S нельзя построить разли-чающий автомат, т.е. не существует условного эксперимента, который различаетначальные состояния автомата S (предложение 1).Как известно [5], если автомат имеет n состояний, два из которых являютсяначальными, то для любого n можно построить условный эксперимент, в которомвходная последовательность, различающая два начальных состояния (если суще-ствует
Евтушенко Н.В., Петренко А.Ф., Ветрова М.В. Недетерминированные автоматы: анализ и синтез. Ч. 1. Отношения и операции: учеб. пособие. Томск: ТГУ, 2006. 142 с.
Starke P. Abstract automata. American Elsevier, 1972. 419 с.
Трахтенброт Б.А. Конечные автоматы: анализ и синтез. М.: Наука, 1970. 400 с.
Spitsyna N., El-Fakih K., Yevtushenko N. Studying the separability relation between finite state machines software testing // Verification and Reliability. 2007. V. 17(4). P. 227−241.
Громов М.Л. Разработка методов синтеза условных тестов для автоматных моделей с недетерминированным поведением: дис. ... канд. физ.-мат. наук. Томск: ТГУ, 2009.
Вы можете добавить статью