3.1.1 Основные определения и понятия

Для правильного и подробного описания этого подхода необходимо ввести основные определения и понятия.

В качестве абстрактной модели дискретного устройства (ДУ) с памятью будем использовать автомат Мили, определяемый пятеркой

А = (X, Y, Z, , ), (3.1)

где X = { X₁, X₂,…., X_m } - множество букв входного алфавита;

Z = { Z_1, Z_2,…, Z_n } - множество состояний автомата;

Y = { Y₁, Y₂, …Y_r } - множество букв выходного алфавита;

(Z_i, X_k) = Z_j; Z_i, Z_jZ; X_kX; i, j = ; k = - множество функций переходов автомата;

(Z_i, X_k) = y; yY, = - множество функций выхода автомата.

В дальнейшем изложении будут использоваться следующие обозначения и понятия:

X_j = X₁ X₂ … X_{k -} входное слово или входная последовательность из К букв;

l (X_j) = k - длина последовательности;

Y_j = Y₁ Y₂ … Y_{k -} выходное слово или выходная последовательность длины l (Y_j) = k.

Любое конечное множество состояний автомата будем называть -множеством. Элементы, образующие -множество, не обязательно различны. -множество, содержащее единственный элемент, называется простым, а содержащее несколько одинаковых элементов - кратным. -множество, однородно, если все элементы одинаковы.

(Z_i, X_j) - выходная последовательность автомата, первоначально находящегося в состоянии Z_i и проявляющаяся в результате приложения входной последовательности X_j.

Многие задачи теории автоматов (кодирование состояний, декомпозиция автоматов, минимизация числа состояний и другие) успешно решаются путем анализа разбиений состояний автомата. Термин "разбиение" имеет в математике ряд значений [10]. Вообще, под разбиением принято понимать всякое расчленение целого на части.

Определение 3.1 Пусть В подмножество Z. Разбиением _i множества Z называют совокупность таких подмножеств B_i, что их по парные пересечения - пустые множества, а объединение всех подмножеств B_i равно Z.

Подмножество B_i называют блоком разбиения _i множества Z.

Пример 3.1 Пусть Z={A, B, C, D, E, F}. Тогда

= {},

={ },

где - разбиения множества Z.

Говорят, что для пары разбиений _{, ,} определенных на множестве Z, разбиение больше или равно разбиению _{( ,} ), если каждый блок разбиения содержится в блоке _. Например, разбиение и из примера 3.1 можно упорядочить в виде _.

Разбиение, в котором каждый блок включает один элемент множества Z, является (0) - разбиением, а разбиение, содержащее в одном блоке все элементы Z, является (1) - разбиением.

Определение 3.2 Если ₁ и ₂ - разбиения множества Z, то произведением разбиений (_{1 2}) является разбиение, полученное в результате пересечения каждого блока из ₁ с каждым блоком из ₂.

Например, произведение пары разбиений множества из примера 3.1 равно

= {}.

Определение 3.3 Если ₁ и ₂ - разбиения множества Z, то суммой разбиений (₁ + ₂) является разбиение, полученное в результате объединения тех блоков ₁ и _2, которые имеют, по меньшей мере, один общий элемент.

Например, сумма пары разбиений множества Z из примера 3.1 равна

₁ + ₂= { }.

Если известна автоматная модель ДУ с элементами памяти, то задача построения проверяющего эксперимента сводится к нахождению входных и выходных последовательностей, которые позволяют однозначно идентифицировать автоматную диаграмму ДУ [11]. Большинство известных методов решения этой задачи основано на работе Хенни [12]. Предложенный им подход дает хорошие результаты для автоматов, которые имеют отличительные последовательности. Поэтому этот класс автоматов многие исследователи называют легко тестируемым [13]. Известна процедура нахождения отличительной последовательности автомата по его автоматной диаграмме предусматривающая построение дерева преемников автомата и применение определенных правил усечения вершин этого дерева. Процедура завершается, когда, либо найдена отличительная последовательность для заданного автомата, либо в результате построения отличительного дерева установлено, что автомат не имеет отличительной последовательности.

Известно, что необходимым условием существования для данного автомата отличительной последовательности является свойство минимальности автомата. Однако это условие не является достаточным, так как существуют минимальные автоматы, не имеющие отличительных последовательностей.

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

Определение 3.4 Входная последовательность X₀ называется отличительной для автомата А= (X, Y, Z, , ), если выходная последовательность автомата, как реакция на X₀, различна для любого начального состояния, то есть

(Z_i, X₀₎ (Z_i, X₀), для Z_i, Z_j Z, Z_i Z_j. (3.2)

С целью определения достаточных условий существования для заданного автомата отличительной последовательности предлагается рассмотреть процедуру построения отличительного дерева и некоторые его свойства.

Отличительное дерево приемников, в котором вершина ранга r является висячей если:

а) ей поставлена в соответствие группа - множеств, содержащая, по меньшей мере, одно кратное - множество;

б) ей поставлена в соответствие группа - множеств, в которой все не простые - множества совпадают с - множествами вершины ранга меньше r;

в) среди вершин ранга r имеется хотя бы одна вершина, отмеченная простым - множеством.

Для иллюстрации воспользуемся примером автомата А-1, заданного таблицей 3.1 переходов-выходов. Отличительное дерево, построенное в соответствии с вышеприведенными правилами усечения дерева преемников, приведено на рисунке 3.1 Каждая вершина отмечена - множествами, полученными в соответствии с правилами построения дерева преемников. Над каждым - множеством в отличительном дереве указаны состояния предшественники, принадлежащие начальному -множеству и порождающие соответствующие им группы - множеств.

Таблица 3.1 - Автомат А-1

Рисунок 3.1 - Отличительное дерево автомата А-1

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

({ } X₁) = { 2, 1, 4 }, { 5, 2 }. (3.3)

Блоки разбиения ₁ ={} множества состояний A-1 определяют отношение эквивалентности состояний в том смысле, что состояния, принадлежащие каждому блоку разбиения ₁ X₁ - неразличимы, а сами блоки разбиения ₁ являются X₁ - различимыми. Вершине отличительного дерева (рисунок 3.1), отмеченной разбиением ₁, поставлена в соответствие группа - множеств 1: {2, 1, 4 },{ 5, 2}, включающих состояния, которые являются преемниками соответствующих состояний блоков разбиения ₁.

В отличительном дереве автомата A-1 каждому - множеству вершины дерева поставлено в соответствие - разбиение множества начальных состояний, для которых состояния - множеств являются конечными состояниями при приложении к входу автомата последовательности входных символов, соответствующих меткам дуг отличительного дерева. Путь в отличительном дереве от его корня до вершины, отмеченной группой простых -множеств, определяет отличительную последовательность минимальной длины. Отличительная последовательность X₀= (X₁, X₁, X₁, X₂, X₁) автомата А-1 определяет следующую последовательность - разбиений начальных состояний