We show that the size of a Las Vegas automaton and the size of a complete, minimal deterministic automaton accepting a regular language are polynomially related. More precisely, we show that if a regular language $L$ is accepted by a Las Vegas automaton having $r$ states such that the probability for a definite answer to occur is at least $p$, then $r\ge n^p$, where $n$ is the number of the states of the minimal deterministic automaton accepting $L$. Earlier this result has been obtained in [2] by using a reduction...

We show that the size of a Las Vegas automaton and the size of a complete, minimal deterministic automaton accepting a regular language are polynomially related. More precisely, we show that if a regular language L is accepted by a Las Vegas automaton having r states such that the probability for a definite answer to occur is at least p, then r ≥ np, where n is the number of the states of the minimal deterministic automaton accepting L. Earlier this result has been obtained in [2] by using a reduction...