Метод синтеза генераторов детерминированных тестов на сетях клеточных автоматов (СКА)
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
а Xi X, i= . Образуем множество ZC = …элементы, которого представляют собой состояния, Xa - совместимые для всех входных символов множества X.
Определение 3.7 Пусть ячейка одномерной ОС без наблюдаемых выходов X представлена моделью автомата Мура (Х,Z,d), в котором Xa - преемником состояния ZiZ является состояние Zk, не обязательно отличное от Zi. Входной символ Xa X будем называть отличительным символом состояния Zi тогда и только тогда, когда Zk не является Xa - преемником для множества Z [Zi] начальных состояний автомата и Zk ZC.
Если столбец Xa таблицы переходов ячейки сети содержит пару неразличимых состояний (Zа, Zb), то есть d (Za, Xa) = Zk, d (Zb,Xa) = Zk состояния (Zа, Zb) неразличимы для входного символа Хa. В общем случае может быть две альтернативы. Пара состояний (Zа, Zb) различается, по меньшей мере, одним входным символом Хb, либо пара (Zа, Zb) - Xi совместима для каждого входного символа Xi X. В первом случае состояния Zа и Zb можно идентифицировать только приложением к входу проверяемой ячейки входного символа Хb. Во втором случае для различения состояний (Zа, Zb) можно воспользоваться множеством характеристических входных символов подобно тому, как в [1] использовались характеристические последовательности при построении диагностических экспериментов для автоматов, не имеющих отличительных последовательностей.
Определение 3.8 Пусть ячейка одномерной сети представлена моделью автомата Мура (Х, Z, d). Множество входных символов Xc={ X1, X2, …, Xr } называется множеством входных характеристических символов тогда и только тогда, когда для любой пары состояний (Zа, Zb) Z автомата
d (Za,X1) d (Za,X2) … d (Za,Xr) d (Zb,X1) d (Zb,X2) … d (Zb,Xr) (3.11)
Определение 3.9 Пусть Z={ Z1, Z2, Z3, … Zr } подмножество состояний минимального автомата А. Множество Хс={ X1, X2, X3, … Xp }, будем называть множеством характеристических последовательностей, если для каждого начального состояния ZiZ, реакция на Хс различна, то есть
l (Z,X1) l (Zi,X2) … l (Zi,Xp) l (Zj,X1) l (Zj,X2) … l (Zj,Xp) Zi Zj, (3.12)
для Zi, Zj Z, а исключение любой последовательности из множества Хс не позволяет различить, по меньшей мере, одно состояние ZiZ.
Множество отличительных и характеристических символов может быть найдено из характеристического дерева автомата ячейки сети, которое строится по правилам, приведенным в разделе 1.5 [1]. На рисунке 3.4 приведено характеристическое дерево сети (рисунок 1.2), из которого следует, что символ X1=1 является отличительным для множества состояний {Z0, Z1, Z2, Z3} символ X0=0 для состояний Z2 и Z3. Пара состояний {Z0, Z1} является X0-совместимой.
Рисунок 3.4 - Характеристическое дерево ячейки сети
Характеристическое дерево ячейки сети, представленной автоматной диаграммой в таблице 3.4, приведено на рисунке 3.5, из которого можно найти множество отличительных и характеристических символов.
Так как произведение разбиений = () и = () равно p (0), то множество Хc={ X1, X3 } является множеством входных характеристических символов. Простые s - множества для каждой вершины характеристического дерева определяют множества состояний, для которых метка вершины дерева является отличительным входным символом.
Исключения составляют лишь те простые s - множества, которые являются состояниями преемниками, принадлежащими множеству Zc то есть множеству состояний, неразличимых для всех входных символов.
Например, из характеристического дерева ячейки сети (рисунок 3.5, таблица 3.4) следует, что
= {Z3, Z4}; = {Z1, Z3, Z4}; = {Z1, Z3}, (3.13)
Таблица 3.4 - Таблица переходов выходов ячейки сети
Z (t) Z (t+1) X1X2X3Z1Z2Z1Z3Z2Z3Z3Z4Z3Z4Z1Z3Z4Z4Z1Z1
Рисунок 3.5 - Характеристическое дерево ячейки сети
Множества Хa - совместимых состояний ячейки позволяют определить множество Zc в виде:
Zc= ={Z3}, (3.14)
Определив множество Zc, из характеристического дерева можно легко найти множество отличительных символов и состояний ячейки, которые различаются этими символами в соответствии с определением 3.7 Для рассматриваемого примера состояние Z1, различается символом X1, состояния Z2 и Z4 - символом X3.
Определение 3.10 Пусть состояние Zj правого выхода ячейки C (k) однородной одномерной сети транспортируется на крайний правый выход сети приложением входного набора Xт к входам ячеек C (k+1), C (k+2),…. C (p). Входной набор Xт является проверяющим тестом, идентифицирующим состояние Zj ячейки C (k), если сост?/p>