code-review.fs

type FiniteAutomaton<'a> = {
    InitialState: string
    FinalStates: Set<string>
    Transitions: Map<string * char, 'a>
}
type DeterministicFiniteAutomaton = FiniteAutomaton<string>
type NondeterministicFiniteAutomaton = FiniteAutomaton<string List>

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)

let nfa = {
    NondeterministicFiniteAutomaton.InitialState = "s0"
    FinalStates = ["s2"; "s3"; "s4"] |> Set.ofList
    Transitions = [
    ("s0", 'a'), ["s1"];
    ("s1", 'a'), ["s2"; "s3"; "s4"]
    ("s2", 'b'), ["s2"];
    ("s3", 'c'), ["s0"];
    ("s4", 'd'), ["s2"]; ] |> Map.ofList
}

let dfa = {
    DeterministicFiniteAutomaton.InitialState = "s0"
    FinalStates = ["s2"] |> Set.ofList
    Transitions = [
    ("s0", 'a'), "s0"
    ("s0", 'b'), "s1"
    ("s1", 'b'), "s1"
    ("s1", 'a'), "s2"
    ("s2", 'a'), "s2" ] |> Map.ofList
}

[<EntryPoint>]
let main argv =
    let input = System.IO.File.ReadAllText "test_dfa.txt"

    // dfa will not work here because F# infers that
    // Map<string * char, 'a>
    // is
    // Map<string * char, string>
    printfn "%A" (accepts input dfa)

    0