Automate probabiliste
De Wikipedia, l'encyclopédie encyclopedia
En mathématiques et en informatique théorique, et notamment en théorie des automates, un automate probabiliste est une généralisation des automates finis non déterministes; chaque transition de l'automate est équipée d'une probabilité (un nombre réel entre 0 et 1). Les transitions sont représentées de manière compacte par des matrices qui sont des matrices stochastiques. Les langages reconnus par les automates probabilistes sont appelés langages stochastiques; ils comprennent, et étendent, la famille des langages rationnels. En particulier, le nombre de langages stochastiques est non dénombrable (alors que celui des langages rationnels est dénombrables).
Le concept d'automate probabiliste a été introduit par Michael O. Rabin en 1963[1],[2],[3]. Une extension conduit aux automates quantiques.