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

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

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

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

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

Добавлен: 30.06.2024

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

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

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

Термин «расширение» подчеркивает тот факт, что у автомата В может быть «богаче поведение», чем у автомата Л, т. е. у автомата В может быть больше различных выходных последовательностей, чем у автомата А .

Пусть на множестве SA X ХА задано отношение эквивалентно­ сти п. Известно, что каждому разбиению Е некоторого множества D ставится во взаимно однозначное соответствие отношение эквивалент­ ности є на множестве D, определяемое соотношением (d, g) £ є <-> <-> d s= g (E). В дальнейшем разбиение и соответствующее ему от­ ношение эквивалентности будем обозначать одинаковыми гречески­ ми буквами: большой — разбиение и малой — отношение эквива­ лентности.

Определение 6.2. Автомат С = ( S A , ХА, УС, б^, Хс) назовем соб­ ственным П-расширением автомата А , если Yc = У А X П И ХС (S, х) = (ХА (s, х), К (s, х)), где К (s, х) — класс разбиения П, содер­ жащий элемент (s, л-). Автомат В назовем it-расширением автомата А , если В есть расширение собственного я-расширения автомата А .

Легко видеть, что собственное я-расширенне автомата есть рас­ ширение этого автомата.

Каждому отношению эквивалентности є на множестве D един­ ственным образом соответствует отображение ХЕ: D Е, определя­ емое соотношением Хг (d) = є (d), где є (а) = \g\ (d, g) £ є} — класс эквивалентности (разбиения), содержащий элемент d. Произ­ вольному отображению X : D ~>- G единственным образом соответ­

ствует отношение

эквивалентности e ^ s D

х

D, называемое ядром

отображения X и определяемое соотношением

(d, g)

£ е\ <-+ X (d) =

=

Ь (ff)-

 

 

 

 

 

 

б, X)

 

Из сказанного следует, что любому автомату А =

