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

алгоритма

AL

Лемма

6 . 5 . Пусть ср •=/= N X N и для каждой пары

(а, Ь) £ ср'

выполняется

| Ф » | > 1 ^ | Ф ' ( * > ) | = 1.

( 6 . 5 )

Тогда

для любой перестановки

М

эквивалентность я (М,

ф) имеет

два класса и оптимальна.

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

Пусть П = П (М,

ср) = (А^,

/<"г)

для некоторой перестановки М

— (аъ

ап). Из п. 5 леммы 6.3 сле­

дует,

что

г >

2.

Покажем,

что

N s

Кх

U К2- Очевидно,

что

аі

Є К\ U К2-

Пусть L =

(аъ

а,) и L £

/С] U К2. Покажем, что

Є

АГІ U /С2. Если | L П Ф' <А-ы) | <

1 .

то

£ ~Кг U АГА- Пусть

L[)q>'

(аж)

~

(^ii

b()

и а / + 1 gf

АТхТогда, в силу (6.5),

по

алго­

ритму А1 элементы Ь1г

Ь{ помещены

в /Са и,

значит, ai+\ £

К2-

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

г =

2.

Лемма определяет множество отношений ф, для которых К А (ф) £

s

Ка

(ср), т. е. в этом случае

с помощью алгоритма А\ строятся

только оптимальные эквивалентности. Заметим,

что при этом

мощ­

в

лемме 6.5, существуют эквивалентности с

как угодно большим

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

Л емма 6 . 6 . Для любого натурального числа

существует множест­

во N (отношение ц> N X N и максимальная эквивалентность ге £

£

К А (ф)), число классов которой больше с.

Д о к а з а т е л ь с т в о . Зафиксируем

число с. Пусть N =

щему

правилу: ф' =

{(2t — l,2i),

(2t, 2i — 1)}! ^ , ^„.Возьмем

из ./V

первые 2с

элементов

и положим,

что

Кх — (1, 3, 5,

2с— 1},

К2 =

(2),

/<з = (4),

Kc+i = {2с}. Затем возьмем следующие

2 (с —

1) элементов,

все нечетные выбранные элементы поместим

в К2,

первый четный

поместим в К3,

второй

— в АГ4

и

так далее.

Последний нечетный элемент из выбранных

поместим

в Кс+\- Про­

должая построение таким образом и далее, за с шагов

исчерпаем

все множество N. Легко видеть, что эквивалентность л,

соответству­

ющая

построенному

разбиению,

является

максимальной,

имеет

ния.

Пусть зафиксированы

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

М =

(ах,

ап). Пусть

по алгоритму

Л1

построено

разбиение

(К и

КГ) и г > 2.

Выберем пару i, j ,

1 <

і <

/ < г,

и построим

отношение ф,7 = Ф U

(Кц

X Ки), где К и = К і (J

Kj-

Пусть П,-/ =

П (М,

фо). Очевидна следующая лемма.

Лемма 6.7. П у = (Kt,

Ki-u КЦ, К,+и

.... КГ).

Оценим число классов эквивалентности, построенной по алго­

ритму ЛІ.

Теорема 6.6. Для всех отношений <р на множестве N число классов

произвольной жвивалентности

из К А (ф)

не превосходит

/

-

4 + 2.

(6.6)

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

Очевидно,

что

для

всех

отношении

выполняется неравенство

До­

k

, где

k

наимень-

2

2

шее целое, для которого

>

4-. п Р и t

= .

k_

2 . в ы п о л н я е т с я COOT-

Т а б л и ц а

37

ношение

(6.5) и по лемме 6.5

1

2

3

4

5

6

7

8

число

классов

любой

эквива­

лентности-из К А (ф) равно

2, т. е.

0

0

0

1

0

0

0

0

1

(6.6)

выполняется.

Предполо­

жим, что для всех отношений

ф ь

0

0

0

1

0

0

0

2

у которых tt

меньше некоторого

0

0

0

0

0

0

3

0

0

0

1

0

4

фиксированного

/ >

-|-

,

со­

0

0

0

0

5

отношение

(6.6)

выполняется.

0

0

1

6

0

0

7

Пусть для

некоторого

отноше­

0

8

ния

ф t =

/.

Поскольку

при

k = 0 и k =

2

теорема

очевид-

на, а случай k

1 невозможен, то можно считать, что k >• 3. Пусть

М — произвольная

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

и П~ (М,Кф) =г

(/С)1;

.

При

г <;

2

неравенство

(6.6)

выполняется.

Пусть

г

> 3.

Положим

t =

г — 1, / =

г и по алгоритму А1 построим разбиение П (М,

ф,у)

=

= П,; , которое в силу

леммы 6.7

имеет

г —

1 класс.

Из

определе­

ния

-;

что

ргх ф' =

рг^р,-; и tii <z

t.

По

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

ф,Ф7 следует,

2. значит г < ; t

|- +

2.

Таким

образом,

1

< 4 7 - 4

+

соотношение (6.6) выполняется для всех ф.

оценка (6.6)

может

Заметим, что при одном и том же значении t

Пусть отношение ф задано табл. 37, в которой ait

=

1, если

(І, /) £

£

ф'. Для

этого отношения

^

~ + 2J = 3 .

Из перестановки

N

=

(1, ....

8) по алгоритму

Л1 строится разбиение П (N,

ф) =

=

а,

2, 3,

6; 4, 5, 8, ; 7}, у

которого три класса,

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

мальной, поскольку из

перестановки М = (8, 7,

1)

по алгоритму

Л1 строится разбиение

П (М, ф) = {8, 7, 5, З, 1; 6, 4,

2}.

6.4.

Модифицированная

задача

с и н т е з а расширений автомата

Пусть

задан

автомат А — (S, X, Y, 6, Ц и отношение

эквивалент­

ности

со на

множестве 5.

Пусть

для

последовательности р £ X*

задано

натуральное

число

*ф (р),

0 <

ip (р) <: d (р),

называемое

далее отметкой.

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

назовем

разрешающей

Определение 6.4.

для множества S , s 5

относительно (со, ip)

(сокращенно

(S0 ,

и, ip)-

разрешающей), если для всех s,

£ S0

Я. (s, р) = % (t, p)

(б (s, p'),

б (/, p')) Є ©,

(6.7)

где p' — начальный

отрезок длины ip (р) последовательности

р.

Пусть под действием последовательности р автомат проходит

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

sl t

sk, где s0 —

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

общим, чем понятие установочной

и

диагностической

последова­

тельности [16]. Так приір (р) = 0

(S0 ,

со, ^-разрешающая последо­

вательность р является (S0 , «^-диагностической, а при ч|з (р) =

d (р)

является (S0 , со)-установочной.

экви­

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

валентность

со,

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

Р

непустых

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

ностей из

X* и

отображение 1р : Р

->-

N, где

N —

множество

где S0 — S, P — множество всех последовательностей фиксирован­

ной длины Г>ил|) (р) = 0 для всех р £ Р.

Проведем некоторые вспомогательные построения. Для каждой

неупорядоченной пары состояний (s, t) автомата Л, где s Ф

t, и для

каждой последовательности р £ Р, которая

не

является

( {s,

t),

со, я|з)-распознающей, построим ориентированный

граф Г (s,

р)

по

правилам:

1. Множество вершин Т графа Г (s, t, р)

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

ненным выделенной Еершиной у, где у

^ S.

2.

Из вершины {с, d) в вершину {/, g\ проводится

дуга с

отмет­

кой х

£Х,

если существует

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

qx

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

ности р, для которой б ({s,

t],

q) =

{с,

d), 6({s, t\,qx)

=

\f,g\.

3. Из вершины {с, d) в

вершину у

проводится дуга с отметкой

х £ X, если существует начальный отрезок qx последовательности р г

для которой б (\s, t), q)

— {с,

d] и б (s, qx) =

б (і,

qx). Если т|і (p) =

= 0, lx (p)

= A'j, то дугу из (s, і} в у с отметкой A'J (если

такая дуга

существует) отметим дополнительной отметкой 0.

Множество всех дуг

графа Г (s, t, р) обозначим через R (s, t, р).

Дугу из вершины {s,

с отметкой х будем обозначать через ({«, Ц, х).

Пусть дано некоторое множество Н графов Г

(s,

t,

р). По мно­

жеству N построим ориентированный граф Г, определяемый прави­

лами:

1. Множество вершин графа равно множеству Т.

2.

Из

вершины

в вершину

g2

проводится

дуга

с отметкой-

х £ X, если хотя бы у одного графа Г (s, t, р)

£ Н

из g1

в g2

прове­

дена

дуга

с отметкой

х.

3.

Каждой дуге (g,

х) графа Г присваивается вес w (g, х),

причем

w (§> х ) — 0> если существует граф Г (s, t, р)

£ Н, у

которого дуга

всех различных графов Г (s, t, р)

£

Н, у

которых (g, х) £

R (s, t, р).

что

Множество всех дуг графа Г обозначим через JR. Будем говорить,

дуга

(g, х) £ R

покрывает

множество

R (s, і, р) е

R,

если

{g,

х) £ R

(s, t, р). Наибольшее

множество дуг из R, которое покры­

вается дугой (g, х) обозначим через М

(g, х).

Пусть Z —

некоторое

множество дуг графа Г. Будем говорить, что множество Z

покрывает

множество дуг Rx £

R, если Рг

s

(J

М (g, х).

є z

Учитывая введенные определения, модифицированную задачу

синтеза можно разбить на две задачи.

Задача

1. Дан граф Г. Построить такое множество дуг Z s R,

чтобы Z покрывало множество R.

Задача 2. По заданному множеству дуг Z построить такую экви­

валентность л на множестве 5 х

X,

чтобы выполнялось соотношение

({s,

t},x)£Z^((s,

х),

(t,x))%

л.

(6.8)

При этом нужно выбирать такое множество Z и строить

такую

жеству дуг Z для каждого xt £ X найдем множество

L t по формуле

{s,t}£Zi^({s,t},xi)eZ.

(6.9)

Далее с помощью формулы (6.10), где

(6.10)

{s,t}£Zt++(s,t)e<pt,

эквивалентность nt

на множестве 5. Теперь по эквивалентностям л£

строится эквивалентность л на множестве S х

X по правилу.

(З,Х,)ЄКІ++*ЄКІІ,

(6.11)

где її,- = (/С,,,

Kir.), П = (Ki,

Кг) и г

= max г,-. Построен-

Из формулы (6.6) следует,

что при решении задачи 1 необходимо

выбрать такое множество Z, покрывающее множество R, чтобы пара­

метр (tt

Y) отношения

ф„ построенного H3Z по (6.9), (6.10) был

шим верхнюю оценку числа классов эквивалентности,

получаемой

далее по алгоритму Л1.

Рассмотрим алгоритм построения множества Z. Пусть

заданы:

автомат Л = (5, X, Y, б, X), конечное множество Р

д Р

— {е},

эквивалентность ш на множестве 5, функция т|> : Р -э- N и множество

S0 допустимых начальных состояний автомата Л.

Алгоритм А2.

1. Построим множество Н0 всех таких графов Г (s,

/, р),

для ко­

торых s, t £ S0,

s Ф t и р не является (50 , со.т^-разрешающей после-'

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

Полагаем, что Н = #„.