АВТОМАТ ВЕРОЯТНОСТНЫЙ

— дискретный стационарный потактный преобразователь информации с памятью, функционирование которого в каждом такте зависит только от состояния памяти в нем и может быть опвдано статистически. Свойства А. в., как входного — выходного преобразователя, изучаются на такой модели. Пусть X, У, Q — конечные или счетные множества входных и выходных букв и состояний А. в. соответственно. Тогда на декартовом произведении множеств определено условное вероятностное распределение заданное на каждом элементе декартова произведения множеств . А. в. обозначается как . функционирование А. в. состоит в том, что в дискретные моменты времени на вход устр-ва подается последовательность букв входного алфавита X. При условии, что А. в. находится в состоянии и на вход подана буква , автомат переходит в следующее состояние и выдает букву с вероятностью . В первом такте фиксировано начальное состояние А. в. или начальное распределение вероятностей состояний. Для теории А. в. существенно то, как именно сказывается закон функционирования, определенный выше для А. в. как однотактного преобразователя информации, на законе его функционирования «в целом» как многотактного устр-ва, определяющего преобразования последовательностей входных букв в последовательности выходных букв с тем же числом букв. Свойства А. в. как идентификатора событий изучаются на модели А. в., выход которого не рассматривается. Тогда на множестве состояний Q определяется условное распределение вероятностей заданное на каждом элементе декартова произведения множеств Пусть — подмн-во и — распределение вероятностей начальных состояний. А. в. наз. объект Функционирование такого А. в. определяется почти аналогично, с той только разницей, что условное вероятностное распределение определяет переходы лишь для его состояний. А. в. наз. конечным, если конечны мн-ва X, У, Q. Пусть — число состояний А. в. Тогда рассматривают А. в. и как систему -матриц с неотрицательными элементами вида , где элементы матриц определены как или, во втором случае, как систему стохастических , где элементы матриц определены как Удобно рассматривать распределение вероятностей в векторной форме. Тогда формально функционирование А. в. можно описать матрицей преобразования Обозначим слово, подаваемое на вход А. в., . Пусть — вектор, составленный из вероятностей начальных состояний А. в. Тогда вектор вероятностей конечных состояний А. в. имеет вид ) где соответствующая матрица.

Одна из осн. задач теории А. описание класса событий, представимых в конечных А. в. Пусть пр, где координаты вектора-столбца пр равны единице для номеров соответствующих состояниям из F и нулю — для остальных номеров. Пусть мн-во всех слов в алфавите X. Говорят, что событие S представлено в А. в. начальным вектором состояний ,

множеством отмеченных состояний F и точкой сечения если любое слово из тогда и только тогда принадлежит S, если выполнено следующее условие: Класс представимых событий является континуальным множеством. Представимое событие Т характеризуется тем, что определяет в пространстве L числовых последовательностей сумма которых сходится абсолютно к единице, некоторую линейную эквивалентность так, что фактор-пространство по этой эквивалентности оказывается конечномерным. Существуют примеры нерегулярных представимых событий и примеры непредставимых событий, являющихся, однако, примитивно-рекурсивными мн-вами. Доказано, что класс представимых в конечных А. в. событий совпадает с классом событий, представимых в конечных автоматах линейных. Для учета реальных возможностей статистич. эксперимента по распознаванию принадлежности данного слова представляемому событию приходится вводить понятие изолированной точки сечения к относительно автомата А как числа, удовлетворяющего условию

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

Задача устойчивости А. в. состоит в характеристике класса А. в., которые при достаточно малых возмущениях переходных вероятностей и фиксированной точке сечения представляют одно и то же событие. Класс конечных А. в., все переходные вероятности которых строго положительны, является устойчивым относительно изолированной точки сечения.

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

Для распознавания эквивалентности пары состояний одного А. в. достаточно диагн. простого эксперимента длины для различных А. в. - длины , где числа состояний соответствующих автоматов. Два А. в. эквивалентны, если для каждого состояния одного из них найдется эквивалентное ему состояние другого.

Пусть А. в. состояниями имеет пару эквивалентных состояний Система матриц полученная из системы матриц вычеркиванием строки и столбца и заменой столбца на сумму столбцов определяет А. в. состоянием, эквивалентный данному. В отличие от теории детерминированных автоматов мн-во миним.

A. в., эквивалентных данному, вообще говоря, континуально.

А. в. А гомоморфен А. в. В, если существует такая прямоугольная матрица полного ранга Н, что где — допустимые мн-ва векторов состояний соответствующих автоматов. Из гомоморфизма следует, что это — эквивалентные автоматы. Из эквивалентности А и В вытекает существование псевдо-вероятностного автомата С, которому гомоморфны А и В, т. е. автомата, формально определяемого как вероятностный, но переходные вероятности могут принимать отрицательные значения. Можно отметить результат, что А. в. А эквивалентен детерминированному автомату на входе которого установлен генератор случайных кодов, управляемый последовательностью входных букв А. Структурная теория А. в. развита пока недостаточно.

Методы теории А. в. опираются на свойства стохастических матриц, матриц с неотрицательными элементами и определяемых этими матрицами линейных преобразований. Существенное значение имеют также чисто автоматные методы, поскольку формально А. это линейный преобразователь распределений вероятностей на мн-ве Q, т. е. линейный автомат с бесконечным числом состояний

Изучение А. в. имеет важное значение для разработки методов анализа дискретных устр-в, проявляющих статистически закономерное случайное поведение, выяснения функциональных возможностей таких устр-в и обоснования границ целесообразности их использования, а также для решения задач синтеза устр-в, удовлетворяющих заданной системе требований.

Лит.: Рабин М. О. Вероятностные автоматы. В кн.: Кибернетический сборник, № 9. М., 1964; Карлайл И. В. Приведенные формы для стохастических последовательных машин. В кн.: Кибернетический сборник. Новая серия, в. 2. М., 1966; Бухараев Р. Г. Вероятностные автоматы. Казань. 1970; Поспелов Д. А. Вероятностные автоматы. М., 1970 [бйблиогр. с. 84—87]; Starke Р. Н. Theorie stochastischeT Automaten. «Elektronische In-formationsverarbeitung und Kybernetik», 1965, Bd. 1, H. 1-2. P. Г. Бухараев.