Что такое вероятностный автомат? Душкин объяснит

• Роман Душкин объясняет теорию формальных автоматов, в частности, вероятностные автоматы.  

• Вероятностные автоматы являются недетерминированными автоматами, но они рассматриваются для понимания их работы.  

• Функция перехода для вероятностного автомата возвращает множество состояний, а не одно состояние, как для детерминированного автомата.  

• Вероятность перехода между состояниями равна 1/4, 1/6 или другому значению, в зависимости от количества возможных переходов.  

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

• Вероятностные автоматы облегчают жизнь, но не усиливают вычислительную модель.  

• Вероятностные автоматы полностью погружены в класс недетерминированных автоматов.  

• Вероятностные автоматы полезны для решения задач, но не привносят новой силы в вычислительную модель.