Automate probabiliste
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. Une extension conduit aux automates quantiques. Un automate probabiliste est formé d'un automate fini non déterministe, où de plus chaque transition est équipée d'une probabilité, c'est-à-dire d'un nombre réel entre 0 et 1 vérifiant une certaine condition de cohérence. Comme pour une automate fini (non déterministe) usuel, une automate probabiliste sur un alphabet est composé des données suivantes : un ensemble fini d'états, noté ; un état initial , élément de ; un ensemble d'états terminaux ou finals ; un ensemble de transitions. De plus, chaque transition de porte un nombre réel positif , appelé sa probabilité, avec la condition que, pour chaque état et chaque lettre , la somme des , pour dans , est égal à 1. Cette condition s'exprime plus simplement en posant si n'est pas une transition. Alors elle revient à : pour tout état et toute lettre . On définit une -matrice pour chaque lettre , par La condition sur la distribution des probabilités s'exprime alors par la condition que les matrices P(a) sont de matrices stochastiques. On étend la fonction aux mots comme suit: Soit un mot, et soit un chemin de à d'étiquette . La probabilité de ce chemin est le produit des probabilités des transitions qui le composent. La probabilité est défini comme la somme des probabilités des chemins de à d'étiquette .