Файл: Богомолов А.М. Эксперименты с автоматами.pdf

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 30.06.2024

Просмотров: 134

Скачиваний: 0

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

2. Для элементарных частичных тестов хи

х2,

 

xt вычисляе­

тся значение функции

распознаваемости:

 

 

 

 

 

 

 

 

DA(XL),

DA(Х2),

 

. . . ,

DA(*,).

 

 

 

 

3.

Из элементарных

частичных

тестов выбирается тест рх

=

хг

с наибольшим значением функции DA (ХГ).

 

 

 

 

 

4.

Производится выбор следующей компоненты теста р = /?1 ( оа .

Для

этого согласно

(3.17) строятся

множества

 

 

 

 

 

 

L A

(рххх),

LA(pxx2),

 

. . . .

 

LA(plxl).

 

 

 

 

5.

Вычисляются

значения

функции

распознаваемости

 

 

 

 

DA(pxxx),

DA(p1x2),

 

 

 

DA(p1xl)

 

 

 

 

и определяется

максимальная

разность

 

 

 

 

 

 

 

max

| D A (pxxt) ~

D A

(рх) \

при і

=1,1,

 

 

 

і

 

 

 

 

 

 

 

 

 

 

 

 

а)

если максимум достигается

при і = т,

то за

последователь­

ность р 2 принимается хт,

и с новой последовательностью ргхт

в ка­

честве последовательности рх переходим

к этапу

4;

 

 

 

б)

если при некоторых і D А (РхХі) — 1, то процесс окончен

и

со­

ответствующие последовательности р1х1

являются

распознаваю-

щими;

 

 

 

 

 

 

 

 

 

 

 

 

в) если D A (рххх)

= D A (рхх2)

=

- • • =

D A (ptxt)

=

D A (рг)

<

1, то

это означает, что под воздействием

входной последовательности

рх

автомат А перешел в эквивалентные состояния (что возможно, когда класс (2.1) не исключительный), и в дальнейшем воздействие вход­ ных последовательностей вида р = рхр2 не увеличит различимость

вклассе. В этом случае переходим к этапу 6.

6.Осуществляется «выход из тупика» возвратом назад на пре­ дыдущий этап, и вместо последовательности рх = хТ выбирается

последовательность рх = xq со значениемDA (xq), близким к D A (хг), и происходит выход к этапу 4. Если в течение ряда попыток «выхо­

да

из тупика» не

удается достичь

большего значения

функции

DA

(PI), то процесс

окончен, и все

последовательности

с макси­

мальным значением функции распознаваемости являются макси­ мальными частичными тестами для класса автоматов.

Отметим некоторые особенности метода.

1. При построении множеств L A (P1P2) согласно (3.17) на этапе 4 используется полугруппа векторов различимости, пример которой представлен в табл. 10 для класса автоматов при п = 4.

2. Количество вычислений значительно уменьшается и сходи­ мость метода ускоряется, если на этапе 4 в качестве следующей компоненты р 2 выбирать частичные тесты р с d (р) > 1, полученные на предыдущих стадиях вычислений. При этом объем вычислений не зависит от длины компоненты р2 .

3. Метод допускает построение теста добавлением новых компо­ нент как справа, так и слева, что следует из (3.17).

74 і

4.Метод можно использовать для определения исключитель­ ности класса автоматов, или определения эквивалентных состояний на основе информации, содержащейся во множествах LA (р), полу­ ченных на заключительном этапе метода.

5.Схема метода полностью применима при решении задачи конт­ роля для класса автоматов.

Проиллюстрируем метод на примере класса из четырех автома­ тов, таблицы переходов и выходов которых представлены в табл. 11.

 

\

 

 

 

 

 

Т а б л и ц а

11

At

Х

x2

 

 

* i

 

хз

 

S

\

* 3

* 4

 

* 4

 

4

4

4

4

4

Уі

Ух

Уг

Уз

л,

4

4

4

4

4

Уі

 

Ух

Уг

 

4

4

4

4

4

Уз

Уі

Уг

УІ

 

9

4

9

9

4

Ух

Уз

 

Уі

 

S I

S l

«Ї

УІ

А,

si

9

4

9

9

Уз

Уг

 

•

S?

S3

s 2

Ух

Уз

 

9

9

4

4

9

 

 

Ух

Уі

 

s 3

s i

s 7

УІ

У4

 

4

s3

4

4

4

У*.

Уі

Уз

УІ

