Вероятностный автомат
-
Определение вероятностного автомата
- Вероятностный автомат — это расширение недетерминированного конечного автомата с вероятностями вместо функций перехода.
- Он имеет набор состояний, входной алфавит, функцию перехода и начальное состояние, а также вектор распределения состояний.
-
Формальное определение
- Вероятностный автомат определяется как кортеж, состоящий из набора состояний, входного алфавита, вероятностных матриц, начального распределения и набора принимающих состояний.
-
Автомат Рабина
- Автомат Рабина имеет начальное распределение, которое является координатным вектором с единицей в одной позиции.
-
Стохастические языки
- Стохастические языки включают обычные языки и могут быть определены как языки, распознаваемые вероятностными автоматами.
- Язык называется η-стохастическим, если существует вероятностный автомат, распознающий его для заданного значения η.
-
Свойства стохастических языков
- Каждый обычный язык стохастичен и каждый обычный язык является η-стохастическим для некоторого η.
- Некоторые стохастические языки не являются регулярными, например, p-адические языки.
- Стохастические языки могут быть представлены автоматами Рабина.
-
Обобщения вероятностных автоматов
- Вероятностные автоматы могут быть обобщены до топологических автоматов, где состояния представлены точками в топологическом пространстве, а матрицы переходов — операторами, действующими в этом пространстве.
-
Примеры и рекомендации
- В статье приведены примеры вероятностных автоматов и их применение к стохастическим языкам.