The complexity properties of probabilistic automata with isolated cut point

AbstractA probabilistic automaton (PA) which accepts a language with e-isolated cut point 12 corresponds to a PA which computes with (12−e) bounded error probability. Let P(L, e) be the minimal number of states of a PA necessary for accepting a language L with e-isolated cut point 12. It is shown that there are languages Lk, 1 < k < ∞ and an infinite sequence of numbers 0 < e1 < e2 < … < 12 such that for all i ⩾1, P(Lk,ei)P(Lk, ei+1) → 0 when k→∞. It is also shown that the probabilistic recognition of the language Wk is more effective than that of the Lk