Анализ вероятностного автомата.
Исходные данные - некоторая схема вероятностного автомата.
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; просмотров: 730;