Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.