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

гдебп; — функция переходов Пг образа автомата А.

ция поведения состояний автомата А, состоящая из п компонент, су­ ществует, поскольку семейство {П,} состоит из нетривиальных разбие­ ний со свойством подстановки и П = 0. В качестве компоненты At

(здесь At = AL) параллельной декомпозиции М автомата А принима­ ется автомат Л п.-Сходимость семейства разбиений {П,-} равносильна связности автомата М относительно А. Это непосредственно следует из того, что изоморфизм а, соответствующий построенной декомпози­ ции поведения состояний, задан равенством а (а) = (Кп (а), •••

...,Кпп (а)).

Функция выходов Л автомата М определяется соотношением

Пусть {П,} (1 •< і •< п) — семейство разбиений множества со­ стояний V автомата М, в котором каждое П/ задано соотношением,

л—і

аналогичным (5.1). Пусть П0 = П П,-. Необходимо доопределить функцию выходов автомата М так, чтобы выполнялось неравенство

П0 >• Щ, можно доопределить функцию выходов Л автомата М так, что будет выполняться неравенство По > ПЛ . При этом фигурирую­ щее в формуле (5.12) отображение g следует заменить отображением /. В результате получим автомат Мх, который может отличаться от М

мой. Теорема доказана.

Проиллюстрируем построение параллельной компонентно-диагно­ стируемой декомпозиции сильно связного автомата на примере авто­

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

Поскольку семейство разбиений {П^ П2 , П3 } удовлетворяет всем, условиям теоремы 5.5, то можно заключить, что существует нетри­ виальная компонентно-диагностируемая параллельная декомпози­ ция поведения состояний автомата ЛЗ, состоящая из трех компонент. Схема соединения компонент параллельной декомпозиции автомата ЛЗ показана на рис. 18, а компоненты Аи Л2 , Л 3 этой декомпозиции; представлены табл. 32, 33 и 34 соответственно.

Введем обозначения:

В рассматриваемом примере

і/ = {А, В, С, D, Е, F, G, Н, К) и a(S) = = {Л, В, С, D, Е, G, К).

Для доопределения функции выходов Л автомата М строим отобра­ жение /, которое представлено табл. 35. Далее находим

Поскольку сеть, соответствующая автомату Мъ связна относительно ЛЗ и По ;> Пд, то она компонентно-диагностируема.

Г л а в а 6

Р А С Ш И Р Е Н И Я А В Т О М А Т О В

Одной из основных задач технической диагностики является задача обеспечения заданного уровня контроля и локализации неисправ­ ностей в процессе проектирования устройства. В работе [15] эта за­ дача сводится к задаче выведения в устройстве контрольных точек для достижения этого уровня.

В теории автоматов такую задачу можно сформулировать как задачу изучения методов преобразования заданного автомата в авто­ мат, который реализует заданный и для которого можно провести заданный тип эксперимента. Искомый автомат можно интерпрети­ ровать как автомат с контрольными точками. Преобразование дан­ ного автомата в автомат с контрольными точками может проводиться на этапе как абстрактного [18], так и структурного синтеза автома­ тов.

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

Методы построения расширений автомата, рассматриваемые в этой главе, являются дальнейшим развитием идей работы [66]. Материалы главы частично основаны на работах [21—23].

6.1. О п р е д е л е н и е расширения автомата

Пусть заданы автоматы А = ( S A , Х А , YА, &А, У И В = ( S B , Х В , Ув, 6в, ^в)- Обобщим понятие реализации поведения состояний автомата, введенное в главе 5. Тройку отображений (а, і, £), где а : S A ->• SB,

для всех s £ SA, x £ X A , назовем представлением автомата А в авто­ мате В. Следуя работе [60] автомат В будем называть реализацией поведения состояний автомата Л, если существует такое представле­ ние (а, і, 0 автомата А в автомате В, для которого а — взаимно однозначное отображение.

Определение 6.1. Автомат В назовем расширением автомата А, если ХА = ХВ и существует такое представление (a, i , Q автомата А в автомате В, для которого і — тождественное преобразование, а а — взаимно однозначное отображение.

Из определения 6.1 следует, что расширение автомата есть част­ ный случай реализации поведения состояний автомата.