Автомат Вероятностный

обобщение автомата конечного, в к-ром функции переходов и выходов являются случайными функциями. Другими словами, А. В. Может быть задан системой где А, S, В - конечные алфавиты, имеющие тот же смысл, что и в конечном автомате, а - случайные функции, отображающие соответственно в и задаваемые системами вероятностных мер определенных для любых аиз А и s из S, соответственно, на множествах Sи В. Эти меры обычно задаются с помощью стохастич. Матриц (см. Автоматов способы задания). В том случае, когда эта вероятностная мера принимает только два значения 0 и 1, понятие А. В. Фактически совпадает с понятием детерминированного автомата. Автономные А. В. Без выхода по существу эквивалентны дискретным цепям Маркова.

Функционирование А. В. Определяется аналогично функционированию недетерминированного автомата, причем начальное состояние определяется путем задания вероятностной меры s на множестве S. Если А. В. Находится с нек-рой вероятностью рв состоянии и воспринимает входную букву а, то с вероятностью он переходит в состояние и выдает букву bвыходного алфавита. Подобно конечным автоматам, А. В. По характеру поведения разделяются на преобразователи и акцепторы. В первом случае, в соответствии с функционированием, А. В. Преобразует входные слова с нек-рыми вероятностями в выходные слова и в слова в алфавите состояний. Эти вероятности для слов одинаковой длины образуют вероятностную меру, так что указанное поведение можно рассматривать как задание счетной системы таких мер.

Во втором случае задается подмножество заключительных состояний и число из отрезка [0,1], называемое точкой сечения. Событие, предста-вимое вероятностным акцептором где - случайная функция, отображающая в S и задаваемая системой вероятностных мер определенных на S, состоит из всех слов в алфавите А, под действием к-рых автомат переходит в одно из заключительных состояний с вероятностью, не меньшей В отличие от конечных атоматов, при помощи А. В. Представим континуальный класс событий. Более того, уже один А. В. При варьировании может представлять континуальный класс событий. В случае же однобуквенного входного алфавита каждый А. В. Представляет лишь счетный класс событий, содержащий, вообще говоря, и нерегулярные события.

Для специальных точек сечения, наз. Изолированными, А. В. Представляют лишь регулярные события. Число из отрезка [0,1] наз. Изолированной точкой сечения для данного А. В., если существует такое положительное число , что для любого входного слова вероятность перевода А. В. Этим словом в заключительное состояние отличается от не менее чем на . Большая часть понятий и задач, характерных для конечных автоматов, в различных вариантах может быть распространена и на А. В. При этом многие из них сохраняют свойства, присущие конечным автоматам. Напр., можно ввести понятие эквивалентности состояний так, что будет сохранена известная теорема об отличимости состояний простым экспериментом (см. Эксперименты с автоматами). Вместе с тем в отличие от конечных автоматов, для к-рых минимальная форма определяется однозначно (с точностью до изоморфизма), для данного А.

В. Может существовать континуум эквивалентных минимальных А. В. Существуют различные виды и способы задания А. В. Напр., А. В. Может быть представлен в виде детерминированного автомата с двумя входами, на один из к-рых поступает случайная последовательность входных букв. А. В. Являются математич. Моделями многих реальных устройств и используются при изучении поведения организмов. Лит.:[1] Бухара ев Р. Г., Вероятностные автоматы, Казань, 1970. [2] Starke P., Abstrakte Automaten, В., 1969. В. Б. Кудрявцев, Ю. И. Янов.