ПРОГРАММИРОВАНИЕ, 2014, No 6, с. 48-53
ТЕСТИРОВАНИЕ, ВЕРИФИКАЦИЯ И ВАЛИДАЦИЯ ПРОГРАММ
УДК 681.32
О СЛОЖНОСТИ ПРОВЕРКИ СУЩЕСТВОВАНИЯ УСТАНОВОЧНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ ДЛЯ НЕДЕТЕРМИНИРОВАННЫХ АВТОМАТОВ *
© 2014 г. Н.Г. Кушик1, В.В. Кулямин2, Н.В. Евтушенко1
1 Томский государственный университет 634050 Томск, ул. Ленина, 36
2
109004 Москва, ул. А. Солженицына, 25 E-mail: ngkushik@gmail.com, kuliamin@ispras.ru, yevtushenko@sibmail.com
Поступила в редакцию 21.06.2014
В статье рассматривается сложность задачи проверки существования установочной последовательности для наблюдаемого полностью определенного недетерминированного автомата. Известно, что минимальная длина такой последовательности для автоматов определенного класса является экспоненциальной относительно числа состояний автомата. Вместе с тем в данной статье показывается, что задача проверки существования такой последовательности принадлежит классу РБРАСЕ.
1. ВВЕДЕНИЕ
Эксперименты с недетерминированными автоматами в последнее время активно используются в различных приложениях, в том числе в задачах синтеза проверяющих тестов для программного и/или аппаратного обеспечения для установки тестируемой системы в известное состояние. Достаточно часто рассматриваются безусловные эксперименты [1], когда на проверяемую систему подается некоторая входная последовательность, сформированная до начала эксперимента, которая позволяет сделать некоторые выводы о свойствах системы, например, о состоянии системы до или после эксперимента.
В частности, для установки системы в известное состояние используются синхронизирующие [см., например, 2-4] и установочные последовательности [5-6]. Ряд оценок сложности получен для задач проверки существования и синтеза соответствующей синхронизирующей последовательности для конечных, в том числе частичных и недетерминированных,
* Работа частично поддержана грантом РФФИ № 14-08-31640 мол_а и проектом 2.739.2014 (Госзадание МиноОбрНауки РФ).
полуавтоматов (задача синхронизируемости полуавтомата) [2-4], где под полуавтоматом понимается система с конечным числом состояний, переходы между которыми помечены действиями из некоторого алфавита. Для конечных автоматов, т.е. систем с конечным числом состояний, переходы между которыми помечены парами "входной_символ / выходной_символ" рассматривают также установочные эксперименты. После наблюдения выходной реакции тестируемой системой на установочную входную последовательность можно определить, в каком состоянии находится система после экперимен-та. Соответственно, возникает задача синтеза установочной входной последовательности для заданного конечного автомата. Задачи построения установочной последовательности для полностью определенных детерминированных автоматов рассматривались, в частности, в работах [5, 6], и показано, что всякий детерминированный приведенный сильно связный автомат обладает установочной последовательностью, длина которой оценивается полиномом второй степени от числа состояний автомата. Более того, показано, что задача проверки существования установочной и синхронизирующей
О СЛОЖНОСТИ ПРОВЕРКИ СУЩЕСТВОВАНИЯ ... ПОСЛЕДОВАТЕЛЬНОСТЕЙ
49
последовательностей для детерминированного полностью определенного автомата является РБРАСЕ-полной [7, 8]. Установочные эксперименты с недетерминированными автоматами рассматривались в работах [9-11]. Показано, что в отличие от случая детерминированных автоматов, установочная последовательность не всегда существует для приведенного сильно связного недетерминированного автомата. Предложен метод синтеза установочной последовательности для полностью определенных наблюдаемых недетерминированных автоматов, и получены оценки длины такой установочной последовательности. В частности, показана достижимость экспоненциальной оценки длины установочной последовательности для наблюдаемого полностью определенного недетерминированного автомата относительно числа его состояний.
Несмотря на экспоненциальную зависимость длины установочной последовательности от числа состояний недетерминированного автомата, открытым остается вопрос оценки сложности проверки существования такой последовательности, т.е. вопрос о сложности проверки установоч-ности недетерминированного автомата. Соответственно, в данной статье рассматривается следующая задача распознавания: проверить, существует ли установочная последовательность для заданного полностью определенного наблюдаемого недетерминированного автомата, и показывается, что эта задача принадлежит классу РБРАСЕ. Полученный результат вместе с известными результатами для детерминированных автоматов [7, 8] автоматически подтверждает полноту поставленной задачи распознавания.
Структура работы следующая. Во втором разделе приводятся основные определения и обозначения из области теории автоматов, кратко рассматриваются алгоритм синтеза установочной последовательности для недетерминированного автомата и известные результаты по оценке длины такой последовательности. Третий раздел посвящен доказательству принадлежности задачи установки для полностью определенных наблюдаемых недетерминированных автоматов классу РБРАСЕ. В заключении кратко анализируются полученные результаты, и оцениваются перспективы дальнейших научных исследований.
2. ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ И ОБОЗНАЧЕНИЯ. СИНТЕЗ УСТАНОВОЧНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ ДЛЯ НЕДЕТЕРМИНИРОВАННЫХ АВТОМАТОВ
Под конечным автоматом (или далее просто автоматом,) [12, 13] понимается пятерка S = (S, I, O, hs, S'), где S - конечное непустое множество состояний с выделенным непустым множеством начальных состояний S', I и O - конечные непустые входной и выходной алфавиты соответственно, такие, что I П O = 0 и hs С S х I х O х S - отношение или множество переходов. Состояние s' называется i/o-преемником состояния s е S для i е I, o е O, если четверка (s, i, o, s') содержится в hs. Соответственно, можно определить множество всех i/o-преемников состояния s £ S как множество состояний {s' е S|(s, i, o, s') е hs}. Если в автомате S для любой пары (s, i) е S х I существу-
(o, s') е O х S такая, что (s, i, o, s') е hs, то автомат называется полностью определенным, в противном слу-
S
называется детерминированным, если для любой пары (s, i) е S х I существует не бо-
(o, s') е O х S (s, i, o, s') е hs. В противном случае автомат называется недетерминированным. Если в неде-
S
(s, i, o) е S х I х O
состояния s' е S такого, что (s, i, o, s') е hs, то автомат называется наблюдаемым, в противном случае автомат называется ненаблюдаемым, [14]. В наблюдаемом автомате для каждого состояния s и каждой пары i е I, o е O суще-
i/o
статье мы рассматриваем класс автоматов, которые являются недетерминированными, полностью определенными и наблюдаемыми.
Параллельно с отношением переходов в автомате часто используют две функции: функцию переходов (функцию пеж£_states) и функцию выходов (функцию outs), определенных следующим образом ne«t_states(s, i) э s', если 3 o е O, (s, i, o, s') е hs; outs(s, i) э o, если 3 s' е S, (s, i, o, s') е hs, однако в отличие от детерминированных автоматов, в общем случае поведение недетерминированного
50
КУШИК и др.
автомата нельзя описать посредством только этих функций [13]. Отношение переходов обычным образом распространяется на последовательности (слова) в алфавитах I и O, и таким образом, множество next_states (s,a) содержит все состояния, в которые автомат
s
входной последовательности а, а множество outs(s, а) содержит все возможные выходные последовательности автомата для этого случая. Пусть S = (S,I,O,hs,S'), |S'| = m > 2, -полностью определенный наблюдаемый недетерминированный автомат. Входная последовательность а € I* называется установочной
S,
бого подмножества {sil,... ,sij} С S' имеет место следующее свойство: У в € out(sil ,а) П out(si2,а)П- ■ -Пout(sij, a)[next_state(sil, а/в) = next _state(si2 ,а/в) = ■ ■ ■ = next_state(sij а/в)}.
S
два начальных состояния si и s2, приведенное выше свойство записывается в виде У в € out(s1^) П out(s2, а)[next _state(s1, а/в) = next state(s2, а/в)}.
В [11] показывается, что для наблюдаемого
S
а
а
ры начальных состояний из множества S'.
Последовательность а € I* называется разде-S,
различных состояний s1 и s2 множества S' справедливо out(s1, а) П out(s2, а) = 0 [11]. По определению, всякая разделяющая последовательность для наблюдаемого автомата S является установочной для этого автомата. Тем не менее обратное в общем случае не верно; входная последовательность может быть установочной для заданного автомата даже в случае, когда нарушается разделимость каждой пары начальных состояний. Необходимые и достаточные условия существования установочной последовательности на основе усеченного дерева преемников автомата устанавливаются в [11]. Мы далее кратко приводим предложенный метод синтеза установочной последовательности для последующей оценки сложности задачи проверки существования такой последовательности.
Синтез установочных последовательно-
стей для недетерминированных автоматов
осуществляется на основе усеченного дерева преемников [5-6]; в работах [9, 11] понятие усеченного дерева преемников обобщается для недетерминированных автоматов. Для наблюдаемо-
S
дерева помечается множеством, которое состоит из всех пар различных начальных состояний, т.е. пар вида sp, sq, sp, sq € S', sp = sq, вершины дерева помечаются множествами пар состояний множества S. Пусть уже построены j уровней дерева, j > 0. Из нетерминальной вершины j-ro уровня, помеченной множеством P пар состояний, есть ребро, помеченное входным символом i, в вершину, которая помечена множеством пар Q: тара sp, sq € Q, если sp и sq являют-i/o
P
вола o € O. Если i/o-преемники некоторой па-PQ принадлежит соответствующий синглетон. Если i
P,
P,
i,
жеством. Вершина Current на k-м уровне, к > 0,
P
ется листом дерева, если для нее выполняется одно из следующих условий.
P
Правило 2: На j-м уровне, j < к, существует вершина, помеченная множеством R, такая, что множество P содержит все пары из R, которые не являются синглетонами.
P
тонов.
В [9] устанавливаются
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.