АВТОМАТ ВЕРОЯТНОСТНЫЙ это:

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

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

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

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

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

Лит.:[1] Бухара ев Р. Г., Вероятностные автоматы, Казань, 1970; [2] Starke P., Abstrakte Automaten, В., 1969.

В. Б. Кудрявцев, Ю. И. Янов.


Математическая энциклопедия. — М.: Советская энциклопедия. . 1977—1985.

Смотреть что такое "АВТОМАТ ВЕРОЯТНОСТНЫЙ" в других словарях:

  • АВТОМАТ — управляющая система, являющаяся автоматом конечным или некоторой его модификацией, полученной путем изменения компонент или функционирования. Основное понятие конечный А. возникло в середине 20 в. в связи с попытками описать на математическом… …   Математическая энциклопедия

  • ВЕРОЯТНОСТНЫЙ АВТОМАТ — устройство (система), автоматически изменяющее свое состояние в зависимости от последовательности предыдущих состояний и случайных входных сигналов. Вероятностный автомат используют при моделировании сложных процессов, напр. систем… …   Большой Энциклопедический словарь

  • Вероятностный автомат — Вероятностный автомат  устройство или система, в которых переход из одного состояния в другое происходит в зависимости от случайных входных сигналов или в зависимости от последовательности предыдущих состояний. Вероятностный автомат в… …   Википедия

  • вероятностный автомат — устройство (система), автоматически изменяющее своё состояние в зависимости от последовательности предыдущих состояний и случайных входных сигналов. Вероятностный автомат используют при моделировании сложных процессов, например систем… …   Энциклопедический словарь

  • вероятностный автомат — tikimybinis automatas statusas T sritis automatika atitikmenys: angl. probabilistic automaton; stochastic automaton vok. probabilistischer Automat, m; stochastischer Automat, m; Wahrscheinlichkeitsautomat, m rus. вероятностный автомат, m;… …   Automatikos terminų žodynas

  • Вероятностный автомат —         система, в которой переход из одного состояния в другое происходит случайным образом. Вероятность этого перехода определяется последовательностью его предыдущих состояний (a1, a2,..., ai,..., an) и входными сигналами (S1, S2,..., Sm) и… …   Большая советская энциклопедия

  • ВЕРОЯТНОСТНЫЙ АВТОМАТ — устройство (система), автоматически изменяющая своё состояние в зависимости от последовательности предыдущих состояний и случайных входных сигналов. В. а. используют для моделирования сложных процессов, например автоматич. управления движением… …   Большой энциклопедический политехнический словарь

  • НЕДЕТЕРМИНИРОВАННЫЙ АВТОМАТ — автомат, у к рого предыдущее состояние и сигнал на входе ещё не определяют полностью последующего его состояния, а только обусловливают класс возможных состояний. Наиболее изученный случай Н. а. вероятностный автомат …   Большой энциклопедический политехнический словарь

  • стохастический автомат — tikimybinis automatas statusas T sritis automatika atitikmenys: angl. probabilistic automaton; stochastic automaton vok. probabilistischer Automat, m; stochastischer Automat, m; Wahrscheinlichkeitsautomat, m rus. вероятностный автомат, m;… …   Automatikos terminų žodynas

  • Детерминированный автомат —         математическая модель системы, состояния которой меняются в дискретные моменты времени, причём каждое состояние системы полностью определяется предыдущим состоянием и входным сигналом. Д. а. формально описывается в виде функции f (si, aj) …   Большая советская энциклопедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»