(S, X,

Y,

ставится в соответствие пара (A', e>J, где

А ' = (S, X, б) —

автомат

Медведева и єх — ядро отображения X. Обратно, каждой паре (Л',

е),

где А ' = (S,

X,

б) — автомат Медведева,

є — некоторая

экви­

валентность на 5

х

X, соответствует автомат (Мили) Л = (5, X,

Е, б,

ЯЕ ), гдеЯЕ —отображение, соответствующее е. Поэтому в дальнейшем произвольную пару (Л', е) также будем называть автоматом Мили.

Каждому автомату (Л', е) можно поставить в соответствие

мно­

жество Рг

всех диагностических

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

т. е.

таких

последовательностей р £ X*, для которых из равенства

Хе (s,

р) =

— К {t, р),

гдез, t £ S , следует равенство s = t.

 

автомат

Пусть Р

cz X*. Автомат (Л', є)

(и соответствующий ему

Л) назовем Р-диагностируемым, если Р s Ре -

 

(S, X,

Рассмотрим следующую задачу. Пусть дан автомат А =

Y, б, X) и некоторое множество Р £

X*, не содержащее пустой после­

довательности е. Требуется построить такое отношение эквивалент­ ности л на множестве S X X, чтобы собственное я-расширение авто­ мата являлось Р-диагностируемым. Покажем, что эта задача всегда

имеет тривиальное решение. Для этого

полагаем, что

я =

^sxx,

где iSxx — тождественное преобразование

множества 5 X X.

Пусть

С — собственное я-расширеиие автомата

А . Покажем,

что

любой

символ х £ X будет для автомата С диагностической последователь­ ностью и тем самым покажем, что эквивалентность я есть решение поставленной задачи.

 

Пусть s и t — произвольно

выбранные состояния автомата С и

s ф t. По определению 6.2, Хс (s, х)

=

(ХА

(s, х),

К (s, х)) и Хс

(t, х)

=

=

(ХА (t, х), K{t, х)). Поскольку я =

isxx и s ф:

t, то (s, х)

(г!, х) (П)

и,

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

%с (s, х) Ф

Хс

(t,

х).

Это

означает,

что х

—

диагностическая последовательность

для

автомата С, что и требо­

валось доказать.

 

 

 

 

 

 

 

 

 

Поставленную

выше задачу

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

задачу построения выходных контрольных точек в автомате для того, чтобы любое входное воздействие из заданного множества Р позво­

ляло

определить состояние автомата. При этом контрольными

точ­

ками

естественно считать те выходные каналы я-расширения,

на

которых наблюдаются сигналы, соответствующие

классам разбие­

ния

П.

 

 

Поскольку задача построения Р-диагностируемого

я-расширения

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

6.2. Задача с и н т е з а расширений автомата

Целью настоящего раздела является построение такого расширения исходного автомата, что любая входная последовательность из заранее заданного множества последовательностей будет для постро­ енного автомата диагностической.

Введем необходимые определения и обозначения. Напомним, что

автоматом

Рабина — Скотт

[36] называется пятерка объектов

В = (5, X ,

б, s0, F), где 5,

X — конечные непустые множества со­

стояний и входных символов соответственно, б — функция переходов автомата, s0 — начальное состояние, F — множество заключитель­ ных или представляющих состояний. Автомату Рабина — Скотт В

ставится в

соответствие

множество W (В) = {р\6

(s0 , р) £

F],

ко­

торое называется событием , представленным в автомате В .

 

 

 

Подмножество

Р Е

X* называется регулярным событием, если

существует

автомат Рабина — Скотт

В , представляющий

событие

W

(В), равное Р . Известно [18], что если Р , Q — регулярные события

из

X*, то регулярными

являются и следующие события: Р U

Q,

Р

Г)

Q , P

- Q , P

• Q =

{pq/p

£ Р Л

Ч Є Q),

Р*

=

{Р/Р

= е

V

\j3k

ЗРІ

pk£P

(Р — Pi •••

Pk)}- Событие P

• Q

называется

про­

изведением событий Р и Q, а событие Р* — итерацией события Р .

Пусть задан некоторый автомат Л = (S, X, Y, б, X) и регулярное событие Р є Х * , не содержащее пустой последовательности. Нашей задачей является построение такого отношения эквивалентности

яЕ (S X X ) 2 с минимальным числом классов, чтобы собственное л-расширение автомата А было Р-диагностируемым.

Учитывая, что автомат

(А',г),

соответствующий

автомату А,

имеет множество диагностических

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

.Ре, и пола­

гая Q равным Р — Рг, нашу

задачу можно сформулировать следую­

щим образом.

 

 

 

Задача синтеза. Дан автомат Медведева А' = (S, X,

б) и регуляр­

ное событие Q <=^ X*, не содержащее е. Построить такое отношение эквивалентности я с минимальным числом классов, чтобы автомат (А', я) был Q-диагностируемым.

В силу сказанного в разделе 6.1, эта задача всегда имеет решение с помощью перебора. Рассмотрим методику решения задачи синтеза для определения возможного уменьшения перебора.

 

Вначале рассмотрим частную задачу синтеза. Дан автомат

Мед­

ведева А' = (S, X,

б), регулярное событие Q s

X* — [е]

и состоя­

ния s0, t0

£ S, s0=£

t0. Найти такую эквивалентность я на множестве

5

X X с

наименьшим

числом классов,

чтобы

Q s

Ря

(s0 .

^о) =

=

{р/Х (s0 , р) Ф

X (t0,

р)}. Не уменьшая

общности, можно предпо­

ложить,

что для

заданного события Q выполняется

соотношение

QX* Е

Q, поскольку, если последовательность р диагностическая,

то для всех р' £

X* последовательность рр' тоже диагностическая.

 

Решение частной задачи будет получено в результате построения

ряда автоматов Рабина — Скотт. Сначала по автомату А'

построим

автомат Рабина — Скотт А = (Т, X, б, {s„, t0), а). Здесь Т — это множество всех неупорядоченных пар {s, t), s, t £ S, дополненное

специальным

элементом а, б

({s, t), х)

= б (s,

х) U 8 (t, х) и

6 (а, х) — а.

Из определения

функции

переходов

автомата Л сле­

дует, что представляющее состояние а автомата не достижимо из на­

чального состояния {s0 , t0\, т. е. W (Л) =

0 .

Пусть

автомат

Раби­

на — Скотт В =

(D,

X, A, d0, f) есть минимальный автомат, пред­

ставляющий событие

Q. Поскольку

QX* s

 

Q, то у автомата В

имеется единственное

представляющее состояние f. Построим авто­

мат G = (D х Т,

X,

6G , g0,

F ) , где 6G

(d,

[s,

t),

x) = (A

(d, x),

б ({s, t], x)), go =

(d0,

{So, t0))

и g£ F,

если g

=

(f,

[s,

Ц) для некото­

рых s, t £ S.

 

 

 

 

 

 

 

 

 

 

 

В дальнейшем автоматом G будем называть подавтомат автомата G,

порожденный начальным состоянием g 0 .

Очевидно, что

W (G) — Q.

Напомним, что пара (g, р), где g £ D

X Т и р

£ X*,

называется

переходом автомата G. Переход (g, х) назовем конечным переходом для автомата G, если g$ F и 6а (q, х) £ F. Множество всех конеч­ ных переходов автомата обозначим через Z (G).

Теперь по автомату G построим автомат Рабина — Скотт Л я , учитывающий структуру автомата Л' и представляющий событие

W (Ал),

содержащее

Q. Автомат Л я = (Т, X,

бя , {s0, t0},a) определя­

ется

так:

 

 

 

 

 

б я

({s,

t),x) = а,

если

((d, {s, t}), x)£Z(G)

для некоторого

d,

 

 

6({s, t),

x) в противном случае.

^ ^

Вдальнейшем автоматом Ал будем называть подавтомат автомата

Лл , порожденный начальным состоянием {s0 , t0). С целью нахожде­

ния события

W (Ап) рассмотрим некоторые свойства автомата

Л я .

Ядром Рп

регулярного события Р назовем множество всех

тех

последовательностей р из Р, для которых выполняется соотношение:

q

<Z р

q $

Р.

Напомним, что q •< р, если для некоторого

р'

£Х*-

\е)

qp'

= р.

Учитывая соотношение QX* ^ Q, получаем равенство Q„X* =

=Q.

Пусть для некоторых q £ X* и х £ X qx £ фя и W (q) =

=(р/бл ({s0 , t0), P) — бя ({s0 , t0], Я)}- Имеет место такая лемма.

 

Лемма 6.1. qx£

QH

-»- W {q)xX*

<= W

 

(Ая).

 

 

 

 

 

 

 

 

" Д о к а з а т е л ь с т в о .

Пусть qx £ Q„.iИз определения ядра

следует, что

(б 0 (g0>

°), *)

£ Z (G). Тогда по

(6.1), учитывая

равен­

ство g„ =

 

(d0, (s0 , *„}), получаем соотношение б я

(б„ ({s0 , t0},

q), х)

=

— а. Из

 

последнего

 

равенства

вытекает соотношение W (q)xX*

 

s

S

W (Ал),

что и требовалось

 

доказать.

 

 

 

 

 

 

 

 

 

 

 

Лемму 6.1 можно записать в следующем виде: (\j „д:е<эя W (q) хХ*)

s

s

W (Ал).

 

Используя

последнее

соотношение

и

соотношение

Q_nX* =

 

Q,

получаем

следствие.

 

 

 

 

 

 

 

 

 

 

 

 

 

Следствие 6.1.

Q є

W (АЛ).

Найдем событие, представляемое

в

автомате

 

Ая.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Лемма 6.2. W (Ля ) =

\}„х^я

 

W

(q)xX*.

6.1

(J

 

 

 

 

 

 

s

 

Д о к а з а т е л ь с т в о .

 

По

лемме

 

W

(q)xX*

 

<=

W (Ап).

Покажем,

что

 

W (АЛ)

=

[}

W

(q)xX*.

 

Пусть.

р £ W (Ля )

и р 2 — такой

начальный

отрезок

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

р,

ч т о р х £

№Я (ЛЯ ). Следовательно, 6 n ( { s 0 , - i 0 } , p 1 ) = а. Тогда, если по­

ложить, что р! = р2л; и б я ({s0 ,

£0 j, р2 ) =

js, і}, то по

(6.1) существу­

ет d

£ D,

 

для которого ((d,

{s,

t}), х) £ Z (G).

Поскольку

состояние

(d,

{s,

t})

автомата G достижимо из (d0, {s0 , t0})

и поскольку

W

(G)

=

=

Q,

то

существует

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

q,

для

которой

бс

(d0,

{So,

t0),

q) = (d,

{s,

 

ф

и

qx

£ Qn. Тогда

p2x

£ W (q)xX*

a

p £

£

W

(q)xX*.B

силу произвольности последовательности p W (Ал)

 

s

=;

 

 

U

 

^

(я)хХ*,

что и доказывает лемму.

 

 

 

 

 

 

 

 

 

 

По множеству Z (Ля ) конечных переходов автомата Л я

определим

отношение ф на 5

X

X. Оно задается формулой

 

 

 

 

 

 

 

 

 

 

 

((s, X

l ) , (t,

х2))£ч>^(х1

 

 

= x2-*({s,

 

t),

хг) £

Z(An)).

 

 

(6.2)

Из (6.2) следует, что отношение ф симметрично. Преобразуем авто­ мат Л л , изменяя его функцию переходов, в некоторый автомат, у ко-

торого множество его конечных переходов порождало бы по (6.2) симметричное и рефлексивное отношение ф. Пусть автомат Рабина — Скотт Л л = (Г, X, бя , {% М> а) определяется следующим образом:

о я ({s,

г}, х) =

\а,

если

выполняется условие У (s, t, х),

 

 

<_ ..

.

 

 

 

 

 

 

 

 

|ол

({s, г}, X) — в противном случае.

 

 

Условие

У (s,

t,

х)

имеет

вид б (s,

х) — б (£, х)

и

существует

последовательность р, для которой б я ({s, t), хр) — а.

 

 

 

 

В дальнейшем автоматом Л я будем называть подавтомат автома­

та Л я , порожденный состояниями, достижимыми из

начального со­

стояния.

 

 

 

 

 

 

 

 

 

 

Рассмотрим

множество

конечных

переходов

автомата

Л я .

Из определения функции 5Я

и того, что все состояния автомата

Л я

достижимы, из начального состояния следует, что если

({s, t),

х)

£

£ Z (Ля ), то

s Ф

t. Пусть отношение ф порождается

множеством

Z (Л я ) по формуле (6.2). Тогда легко видеть, что ф — симметрично и

рефлексивно. Далее, из определения функции переходов б л следует,

что W (Ля) => W (Ля ) э

Q.

 

 

 

 

 

 

Пусть ф — отношение, определенное множеством Z (Ля ) по фор­

муле (6.2), и я — произвольное отношение эквивалентности на мно­

жестве 5

X

X.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Теорема

6. J. я

s

Ф <-> Q Е

Рл

(s0> to)-

 

 

Q. По следствию

 

Д о к а з а т е л ь с т в о .

Пусть я

s

Ф и р £

6.1

р

£ W (Ля ). Пусть

qx — начальный отрезок

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

ти

р,

для

которого

qx

£ Wa

(А'„)

и б я

({s„, t0\,

q)

=

[s,

t\. Тогда

({s,

t), x)

£ Z (A'n) и no (6.2) ((s, x), (t,

x))

ф. По

предположению

я s

ф и,

значит,

((s,

0 .

 

*))

(2 я.

Из

определения

функции

б я

следует, что б (s0 , q)

(J б (<0, 9) =

{s, і). Для простота положим, что

б (s0 ,

9) =

s, б (t0,

q)

=

1 Тогда Хл

(s, х)

Ф

X (t,x)

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

Х„ (s0 , qx) Ф

Xn (t0,

qx).

Поскольку

qx <; p,

получаем, что Xn [s0,p)

Ф

Ф

 

(^o> p)> T-

e-

P €

Рл (s0 .

A>)- Таким

образом,

если

я s

ф, то

<3 =

Р Я ( %

О -

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Пусть теперь Q є

Р я

(s0,

4) и ((s> *і)>

 

хг))

€

я. Если

хх ^= х2 ,

то по (6.2) ((s, Xj), (і, х2 ))

£ ф. Пусть x x =

x2 =

x и пусть /? —

неко­

торая последовательность, для которой бд ({s0 ,

/ 0 ) , /?) =

{s, Ц. По­

скольку {s,

достижимо из

начального состояния, то такая после­

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

существует. Из

равенства

°п (а, х')

=

а,

где

х'

—

произвольное,

следует,

что

Ая

(s„, рх)

=

Ая

(/„,

рх),

т.

е. рх

^

g

Р я

(s0 , £0). По предположению

рх

&

Q, и,

значит, ({s, і}, х)

^

g Z(An).

Тогда по

(6.2)

((s,

х),

(t, х))

£ ф. Таким

образом,

если

Q s

Р я (so>

 

то я =

ф, что и доказывает теорему.

 

 

 

 

 

 

Теорема 6.1 показывает, что частная задача синтеза равносильна

задаче нахождения отношения эквивалентности, включающегося в отношение ф и имеющего минимальное число классов эквивалент­

ов

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