§ 10.19. Стохастические конечные автоматы

Определенным обобщением детерминированных автоматов, о которых мы говорили выше, представляют собой стохастические автоматы. В стохастических автоматах мы можем говорить лишь о вероятностях перехода из одного состояния в другое. Уравнения такого стохастического автомата можно записать в такой форме:

                                                    (10.82)

В первом уравнении (10.82)  представляет собой случайную решетчатую функцию и, в частности, бернуллиеву, обладающую тем свойством, что вероятность появления той или иной дискреты фиксирована и не зависит от появления других дискрет.

Таким образом, в стохастическом автомате состояние зависит от случайной решетчатой функции , которая может изменять как «параметры» конечного автомата, так и представлять дополнительное к выходному случайное воздействие (рис. 10.10).

В этом последнем случае первое уравнение (10.82) примет более определенный вид

,                                                     (10.83)

где символ сложения  означает, что сумма  всегда принадлежит входному алфавиту.

Рис. 10.10

Обычно стохастический автомат определяют матрицей перехода

                             (10.84)

Она отличается от матрицы состояний (10.81) и тем, что в ней элементы  заменены переходными вероятностями , которые определяют вероятность перехода из -го состояния в -e. Естественно, что  должны удовлетворять условиям симплекса

                                    (10.85)

Стохастические автоматы охватывают детерминированные как частный случай при .