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

Автомат вероятностный – обобщение автомата конечного, в котором функции переходов и выходов являются случайными функциями. Другими словами, А. в. может быть задан системой (A,S,B,φ,ψ), где A,S,B – конечные алфавиты, имеющие тот же смысл, что и в конечном автомате, а φ,ψ – случайные функции, отображающие S x A соответственно в S и B и задаваемые системами вероятностных мер φ_s,_a,ψ_s,_a определенных для любых a из A и s из S, соответственно, на множествах S и B. Эти меры обычно задаются с помощью стохастических матриц (см. Автоматов способы задания ). В том случае, когда эта вероятностная мера принимает только два значения 0 и 1, понятие А. в. фактически совпадает с понятием детерминированного автомата. Автономные А. в. без выхода по существу эквивалентны дискретным цепям Маркова. Функционирование А. в. определяется аналогично функционированию недетерминированного автомата, причем начальное состояние определяется путем задания вероятностной меры σ на множестве S. Если А. в. находится с некоторой вероятностью p в состоянии s и воспринимает входную букву a, то с вероятностью p• ω(s,a,s′,b) он переходит в состояние s′ и выдает букву b выходного алфавита.

Подобно конечным автоматам, А. в. по характеру поведения разделяются на преобразователи и акцепторы. В первом случае, в соответствии с функционированием, А. в. преобразует входные слова с некоторыми вероятностями в выходные слова и в слова в алфавите состояний. Эти вероятности для слов одинаковой длины образуют вероятностную меру, так что указанное поведение можно рассматривать как задание счетной системы таких мер. Во втором случае задается подмножество заключительных состояний и число λ из отрезка [0,1], называемое точкой сечения. Событие, представимое вероятностным акцептором Aσ = (A,S,φ,S′,λ), где φ – случайная функция, отображающая SxA в S и задаваемая системой вероятностных мер φ_s,_a, определенных на S, состоит из всех слов в алфавите A, под действием которых автомат переходит в одно из заключительных состояний с вероятностью, не меньшей λ. В отличие от конечных автоматов, при помощи А. в. представим континуальный класс событий. Более того, уже один А. в. при варьировании может представлять континуальный класс событий. В случае же однобуквенного входного алфавита каждый А. в. представляет лишь счетный класс событий, содержащий, вообще говоря, и нерегулярные события. Для специальных точек сечения, называемых изолированными, А. в. представляют лишь регулярные события. Число λ из отрезка [0,1] называют изолированной точкой сечения для данного А. в., если существует такое положительное число δ, что для любого входного слова вероятность перевода А. в. этим словом в заключительное состояние отличается от λ не менее чем на δ.

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

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

Рекомендуемая литература

Бухараев Р. Г., Вероятностыне автоматы, Казань, 1970;

Starke P., Abstrakte Automaten, В., 1969..