Language Recognition Using Probabilistic Turing Machines in Real Time, and Automata with a Push-Down Store

For each of the two classes of machines, the following result is obtained: There exists a language that can be recognized with probability $1-\varepsilon$ for any $\varepsilon>0$, but which cannot be recognized. deterministically.