As the question implies, can you mention any difference between Hidden Markov Model and Non-deterministic Finite-State Machine? Are they different or the same?
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 "in between" 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 & 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., "if the weather is cloudy then 20% it will turn rainy / 80% it will turn sunny".