Анализ вероятностного автомата.

Исходные данные - некоторая схема вероятностного автомата.

2 этапаанализа:

1) Составить таблицу переходов, уточнив входные буквы, выходные буквы и т.д.

2) Известна таблица переходов, таблица выходов неизвестна. Найти вероятности появления выходных букв.

 

Пример: В качестве вероятностного автомата возьмем триггер RS типа.

Как было раньше установлено, на входы этого триггера нельзя одновременно подавать единицы, так как он переходит в неявное состояние. Но для вероятностных автоматов подавать такие входные сигналы можно. Схема - источник случайной двоичной последовательности.

Составим таблицы переходов.

Сперва определяем, какие входные и какие выходные данные:

Следовательно, имеем 4 таблицы переходов:

 

(имеем симметричный триггер)

Это одношаговые таблицы переходов.

Qi— состояние автомата.

Примечание: на самом деле оба плеча триггера не одинаковы, что приводит к тому, что на практике вероятность перехода отличается от 1/2.

 

Вероятности появления выходных букв.

Для нахождения вероятности появления выходных букв используется уравнения Маркова, уравнения Колмогорова Чепмена и формулы полной вероятности. Смотри курс лекций по теории вероятности.

Общая методика анализа вероятностного автомата состоит в следующем:

1. Исходными данными для анализа является вектор

начального состояния ВА P(a0), Р(а1), Р(a2), ... , Р (аm); t=0

Матрица переходов за один шаг для каждой входной буквы.

Таблица вероятности выходных букв.

2. Нахождение матрицы переходов за п шагов, например:

В общем случае, если на вход автомата поступает одна буква, то можно воспользоваться уравнением Колмогорова - Чепмена:

3. Нахождение вероятностей состояний ВА:

Сначала воспользуемся уравнениями Маркова для нахождения условных вероятностей состояний

Затем находим абсолютную вероятность состояний по формуле полной вероятности:

4. Нахождение вероятностей выходных букв yi для разных случаев: a) Y - детерминированный автомат Мура

б) Просто ВА Мура по формуле полной вероятности:

в) Сложный случай - ВА Мили:

Примечание: в случае, если состояние автомата и входная буква независимы, то

 








Дата добавления: 2016-02-09; просмотров: 721;


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.008 сек.