NFA和DFA的实施

Question

您能回顾一下我的F#代码并指出关于它的一些见解吗？

我想知道的是，按相关性排列：

• 避免DFA和NFA之间的这么多通用代码。我想让一些更通用的东西，有很多共同的代码。
• 让它更像F#的习语

表现不是问题。可读性就是。

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

快速查看一下就会发现，与FiniteAutomaton类型的唯一区别是，转换要么采用string，要么采用string List。所以把它概括一下！

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)

我试图尽可能多地删除类型注释。让F#'s类型推理发挥它的魔力。而且，它方便地传递fa而不是fa.Transitions。最后，代码编译，但我不知道它是否工作。

编辑：

如果您想成为完全通用的，您可以这样做：

type FiniteAutomaton<'STATE, 'TOKEN when 'STATE:comparison and 'TOKEN:comparison> = {
    InitialState: 'STATE
    FinalStates: Set<'STATE>
    Transitions: Map<'STATE * 'TOKEN, 'STATE List>
}

另外，'STATE应该是'TOKEN List。