DFA minimization in F#

Question

I'm completely new to functional programming and have elected to use F# for a project which entails the parsing and minimization of a DFA.

I currently have my parser completed and am able to format each element of the DFA's tuple (states, alphabet, transition function, start state, final states) in whatever way I'd like and I have reached the point where I need to implement the minimization algorithm. The algorithm being used is:

For some DFA (Q, Σ, δ, S, F) where
Q: The set of states
Σ: The alphabet
δ: The transition function
S: The start state
F: The set of final states

Step 1. For each pair of states 
    (p, q) ∈ Q x Q
    If p ∈ F and q ∉ F (or vice versa), then set distinct(p, q) = 1.

Step 2. Loop until there is no change in the table contents:
    For each pair of states (p, q) ∈ Q x Q:
    For each alphabet symbol a ∈ alphabet:
    If distinct(p, q) = 0 and distinct(δ(p, a), δ(q, a)) = 1, then set    
    distinct(p, q) = 1.

I have the DFA tuple elements formatted like so:

States:

["0";"1";"2";"3"]

Alphabet:

["a";"b"]

Transition Function (ie: ["0";"a";"1"] is read as "0 on an 'a' goes to 1"]

[["0";"a";"1"];["1";"a";"1"];["1";"b";"2"];["2";"a";"0"];...;["5";"a";"4"]

Start State:

["0"]

Final States:

["1";"5"]

I also have have a distinct table formatted. It's basically the Cartesian product of States x States (QxQ from the above minimization algorithm) with any repeated products and duplicate elements ignored:

[["0";"1"];["0";"2"];["0";"3"];["0";"4"];["0";"5"];["1";"2"];
 ["1";"3"];["1";"4"];["1";"5"];["2";"3"];["2";"4"];["2";"5"];
 ["3";"4"];["3";"5"];["4";"5"]]

My initial strategy was to make a new list with only pairs which are either both non-final, or both final. (The only two conditions failing the 'Step 1' condition).

My problem is this: I am having a difficult time coming up with a way to compare the resulting list to the transition function of each pair of states. For example, take the pair of states ["1";"5"]. As the algorithm states, we must compare what happens to '1' for each alphabet character to what happens to '5' for each alphabet character. In this case, the transition function states:

For 1:

["1";"a";"1"];["1";"b";"2"]

-'1' on an 'a' goes to '1'

-'1' on a 'b' goes to '2'

And for 5:

["5";"a";"4"]

-'5' on an 'a' goes to '4'

Because both states, '5' and '1', behave differently when passed the same alphabet character, they are distinct. But, as I've stated, I'm not at all clear as to how to implement this comparison.

Any help would be greatly appreciated. Take care!

Answer 1

If your transition function is stored as triples as you show above:

• Sort them into separate lists of state pairs according to letter
• Make a random access array (or associative map) out of each such list

Since you are inverting the transition function, the index/key of each mapping will be the destination state, and the contents/value will be a list of zero or more origin states that the letter maps to it.

Make sure that all elements of your "distinct" list have their first element less than their second (by swapping the two if necessary), and make sure the list itself is sorted. Then, for each array or map:

• Apply the mapping to your "distinct" list as follows:
  • look up both elements of each "distinct" pair
  • perform the cartesian product of the two "origin state" lists from a given pair
  • combine the resulting pairs from all cartesian products into a single list
• For this new list:
  • Filter out any resulting tuples with identical elements
  • Swap any tuples whose first element is greater than the second
  • Sort the result
  • Eliminate neighboring duplicates
• Do a merge pass with the "distinct" list: