##Simplify a DFA
Understanding and simplifying a formal language can be difficult. Doing it for a visual representation of that language is a well-understood phenomenon for "regular languages" (RegEx anyone?).
Your task is: Given a Deterministic Finite State Automaton, find the simplest representation of that automaton.
An automaton is formally defined as a 5-Tuple \$M = (S, \Sigma, \delta, s_0, F)\$
\$S\$ contains a Set of all possible States the automaton has.
\$\Sigma\$ defines the alphabet that the Automaton works on. For all intents and purposes here this is the standard ASCII alphabet.
\$\delta\$ is the "transition function" more on that later.
\$s_0\$ is the starting state for the automaton.
\$F\$ is a subset of \$S\$ and describes all Statesstates that are valid terminations for the Automaton.
###How it works
\$\delta\$ defines the transitions between the states. Say our word begins with an a. The automaton inputs it's current state (\$s_0\$) and the read character (a) as arguments to \$\delta\$ and the result of this function "call" is the state that the automaton has next.
If there is no such state, the automaton terminates with the result that the input is not contained in the language.
Otherwise the automaton reads the next character in the input and checks again. If (and only if) the automaton reaches a "terminating state" when the last character from the input is read, the input is in the language described by the automaton.
It kinda looks like this in java-ish pseudocode:
currentState = start;
for each (character in input)
currentState = delta(currentState, character);
if currentState is empty: return false;
end for
return currentState is in terminatingStates;
###The##The goal
The goal of simplifying a DFA is to reduce the number of States it has to a minimum.
###How to minimize the number of states
The standard algorithm taught in CS-Theory classes works as follows:
Create a list of all pairs of states. The order of states in a pair does not matter. (Iow. \$(s_0, s_1) = (s_1, s_0)\$
Mark all pairs where at least one component is a terminating state.
While you mark new pairs do:
Check all non-marked pairs for each symbol in your alphabet for the following condition:
if the pair delta(currentPair[0], symbol) and delta(currentPair[1], symbol) is marked: mark currentPair break for
After you stopped marking pairs, you can merge all non-marked pairs, where each pair of states gets a new state.
As you can see, this algorithm is basically \$O(2^nm)\$ where \$n\$ is the number of states and \$m\$ the number of different symbols in your alphabet.