LOWER BOUNDS FOR LAS VEGAS AUTOMATA BY INFORMATION THEORY

摘要

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 ≥ 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 to one-way Las Vegas communication protocols, but here we give a direct proof based on information theory.