# Introduction to probabilistic automata

Where can I find an introduction to probabilistic automata and what they recognize (certain functions from words to $[0,1]$)? Is there a standard term for such functions which are recognized by probabilistic automata, analogous to "regular languages" for what deterministic finite automata (DFAs) recognize?

I'm looking for something which approaches it analogously to studying basic questions on DFAs and regular languages, such as expressiveness, closure, and decidability properties.

This and this don't quite seem to be what I'm looking for.

• They are the "positive supports" of $\mathbb{Z}$-rational series, i.e., the languages $\{w \mid (r, w) > 0\}$ for $r$ such a series. This is not all too well behaved, though. I studied the Boolean closure of this class, if you are interested: eccc.hpi-web.de/report/2013/040. – Michaël Cadilhac Apr 29 '16 at 12:15

Let $P$ be a probabilistic automaton defined on the alphabet $\Sigma$ and $f_P(w)$ be the accepting probability of $P$ on the input $w \in \Sigma^*$. Then, $P$ with cutpoint $\lambda \in [0,1)$ defines the following language:
$L(P,\lambda) = \{ w \in \Sigma^* \mid f_P(w) > \lambda \}$.