<p><a href="http://www.sciencedirect.com/science/article/pii/S0019995863902900" rel="nofollow">The first paper</a> by Rabin (1963) gives the basics what you are looking for. The class of languages recognized by probabilistic automata (with cutpoint) is called stochastic languages. </p>

<p>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:</p>

<blockquote>
  <p>$ L(P,\lambda) = \{ w \in \Sigma^* \mid f_P(w) &gt; \lambda \}  $.</p>
</blockquote>

<p>Remark that the recognition with cutpoint can be seen as recognition with unbounded error. In case of bounded-error (or isolated cutpoint) probabilistic automata can recognize all and only regular languages.</p>

<p><a href="https://books.google.com.tr/books?id=ILviBQAAQBAJ&amp;pg=PR1&amp;lpg=PR1&amp;dq=azaria%20paz%201971&amp;source=bl&amp;ots=kKRvF-fAHW&amp;sig=ooFp9HxYRsU59UzF44bwoIslkbk&amp;hl=en&amp;sa=X&amp;ved=0ahUKEwjo54D83oXMAhXGPxQKHVnZBSIQ6AEIMjAE#v=onepage&amp;q=azaria%20paz%201971&amp;f=false" rel="nofollow">The book</a> by Paz (1971) and <a href="http://link.springer.com/article/10.1007%2FBF01088986" rel="nofollow">the survey</a> by Bukharaev (1980) are good references.</p>

<p>You can also check a recent <a href="http://arxiv.org/abs/1507.01988" rel="nofollow">survey on quantum automata</a> where you can trace some references on probabilistic automata.</p>

CC BY-SA 3.0
2016-04-11T04:41:24.377Z
2016-04-11T10:55:50.600Z
2016-04-11T10:55:50.600Z
Abuzer Yakaryilmaz
<p>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?</p>

<p>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.</p>

<p><a href="http://wwwhome.ewi.utwente.nl/~marielle/papers/pa.pdf">This</a> and <a href="http://www.win.tue.nl/~evink/research/Postscript/voss04.pdf">this</a> don't quite seem to be what I'm looking for.</p>

CC BY-SA 3.0
2016-04-29T12:15:22.443Z
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: http://eccc.hpi-web.de/report/2013/040/.
Michaël Cadilhac
<reference-request><fl.formal-languages><probabilistic-automata>
Introduction to probabilistic automata
Prateek
# Introduction to probabilistic automata

(Asked by: username_0 on 2016-04-10)

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](http://wwwhome.ewi.utwente.nl/~marielle/papers/pa.pdf) and [this](http://www.win.tue.nl/~evink/research/Postscript/voss04.pdf) don't quite seem to be what I'm looking for.

**Tags:** reference-request, fl.formal-languages, probabilistic-automata

> **Comments:**
> **username_1**: 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: http://eccc.hpi-web.de/report/2013/040/.  

---

## 1 answers

### Answer by username_2 on 2016-04-11. Score: 9 | Accepted answer

[The first paper](http://www.sciencedirect.com/science/article/pii/S0019995863902900) by Rabin (1963) gives the basics what you are looking for. The class of languages recognized by probabilistic automata (with cutpoint) is called stochastic languages.

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 \} $.

Remark that the recognition with cutpoint can be seen as recognition with unbounded error. In case of bounded-error (or isolated cutpoint) probabilistic automata can recognize all and only regular languages.

[The book](https://books.google.com.tr/books?id=ILviBQAAQBAJ&pg=PR1&lpg=PR1&dq=azaria%20paz%201971&source=bl&ots=kKRvF-fAHW&sig=ooFp9HxYRsU59UzF44bwoIslkbk&hl=en&sa=X&ved=0ahUKEwjo54D83oXMAhXGPxQKHVnZBSIQ6AEIMjAE#v=onepage&q=azaria%20paz%201971&f=false) by Paz (1971) and [the survey](http://link.springer.com/article/10.1007%2FBF01088986) by Bukharaev (1980) are good references.

You can also check a recent [survey on quantum automata](http://arxiv.org/abs/1507.01988) where you can trace some references on probabilistic automata.


---

