What is difference between Hidden Markov Model and Non-deterministic Finite-State Machine?
Deterministic Finite State Machines have at most one trace for a given input. Nondeterministic Finite State Machines may have many traces for a given input. A Hidden Markov Model in some sense fits &quot;in between&quot; these extremes as the traces are probabilistic. With a Hidden Markov Model we do not have complete freedom to choose which trace to follow as we are governed by probabilities. A Hidden Markov Model is essentially a transducer-style Finite State Machine having outputs &amp; transitions governed by a random process; the outputs generated at states are per a random variable model of what happens at that state, e.g., &quot;if the weather is cloudy then 20% it will turn rainy / 80% it will turn sunny&quot;.