Л

4

s3

4

4

4

УІ

Уг

Ух

Уз

 

 

S3

 

 

 

 

 

 

 

 

4

4

4

4

4

Ух

Уг

Уг

УІ

 

4

4

4

4

4

Уг

У2

Уг

УІ

А,

4

4

4

4

4

Уг

Уз

Уз

Ух

 

4

4

4

4

4

УІ

Уз

Уг

Уг

Класс автоматов характеризуется следующими парами: St = [s\,

si,

$з}> X — \XV

X2,

X3,

JC4 ),

 

 

 

 

 

Y =

{yvy2,y3,y4},

I =

{1,2,3,4}.

 

M-структура

векторов различимости

для данного класса

при

п = 4 представлена

на рис. 9, полугруппа векторов различимости

приведена в

табл. 10.

 

 

 

Строим таблицу

переходов' — выходов автомата

А ,

имеющего 81

состояние,

получая

одновременно

 

множества

L A

(хг),

LA (Х2),

L A (Х3), LA

. Вычислим

функции

распознаваемости.

Получаем

значения:

 

 

 

 

 

 

 

 

 

 

 

D A (XJ) =

0,778,

DA{x2)

=

0,802,

D A

(л'3) = 0,670,

DA{xJ

 

= 0,792.

Максимум достигается при DA (Х2). В качестве первого символа теста

выбирается р х

=

х2. Строим множества LA (Х2ХС) при і

=

1,4 и вы­

числяем для них функцию распознаваемости:

 

 

 

D A ( Х Л )

=

0,965, D A (х2х2)

=

0,946, D A (х2х3)

=

0,909,

 

 

 

 

D^(x 2 ^) =

0,979.

 

 

;

Максимальное приращение функции получается на втором шаге

при выборе символа р 2 =

хА.

 

 

 

 

 

 

 

Принимаем за последовательность

рх — х2хА и переходим

к І

эта­

пу

4 для

построения множеств

LA (Х2Х^Х{).

Построив

эти

множе­

ства, вычисляем функцию

распознаваемости

 

 

 

 

 

D A (x2xiXl)

= 0,999, D A (х2х,х2)

=

0,979,

D A (х2х,х3)

= 0,999,

 

 

 

 

 

D A {Х2

 

xtxt)=l.

 

 

 

 

Процесс окончен, и найдена распознающая последовательность/?

=

=

х^хлхл.

Заметим, что для данного

класса

распознающей

после­

довательности

из двух символов не существует. Как было отмечено,

функция распознаваемости позволяет ввести квазипорядок на мно­

жестве частичных тестов (рефлексивное и транзитивное

отношение)

 

p 1 < p 2 ^ D x ( p 1 ) < D / i ( p 2 ) .

(3.25)

Так, для примера, в предыдущем разделе квазипорядку

удовлетво­

ряют тесты: XgX2

5> ххххх9

в силу того, что

 

D A

(*З Х2) =

0,980, D A {хг хг х3) = 0,940.

 

Наряду с распознаваемостью, другой существенной характеристи­ кой частичного теста р является его длина d (р). Пользуясь этими двумя характеристиками, можно на множестве всех частичных те­ стов для данного класса автоматов определить следующее отношение квазипорядка:

Pi<P2~ (d(р2)< d(Р0 Л D A ( P L ) < D A (р2 )). (3.26) Легко видеть, что (3.26) рефлексивно и транзитивно. Этот квазипо­

рядок можно

интерпретировать

так: тест р 2 «лучше», чем тест р 1 ;

так как он

более короткий и

имеет большую распознаваемость.

Для рассмотренного примера этот квазипорядок имеет место между

следующими

тестами: ххх2

>-

х^х^х^, так

как

DA [ХХХ2)

=

0,930

и DA {XJ^XJ)

= 0,870,

и х^х4 >

х^х^,

так

как

DA (Х^)

—

0,960

и D A (Х1Х1Х2)

— 0,950.

На основании, свойства функции

распозна­

ваемости DA (р) <С DA (рр')

можно

на множестве частичных те­

стов задать

иерархический

порядок

следующим

образом:

 

 

Pi < Р2

*-»• 3 р- (р2

= РлР')-

 

 

(3-27)
Рис. 10. Иерархический поря­ док с корнем я, и одной вет­ вью х4 для примера в в табл. 13.

Иерархический порядок задает на множестве частичных тестов систему деревьев, корнями которых являются элементарные частич­ ные тесты, и вершинам, более удаленным от корня, соответствуют частичные тесты с большим значением функции DA (р). Деревья являются бесконечными, однако представляет интерес только их конечная часть, которую можно выде­ лить введением следующих правил об­ рыва бесконечных цепей:

1) вершина в дереве считается конеч­ ной, если ей соответствует частичный тест со значением функции DA (р) — 1; 2) вершина в дереве считается конеч­ ной, если всем следующим непосред­ ственно за ней вершинам соответствуют частичные тесты, распознаваемость кото­ рых равна распознаваемости данной вер­

шины.

Пример такого дерева с корнем хг и одной ветвью xt для класса автоматов, представленного в табл. I I , приведен на рис. 10.

Введем понятие эквивалентности или неотличимости частичных тестов. Два частичных теста для класса автоматов являются 'эквивалентными, если им со­ ответствуют равные множества LA (р):

ргсор2++

LA(pj

= LA(р2).

(3.28)

Для решения задачи распознавания класса автоматов достаточно знать раз­ биение множества 5, порождаемое мно­ жеством L A (р), поэтому на множестве

частичных тестов можно задать следующее отношение равенства:

PiosPt**

V.eiV(Р14рл(Pi, Ri) = ргх рл(p2 , Rd).

(3.29)

Отношение (3.29) является отношением эквивалентности на полу­ группе X* с конечным числом классов в силу конечности числа клас-' сов разбиения конечного множества состояний S автомата Л.

Значительный интерес представляет задание на множестве ча­ стичных тестов отношения сходства или толерантности т [25, 49, 50] в следующем виде:

рх тр2 ^> L A (рг) П L A (р2) ф 0 .

(3.30)

Толерантность тестов, близких к равным по отношению (3.29), задается следующим соотношением:

/ W i * * У<є*(рГіР<*(Рі, Rt) П рГіРдОо,,

ЯдФ0).

(3.31)

77

Легко видеть, что (3.30) и (3.31) являются толерантностями по соответствию i}> : X * ->- L*A (р), определяемому автоматным отобра­ жением автомата А . Соотношения (3.30) и (3.31) симметричны, а их рефлексивность следует из того, что соответствие \|) определено на всей полугруппе X * . Однако транзитивность здесь не имеет места, поэтому нельзя говорить о классах толерантности тестов. Для каж­ дого частичного теста р можно согласно (3.30) или (3.31) определить класс толерантных к нему тестов, однако между элементами этого класса толерантность может не иметь места.

Ввиду того, что множества {ргх рл {р, Ri)}, і Є N, представляют совокупности непересекающихся классов, индексированных век­ торами различимости Rt, можно ввести количественную меру толе­ рантности с помощью следующей функции:

„ /

„

о

D \

1 рті 9 Л (РЪ Ъ) Л РГ! РЛ (Ро,

Ri) |

 

 

а

 

 

R i ) =

ІРг 1 Рл(Р 1 . ^)ирг і Р л(Р,^)1 •

 

( 3 - 3 2 )

Для каждой

пары

последовательностей

(pv

р2)

можно

построить

вектор (a (р1 5

р2,

Rj), a (plt

р2, R2),

а

(р1г

р2,

RN))

размерности

N, и каждая компонента этого вектора является числом, указываю­

щим меру близости классов разбиения

с

индексом R£

последова­

тельностей р!

и

р2.

 

 

 

 

 

 

 

 

 

Если рг! рл (рх,

Ri) Г)

P r i PA (р2 . Ri)

=

0 ,

то a

( f t , р2,

R J = 0.

При полном совпадении классов разных разбиений a ( f t , р2,

R{) = 1.

Толерантность

 

частичных

тестов можно также

определить за­

висящей от двух

 

параметров —• подмножества

индексов

векторов

различимости N cz N и порогового наименьшего допустимого зна­

чения q функции

а

( f t , рг,

Rc):

 

 

Plx(N,

q)p2

^i£N (t t (Pi' Pf R^

^ °)-

(3.33)

За подмножество

 

<_>

индексов

JV можно выбирать

индексы

векторов

различимости на верхних уровнях УИ-структуры, непосредственно близких к наибольшему элементу R — IR, И принимать 0 < q •< 1.

Г л а в а 4

В Е Р О Я Т Н О С Т Н Ы Е Э К С П Е Р И М Е Н Т Ы С А В Т О М А Т А М И

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

Смотрите также файлы