NFA and DFA implementation
A quick look shows the only difference with your FiniteAutomaton types is that the transition either takes a string or string List.  So genericize it!

type FiniteAutomaton&lt;'a&gt; = {
    InitialState: string
    FinalStates: Set&lt;string&gt;
    Transitions: Map&lt;string * char, 'a&gt;
}
type DeterministicFiniteAutomaton = FiniteAutomaton&lt;string&gt;
type NondeterministicFiniteAutomaton = FiniteAutomaton&lt;string List&gt;


The rest pretty much falls in place:

let private nextState symbol state fa =
    fa.Transitions |&gt; Map.tryFind (state, symbol)

let rec private haltState (input:string) index state fa =
    match index with
    | i when i = input.Length -&gt; state
    | _ -&gt;
        match nextState input.[index] state fa with
        | None -&gt; null
        | Some state -&gt; haltState input (index+1) state fa

let accepts input fa =
    fa.FinalStates |&gt; Set.contains (haltState input 0 fa.InitialState fa)


I try to remove as much type annotations as possible.  Just let F#'s type inference do its magic. Also, it was convenient to pass around the fa instead of fa.Transitions.  Finally, the code compiles, but I have no idea if it works.

Edit:

If you want to be totaly generic you can do this:

type FiniteAutomaton&lt;'STATE, 'TOKEN when 'STATE:comparison and 'TOKEN:comparison&gt; = {
    InitialState: 'STATE
    FinalStates: Set&lt;'STATE&gt;
    Transitions: Map&lt;'STATE * 'TOKEN, 'STATE List&gt;
}


Also 'STATE should be a 'TOKEN List.