How do you normalize a finite state machine?

Question

1. How do you find the minimal Deterministic FSM?
2. Is there a way to normalize non-deterministic FSMs?
3. Is there a linear time bound algorithm to find the minimal FSM for a given machine?
4. Is there a way to see if two FSMs are equivalent?

This is not a homework question. I was watching this lecture series and just got curious.

Answer 1

As all nondeterministic FSM have a coresponding deterministic FSM, the answer to to 1 and 2 should be the same.

If you want to know more, get a copy "Introduction to the Theory of Computation" by Michael Sipser, which is a really great book to learn these things. Sipser knows what he talks about and how to communicate it very well.

Answer 2

Check "Basics of Compiler Design" starting at section 2.5. Available for free online. http://www.diku.dk/hjemmesider/ansatte/torbenm/Basics/basics%5Flulu.pdf

It covers converting a NFA to a DFA and minimizing the DFA. NFAs can expand exponentially when converted to DFAs.

"... any regular language (a language that can be expressed by a regular expression, NFA or DFA) has a unique minimal DFA. Hence, we can decide equivalence of regular expressions (or NFAs or DFAs) by converting both to minimal DFAs and compare the results."

Answer 3

Some informal answers to give you the ideas, for detailed proofs read a good book on Automata, for example this one or the ones mentioned in the other answers. And I am pretty sure there are online materials you could find answering all of your questions.

• How do you find the minimal Deterministic FSM?

The procedure is to eliminate duplicated states (or to merge equivalent states). You know that state and transitions are the keys to generate strings. Basically, duplicated states do not contribute in making the language generated any larger or less. The algorithm starts from final states that always have the ability of generating the lamda (empty string), and recursively update a table which indicate the generating ability of a state, and finally merge those states making no difference.

• Is there a way to normalize non-deterministic FSMs?

The normalized DFA for the NFA is using different collections of the states of NFA as DFA's states, for example, {state0} -(1)-> {state1, state2} to remove the non-deterministic part, there is no way to avoid the state explosion as DFA has to do that to represent the language.

• Is there a linear time bound algorithm to find the minimal FSM for a given machine?

I remember the best one is O(NLogN) by doing some tricks of reusing information in some paper by a Western Ontario University Professor, and doubt there exists better ones. I believe the classical one is O(N^2).

• Is there a way to see if two FSMs are equivalent?

Yes. Get the minimal one, code the state by their accessing string (a string that could reach the state from the start state, this is pretty much the real "name" of a state there), and verify the transition map. There might be better ways though, but there would be no big difference on the bigO.

Answer 4

• If you are given some deterministic FSM, then you can find an equivalent, minimal one using a quite easy algorithm in O(n²); Hopcroft's algorithm does it in O(n log n). Here you'll find description of both. You can check if A and B are equivalent by minimizing them and checking if they are the same.
• If you are given some nondeterministic FSM, then finding an equivalent, minimal one is PSPACE-complete. In other words, no good algorithm is known and is conjectured that it doesn't exist. Checking equivalence of two nondeterministic automatas is PSPACE-complete too. So, unless there will be a very improbable breakthrough, you should convert the automaton to a deterministic one (this takes much time) and then perform checks.
• You can transform a nondeterministic FSM to a deterministic one with exponential number of states. This is unavoidable. Exercise (not hard!): the language consisting of words in which the n-th letter from the end is "a" can be recognized using a nondeterministic FSM with n states, and it cannot be recognized using a deterministic FSM with less than 2ⁿ states. Exponential bound cannot be broken in general case.