NFA and DFA implementation

Question

Can you review my F# code and point out some insights about it?

What I want to know, in order of relevance:

• Avoid so much common code between DFA and NFA. I want to make something more generic, there is much code in common there.

• Make it more F# idiomatic

Performance is not a concern. Readability is.

module DFA =
    type DeterministicFiniteAutomaton = {
        InitialState: string
        FinalStates: Set<string>
        Transitions: Map<string * char, string>
    }

    let private nextState (symbol:char) (state:string) (transitions:Map<string * char, string>) =
        transitions |> Map.tryFind (state, symbol)

    let rec private haltState (input:string) (index:int) (state:string) (transitions:Map<string * char, string>) =
        match index with
        | i when i = input.Length -> state
        | _ ->
            match nextState input.[index] state transitions with
            | None -> null
            | Some state -> haltState input (index+1) state transitions

    let accepts (input:string) (dfa:DeterministicFiniteAutomaton) =
        dfa.FinalStates |> Set.contains (haltState input 0 dfa.InitialState dfa.Transitions)

module NFA =
    type NondeterministicFiniteAutomaton = {
        InitialState: string
        FinalStates: Set<string>
        Transitions: Map<string * char, string List>
    }

    let private nextState (symbol:char) (state:string) (transitions:Map<string * char, string List>) =
        transitions |> Map.tryFind (state, symbol)

    let rec private haltStates (input:string) (index:int) (state:string) (transitions:Map<string * char, string List>) =
        match index with
        | i when i = input.Length -> Seq.singleton state
        | _ ->
            match nextState input.[index] state transitions with
            | None -> Seq.empty
            | Some states ->
                states |> Seq.collect (fun state ->
                    haltStates input (index+1) state transitions)

    let accepts (input:string) (nfa:NondeterministicFiniteAutomaton) =
        haltStates input 0 nfa.InitialState nfa.Transitions
        |> Set.ofSeq
        |> Set.intersect nfa.FinalStates
        |> Set.count > 0

Answer 1

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<'a> = {
    InitialState: string
    FinalStates: Set<string>
    Transitions: Map<string * char, 'a>
}
type DeterministicFiniteAutomaton = FiniteAutomaton<string>
type NondeterministicFiniteAutomaton = FiniteAutomaton<string List>

The rest pretty much falls in place:

let private nextState symbol state fa =
    fa.Transitions |> Map.tryFind (state, symbol)

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

let accepts input fa =
    fa.FinalStates |> 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<'STATE, 'TOKEN when 'STATE:comparison and 'TOKEN:comparison> = {
    InitialState: 'STATE
    FinalStates: Set<'STATE>
    Transitions: Map<'STATE * 'TOKEN, 'STATE List>
}

Also 'STATE should be a 'TOKEN List.