ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 30.06.2024
Просмотров: 136
Скачиваний: 0
Таким образом, по (3.14), каждой конечной последовательности векторов различимости q = RxR2...Rt, полученной с выхода ком бинационной схемы К, однозначно соответствует вектор различи мости R = Rj^U R2\J ... \JRi. Для нахождения этого вектора исполь зуется полугруппа R* относительно сложения, пример которой при /г = 4 приведен в табл. 10.
На множестве состояний 5 автомата А (3.1) зададим бинарное отношение рл (р, q), зависящее от двух параметров — входной последовательности р и выходной последовательности q векторов различимости:
рА(р, |
q) = {(slf s2)| s2 = 6 ( S l , p) Л K(b(sv |
p)) = |
q). |
(3.15) |
|
По (3.14) |
последовательности q всегда |
можно |
поставить |
в одно |
|
значное соответствие вектор различимости |
R. |
|
|
|
|
Пусть N — множество индексов всех |
элементов |
М-структуры |
|||
векторов различимости. Рассмотрим при фиксированной входной последовательности р множество всех бинарных отношений {рл (р, q)}
при всех |
возможных |
q £ В*, для которых d (q) = d (р). |
Будем |
||
обозначать |
это |
множество |
|
|
|
|
L A |
(р) = |
{PA (p,q)\q£B*/\d |
(q) = d (р)}. |
(3.16) |
Множество LA (р) полностью характеризует распознающие свойства входной последовательности р для класса автоматов (2.1), так как элементы этого множества рд (р, q) указывают все возможные пе реходы состояний автомата А, при которых по (3.15) и (3.14) полу чается вектор различимости R, соответствующий последователь ности q.
Пусть дано два множества L A (Pi) и LA (рг). Элементы множества LA ІРІРІ) определяются с использованием операции произведения бинарных отношений.
Покажем, что для определенных по (3.15) бинарных отношений
справедлива формула произведения |
|
Рл (PiP2 . ?rfs) = Рл (pi, q2) О Рл (Pi, Qd- |
(3-17) |
Это следует из такой цепочки эквивалентных преобразований:
|
|
|
(slt |
s„) £ рл (ра, |
<7г) О Рл (Pi, Qi) |
|
|
||||
** |
3 >, ((St, |
s3) Є Рл (Pi, |
?i) Л (s3. s2) € PA (p2 , q2)) |
*+ |
|||||||
«-> 3 S 3 |
(s3 |
= |
б (sl t |
px ) |
Л К (A. (Si, Pi)) = ft Л s2 |
= б (Sj, |
p2 ) Л |
||||
|
|
|
|
|
Л |
K(b(Sa, |
p2 )) |
= |
q2)++ |
|
|
|
<-> |
3 s , (s3 |
= |
б (sl t p j |
Л s2 |
= |
б (s„ p2 ) Л |
<7i<72 = |
|
||
|
|
|
|
= |
/C^(Si,p1 ))K(^(s3 , Pi)))<-> |
|
|
||||
|
*-» (s2 |
= б (Si, Pip2 ) Л |
К (Я (Si, |
Px P2 )) = |
7i?2 ) |
|
|||||
|
|
|
|
«-* (si> S2) € |
Рл (PiPa, ?i<72)- |
|
|
||||
Введем в рассмотрение множество последовательностей QT =
= [q £ В* ] d (q) = /}. Символом рл (p, R) обозначим бинарное отношение, определяемое следующим образом:
рл (Р, R)= |
U Рл (Р, q). |
в
Если на вход автомата А подать распознающую последовательность рх для класса автоматов (2.1), то автомат А, находясь в любом со стоянии, выдает на выходе комбинационной схемы К последователь ность qx, которой по (3.14) соответствует наибольший вектор раз личимости R = //?, и число пар в бинарном отношении рл (рх, /«) равно числу состояний \S\ автомата А. Это очевидно при к > а. При k < п, несмотря на то, что вектора различимости верхних уров ней М-структуры с k-го по (п — 1)-й не могут быть получены с вы хода комбинационной схемы К, тем не менее эквивалентная им раз личимость достигается за счет выходных последовательностей q =
— RxR2...Rt благодаря (3.14).
Таким образом, диагностическая задача для класса автоматов
(2.1) решается с помощью входной |
последовательности р |
тогда и |
|
и только тогда, когда выполняется условие |
|
, |
|
V * s (в (/С (Ms,/>))) = /*)• |
|
(3.18) |
|
Множества {ргх олір, Ri)}tq.N образуют разбиение |
множества 5 авто |
||
матов А, где каждый класс разбиения отмечен |
вектором |
различи |
|
мости Ri. Следовательно, справедливо следующее соотношение: |
|||
U prlPA(p, |
Rd = S. |
|
(3.19) |
Как следствие (3.19), получаем соотношение 2 1 РГхРл(р, ^ ) | = |5|.
Пусть i0 £ N — индекс вектора различимости / « , тогда
| р г і Р л ( р , / Д ) | + 2 | Р Г І Р А ( Р . fli)| = |S|. |
(3.20) |
Ранее уже отмечалось, что если р — распознающая последователь ность для класса автоматов (2.1), то | рл (р, Ы) \ = |S| и, следова тельно,
| p r l P A ( p , / * ) | = | S [ . |
(3.21Г |
Тогда, как следствие этого и на основе (3.20), приходим к выводу, что для распознавающей последовательности р справедливо:
2|рГіРл(р,Я,)1 = 0. |
(3.22). |
Легко показать, что если имеет место (3.22), то последовательность р является распознающей. ^
Условия (3.18), (3.21) и (3.22) являются основой для создания методов построения теста. Условие (3.18) может быть использовано
7-і
для проверки, является ли входная последовательность р распознаю щей, но оно имеет тот недостаток, что требует вычисления функции © (К {X (s, р))) = 6 (q) для всех состояний s и сравнения ее значе ния с JR. Если последовательность р строится на каждом этапе рекуррентно добавлением новых символов, то условие (3.18) выпол нится только один раз, когда р станет распознающей последователь ностью. Поэтому с точки зрения сокращения вычислений на каждом этапе более удобно использовать отрицание этого условия, которое имеет вид
3s£s(e(K(X(s, р)))ФЫ)
и является необходимым и достаточным условием того, что р не яв ляется распознающей. Это условие истинно всегда, когда р еще не является распознающей последовательностью, и для проверки этого достаточно найти только одно состояние s, при котором ус ловие выполняется.
На |
М-структуре векторов различимости |
определим |
функцию |
fij (R) |
следующим образом: значение функции |
на элементе |
R равно |
отношению числа различимых пар автоматов в классе по вектору
различимости R |
к числу |
всех возможных пар автоматов в классе. |
|||||||||||
На множестве бинарных |
отношений |
LA (р) определим другую |
|||||||||||
функцию |
]ІАІР, |
R) |
следующим образом: |
|
|
|
|||||||
|
|
|
|
, |
™ |
|
|Ри(/>.Л)1 |
|
|
ІР/(Р.Л)| |
(3.23) |
||
|
|
|
|
|
|
|
> j |
I РА (Р. |
1 |
|
I |
Л 1 |
|
Отметим |
основные |
свойства |
функции |
\ХА (р, |
R): |
|
|||||||
1) |
если рА |
(р, |
R) |
= |
0, |
то ЦА (р, |
R) |
= |
0; |
|
|
||
2) |
\Х.А (р, |
R) |
изменяется в интервале от 0 до 1; |
|
|||||||||
3) |
2 |
^ |
(р, |
Rc) |
= U |
|
|
|
|
|
|
||
4) |
если р |
— распознающая последовательность, то |
\ІА (р, IR) = |
||||||||||
=1 и \iA (р, Rt) = 0 при всех R{ Ф IR.
Дадим содержательную интерпретацию частичного теста. Рас
познающие свойства частичного теста р для класса автоматов одно значно определяются множеством LA (р), элементы которого заданы на множестве всех состояний автомата А. Если решается задача распознавания класса автоматов и за множество начальных допу стимых состояний для каждого автомата класса принимается все множество состояний, то функция \л.А (р, R) дает вероятностную меру распознающей способности входной последовательности р: значение функции [iA (р, R[) равно вероятности того, что последовательность р обеспечивает различимость, определяемую вектором R£, при рас познавании класса автоматов, а класс ргх рл (р, Rt) разбиения множества состояний 5 указывает, из каких начальных состояний достигается эта различимость. Имеющая здесь место неопределен ность связана с тем, что перед приложением входной последователь ности р неизвестно истинное начальное состояние исследуемого автомата, как одного из представителей класса. Чем большей ин-
формацией располагает исследователь перед началом эксперимента о множестве начальных допустимых состояний для каждого авто мата в классе (насколько оно меньше всего множества состояний), тем в большей мере снимается неопределенность о распознающих свойствах частичного теста. В предельном случае, когда известно,
п
что ргх рл (р, IR) = X S;o = S0, то частичный тест р является
/ = 1
распознающим тестом.
Введем понятие распознаваемости класса автоматов. Определение 3.3. Распознаваемостью класса автоматов (2.1) (ав
томата А, определенного формулой (3.1)) называется функция DA (р):
DA (р) = 2 |
(RT) • v-A (р, Ri), Р Є X*. |
(3.24) |
Отметим основные свойства этой функции: |
|
|
1) DA (р) принимает значения в интервале [0, \ ]\DA |
(р) = 0, ког |
|
да входная последовательность р обеспечивает нулевую различимость
по всем состояниям; DA (р) |
~ 1, когда последовательность р — рас |
|||
познающая, т. е. |
(IR) = |
1, \IA (р, IR) = 1 и |
\iA {р, Ri) = 0 при |
|
всех Ri Ф IR; |
|
|
|
|
2) DA (р) |
не убывает с |
увеличением длины |
последовательности, |
|
D A (р) < D A |
(рр'). |
DA (р) класса автоматов |
может быть принята |
|
Распознаваемость |
||||
в качестве одной из возможных оценок распознающих свойств вход ных последовательностей, которая обеспечивает их линейную упо рядоченность как тестов.
Значение функции распознаваемости можно принять как одну из возможных количественных мер частичности теста для классов автоматов.
Частичный тест р с длиной d (р) = 1 назовем элементарным ча стичным тестом. Очевидно, что для получения множества LA (р) для любой последовательности р достаточно наличие всех множеств
для элементарных частичных тестов |
L A (*i), LA (х2), |
LA (xt)t |
|
где xlt x2, |
xt — символы входного |
алфавита. Все эти множества |
|
могут быть получены из таблицы переходов — выходов автомата А. Используя линейную упорядоченность частичных тестов функ
цией DA (р), можно предложить метод построения частичных те- _ стов, который назовем методом направленного поиска. Этот метод позволяет на каждом шаге получить частичный тест с наибольшей распознаваемостью, и выбор следующего шага по доопределению теста происходит с учетом линейной упорядоченности частичных тестов.
Алгоритмическая схема метода состоит из следующих этапов. 1. Для класса автоматов (2.1) строится таблица переходов-вы ходов автомата А (3.1), которая содержит все множества для эле
ментарных частичных тестов:
L A (хг), L A (Х2), . . . , L A (xt).