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

обобщение автомата конечного, в к-ром функции переходов и выходов являются случайными функциями. Другими словами, А. в. может быть задан системой [img: http://localhost:8080/file/010104-68.jpg] где А, S, В - конечные алфавиты, имеющие тот же смысл, что и в конечном автомате, а [img: http://localhost:8080/file/010104-69.jpg] - случайные функции, отображающие [img: http://localhost:8080/file/010104-70.jpg] соответственно в [img: http://localhost:8080/file/010104-71.jpg] и задаваемые системами вероятностных мер [img: http://localhost:8080/file/010104-72.jpg] определенных для любых аиз А и s из S, соответственно, на множествах Sи В. Эти меры обычно задаются с помощью стохастич. матриц (см. Автоматов способы задания). В том случае, когда эта вероятностная мера принимает только два значения 0 и 1, понятие А. в. фактически совпадает с понятием детерминированного автомата. Автономные А. в. без выхода по существу эквивалентны дискретным цепям Маркова. Функционирование А. в. определяется аналогично функционированию недетерминированного автомата, причем начальное состояние определяется путем задания вероятностной меры s на множестве S. Если А. в. находится с нек-рой вероятностью рв состоянии [img: http://localhost:8080/file/010104-73.jpg] и воспринимает входную букву а, то с вероятностью [img: http://localhost:8080/file/010104-74.jpg] он переходит в состояние [img: http://localhost:8080/file/010104-75.jpg] и выдает букву bвыходного алфавита. Подобно конечным автоматам, А. в. по характеру поведения разделяются на преобразователи и акцепторы. В первом случае, в соответствии с функционированием, А. в. преобразует входные слова с нек-рыми вероятностями в выходные слова и в слова в алфавите состояний. Эти вероятности для слов одинаковой длины образуют вероятностную меру, так что указанное поведение можно рассматривать как задание счетной системы таких мер. Во втором случае задается подмножество [img: http://localhost:8080/file/010104-76.jpg] заключительных состояний и число [img: http://localhost:8080/file/010104-77.jpg] из отрезка [0,1], называемое точкой сечения. Событие, предста-вимое вероятностным акцептором [img: http://localhost:8080/file/010104-78.jpg] где [img: http://localhost:8080/file/010104-79.jpg] - случайная функция, отображающая [img: http://localhost:8080/file/010104-80.jpg] в S и задаваемая системой вероятностных мер [img: http://localhost:8080/file/010104-81.jpg] определенных на S, состоит из всех слов в алфавите А, под действием к-рых автомат переходит в одно из заключительных состояний с вероятностью, не меньшей [img: http://localhost:8080/file/010104-82.jpg] В отличие от конечных атоматов, при помощи А. в. представим континуальный класс событий. Более того, уже один А. в. при варьировании [img: http://localhost:8080/file/010104-83.jpg] может представлять континуальный класс событий. В случае же однобуквенного входного алфавита каждый А. в. представляет лишь счетный класс событий, содержащий, вообще говоря, и нерегулярные события. Для специальных точек сечения, наз. изолированными, А. в. представляют лишь регулярные события. Число [img: http://localhost:8080/file/010104-84.jpg] из отрезка [0,1] наз. изолированной точкой сечения для данного А. в., если существует такое положительное число [img: http://localhost:8080/file/010104-85.jpg], что для любого входного слова вероятность перевода А. в. этим словом в заключительное состояние отличается от [img: http://localhost:8080/file/010104-86.jpg] не менее чем на [img: http://localhost:8080/file/010104-87.jpg]. Большая часть понятий и задач, характерных для конечных автоматов, в различных вариантах может быть распространена и на А. в. При этом многие из них сохраняют свойства, присущие конечным автоматам. Напр., можно ввести понятие эквивалентности состояний так, что будет сохранена известная теорема об отличимости состояний простым экспериментом (см. Эксперименты с автоматами). Вместе с тем в отличие от конечных автоматов, для к-рых минимальная форма определяется однозначно (с точностью до изоморфизма), для данного А. в. может существовать континуум эквивалентных минимальных А. в. Существуют различные виды и способы задания А. в. Напр., А. в. может быть представлен в виде детерминированного автомата с двумя входами, на один из к-рых поступает случайная последовательность входных букв. А. в. являются математич. моделями многих реальных устройств и используются при изучении поведения организмов.