A simple result is presented that links the learning of hidden Markov models to results in complexity theory about nonlearnability
of finite automata under certain cryptographic assumptions. Rather than considering all probability distributions, or even
just certain specific ones, the learning of a hidden Markov model takes place under a distribution induced by the model itself.
Keywords Pac-learning - hidden Markov models - complexity
Supported by a Marie Curie fellowship of the European Union under grant no. ERB-FMBI-CT98-3248. Most of this research was
done while the author was working at the University of Munich.