1.7Сеть вероятностных автоматов и её свойства.
В качестве модели, описывающей совместную работу совокупности вероятностных автоматов, будем использовать понятие вероятностной сети автоматов.
Сеть вероятностных автоматов – это шестёрка
,
где:
-
Z – входной алфавит.
-
, – множество компонентных автоматов (КА) сети. КА - полуавтомат, его множество состояний, его входной алфавит:
его функция переходов
-
W – выходной алфавит сети.
-
- множество функций соединения компонентных автоматов сети.
-
– множество входных функций.
-
- выходная функция сети, где случайная величина .
-
случайная величина,
Множества и назовём, соответственно, базисом и структурой сети.
Определённую таким образом вероятностную сеть можно рассматривать как общую модель совместной работы совокупности вероятностных автоматов, поскольку в ней нет ограничений ни на выбор элементов базиса, ни на выбор структуры.
Для сети N можно строить функционально эквивалентный ей автомат , который будем называть результирующим автоматом сети N.
Результирующим автоматом сети назовём автомат
,
у которого:
-
-
-
-
Функция переходов , определяемая следующим образом:
Здесь
-
Функция выходов (в модели Мили), определяемая следующим образом:
В модели Мура
1.8Алгоритм декомпозиции вероятностного автомата.
Введённые понятия сети автоматов и её результирующего автомата позволяют сформулировать задачи композиции и декомпозиции автоматов. Под задачей композиции автоматов понимается задача нахождения для сети N её результирующего автомата .
Для определения задачи декомпозиции автоматов введём дополнительные понятия.
Автомат называется подавтоматом автомата , если и только если и для любого справедливо
где .
Другими словами, на области определения автомата поведение обоих автоматов совпадает. Таким образом, автомат S «делает столько же, сколько и , и, быть может, несколько больше».
Автоматы S и называются изоморфными, если существуют три взаимно-однозначных отображения
,
таких, что
и
для любых и , где .
Тройку отображений , и называют изоморфизмом автоматов и . Кратко понятие изоморфизма формулируется следующим образом: образ функции равен функции образов. Иначе, изоморфные автоматы идентичны с точностью до обозначений состояний, входных и выходных сигналов.
Автомат назовём реализацией автомата (обозначение ), если у автомата S существует подавтомат, изоморфный . Таким образом, если автомат S реализует автомат , то поведение с точностью до обозначений совпадает с поведением на области определения , так как у автомата S должен быть некоторый подавтомат , изоморфный .
Под задачей декомпозиции автомата S будем понимать задачу построения сети N, такой, что её результирующий автомат реализует заданный автомат S, т.е. .
1.8.1Разбиение множества.
Разбиением множества А называется множество , элементы которого – подмножества , удовлетворяющие следующим условиям:
-
Для любых двух множеств и .
-
-
.
Множества назовём блоками разбиения .
Пусть – множество состояний компонентного автомата . Определим разбиение на множестве следующим образом: , если и только если для всех . Таким образом, два состояния и результирующего автомата попадают в один блок , если и только если в их кодах соответственно равны компоненты .
Каждый блок соответствует различным элементам во множестве (- множество состояний компонентного автомата ), т.е. в столько блоков, сколько различных внутренних состояний имеет система автоматов . Если в , то на можно аналогичным образом задать разбиение (иногда его называют примарным разбиением). Это разбиение, очевидно, определяется следующим образом: , если и только если . Таким образом, в один блок разбиения попадают те состояния результирующего автомата, которые имеют одинаковые i-е компоненты. Следовательно, число блоков разбиения равно числу состояний компонентного автомата и между блоками и состояниями имеется взаимно-однозначное соответствие. В связи с этим можно отождествлять состояния с блоками разбиения [1].
1.8.2СП-разбиение.
Разбиением на множестве состояний автомата обладает свойством подстановки (является СП-разбиением), если и только если из (- в одном блоке ) следует, что для всех .
Иначе, под действием любого входного сигнала автомат из состояний, находящихся в одном блоке , переходит в состояния, также находящиеся в одном блоке, т.е. каждый входной сигнал отображает блоки в блоки . Таким образом, для и существует единственный блок , такой, что .
Пусть СП-разбиение на множестве состояний автомата . Тогда образом автомата S назовём полуавтомат , у которого , если и только если .
Если и СП-разбиения, то и тоже СП-разбиения.
1.8.3Процедура нахождения всех СП-разбиений.
-
Для каждой пары состояний вычисляется наименьшее СП-разбиение , которое отождествляет с (первичные СП-разбиения).
-
Находятся все возможные суммы полученных на первом шаге . Эти суммы образуют вторичные СП-разбиения.
Отождествим два состояния и в одном блоке искомого разбиения . Тогда из определения разбиения с СП следует, что для любого состояния и также должны быть отождествлены , где . Ясно, что если состояние отождествлено с , - с , то состояния и также должны быть отождествлены, поскольку разбиение соответствует эквивалентности, а последняя транзитивна. Процесс повторяется для каждой пары состояний, вошедших в один блок, до тех пор, пока не перестанут отождествляться новые состояния. Построенное таким образом разбиение имеет свойство подстановки и является минимальным разбиением, которое отождествляет состояния и в одном блоке. Чтобы получить другие разбиения, процесс повторяется для каждой пары состояний, т.е. раз, где M – число состояний автомата [1].
1.8.4Пары разбиений.
Два разбиения определённых на множестве состояний A автомата , назовём парой разбиений, если и только если из следует для всех .
Т.е. при работе S блоки переводятся в блоки под действием любого входного сигнала, т.е. для каждого и существует единственный блок , такой что .
Если СП-разбиение, то пара разбиений. Также можно показать, что если и две пары разбиений на множестве состояний A автомата S, то и тоже пары разбиений на множестве A.
По аналогии с взаимно-однозначным соответствием между блоками и состояниями , определяет входы в от других автоматов. Т.е. существует взаимно-однозначное соответствие между блоками и состояниями системы автоматов . Как и в любом автомате Мили, следующее состояние (блок разбиения ) определяется его текущим состоянием и входным сигналом (входной сигнал здесь – состояние системы автоматов и буква внешнего входного алфавита ). Таким образом, состояние в любой момент времени определяется состоянием системы автоматов , и , т.е. блоком разбиения и , поэтому пара разбиений, а реализует отображение в .
1.8.5Общая теорема декомпозиции.
Пусть некоторое множество разбиений на множестве A состояний декомпозируемого автомата .
Теорема. Множеству разбиений можно поставить в соответствие абстрактную сеть автоматов N, так чтобы , если и только если
. (1.1)
При этом устанавливается взаимно-однозначное соответствие между разбиениями и компонентными автоматами .
Полностью доказательство теоремы приведено в [5].
Множество разбиений, удовлетворяющих условию (1.1), будем называть ортогональным множеством разбиений.
Таким образом, для декомпозиции автомата необходимо выбрать ортогональное множество разбиений. Способ выбора такого множества будет описан ниже, в соответствующем параграфе.
Поставим в соответствие каждому разбиению функцию , такую, что , т.е. значение функции на паре равно блоку , в котором содержится состояние .
Образуем на множествах A и Z соответственно разбиения и , так что:
-
и находятся в одном блоке разбиения , если и только если для любого справедливо: . Иначе
-
и находятся в одном блоке разбиения , если и только если для любого справедливо: . Иначе
Полученные таким образом пара разбиений, т.е. каждый блок отображается любым входным сигналом в некоторый блок . При этом максимальное разбиение, образующее пару .
Построим сеть , для чего определим все компоненты кортежа N. Начнём с входного и выходного алфавитов сети.
-
Полагаем .
-
Полагаем .
-
Построим компонентные автоматы , т.е. определим базис сети.
-
Полагаем .
-
Для определения входного алфавита компонентного автомата воспользуемся построенными разбиениями и . Напомним, что
(1.2)
Здесь и соответственно внутренний и внешний входные алфавиты автомата .
Если на вход функции поступают выходы компонентных автоматов , то пара разбиений, где , так как максимальное разбиение, образующее пару с . Нетрудно также доказать, что . Таким образом, для нахождения автоматов, выходы которых присоединяются ко входу , необходимо найти такое произведение , которое не превосходит , и тогда выходы должны быть соединены со входом .
Определим разбиение следующим образом:
, (1.3)
т. е. не входит в это произведение, так как ко входу могут присоединяться выходы других, отличных от , компонентных автоматов.
В автомате полагаем , а определяется согласно равенствам (2).
-
Определим функцию переходов компонентного автомата .
Пусть соответственно блоки разбиений . Если , т. е. (СП-разбиение), то
.
Таким образом, значение функции переходов равно блоку разбиения , содержащему . Здесь функция переходов декомпозируемого автомата .
Если же , то
-
Построим функции соединения компонентных автоматов ; иначе (в терминах разбиений) .
Пусть . Образуем множество , такое, что . Таким образом, в попадают только те векторы из , у которых пересечение всех компонентов не пусто. Такое пересечение имеет место, так как компоненты блоки разбиений, т.е. множества.
Функция реализует отображение . Значение определим следующим образом:
т.е. значение функции равно тому блоку разбиения , в который входит пересечение компонентов .
На множестве функция не определена.
-
Определим множество входных функций следующим образом:
т. е. значение функции на равно блоку разбиения , содержащему . Отсюда ясно, что автомат не различают тех букв входного алфавита , которые входят в один блок разбиения .
-
Построим выходную функцию сети , иначе (в терминах разбиений) .
Пусть . Образуем множество , такое, что . Таким образом, в попадают только те векторы из , у которых пересечение всех компонентов не пусто.
Функция реализует отображение . Значение определим следующим образом:
т. е. значение выходной функции сети совпадает со значением функции выхода декомпозируемого автомата на паре , где состояние, попавшее в пересечение компонентов вектора .
На множестве функция не определена.
В работе [ссылка] показано, что построенная таким образом сеть реализует исходный автомат .
Разбиения и однозначно определяется разбиением ; показывает, какие автоматы воздействуют на автомат , а определяет классы неразличимых автоматом букв входного алфавита .
Таким образом, характеристическая тройка автомата . Стоит отметить, что и являются наибольшими разбиениями, причем, чем больше , тем меньше выходов других автоматов воздействует на . Чем больше , тем проще зависимость от внешнего входа . Использование разбиений и при построении является, таким образом, необходимым условием для построения сети наименьшей сложности.
На рисунке 1.2 представлена общая схема алгоритма декомпозиции вероятностного автомата.
Рисунок 1.2 Общая схема алгоритма декомпозиции.
1.8.6Выбор ортогонального множества разбиений.
Из конструктивного способа построения сети видно, что структура сети определена в общем случае не однозначно, поскольку неравенство , которое определяет автоматы , влияющие на поведение , может быть выполнено при различных совокупностях разбиений из , где последнее является ортогональным множеством разбиений (т.е. ).
Как было показано выше, от выбора ортогонального множества разбиений зависит структура и состав результирующей сети .
Выбор данного множества должен быть осуществлён до начала декомпозиции автомата. Так как имеется однозначное соответствие между этим выбором и результирующей сетью, то в зависимости от целей декомпозиции можно ввести критерий выбора (оценки) конкретного множества, который позволит получить результат, наиболее полно удовлетворяющий этим целям.
Например, из всех возможных вариантов декомпозиции особый интерес представляют случаи, при которых распределение состояний по подавтоматам сети наиболее равномерно.
Рассмотренный выше критерий даёт количественную оценку каждому множеству ортогональных разбиений (в процентах):
,
где число элементов во множестве ортогональных разбиений, число элементов во множестве состояний исходного автомата, количество элементов в ом блоке, оцениваемого разбиения, количество блоков, оцениваемого разбиения, количество блоков ого разбиения.
Данный критерий даёт тем большую оценку, чем больше разбиение соответствует ему.
|
