Skip to content

Instantly share code, notes, and snippets.

@matthewd673
Created June 21, 2025 03:55
Show Gist options
  • Save matthewd673/3f31190e14df7b374b151dc9081476d2 to your computer and use it in GitHub Desktop.
Save matthewd673/3f31190e14df7b374b151dc9081476d2 to your computer and use it in GitHub Desktop.
Tiny DFA simulation in OCaml
(* Data structures *)
type trsns = (int * int) list (* (next * value) list *)
type state = trsns * bool (* trsns * success *)
type dfa = state list * int (* state list * start *)
(* Simulation *)
let exec dfa input =
let rec step states ptr = function (* match input *)
| [] ->
let (_, s) = List.nth states ptr in
s
| h :: t ->
let (trsn, _) = List.nth states ptr in
match List.find_opt (fun (_, v) -> v = h) trsn with
| None -> false
| Some(n, _) -> step states n t
in
let (states, start) = dfa in
step states start input
;;
(* Example *)
let () =
let x = ([
([(1, 10)], false); (* 0 *)
([(2, 11); (3, 12)], false); (* 1 *)
([], true); (* 2 *)
([(3, 13); (2, 14)], false); (* 3 *)
], 0) in
let res = exec x [10; 12; 13; 13; 13; 13; 14] in
Printf.printf "Success? %b\n" res
;;
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment