Created
June 21, 2025 03:55
-
-
Save matthewd673/3f31190e14df7b374b151dc9081476d2 to your computer and use it in GitHub Desktop.
Tiny DFA simulation in OCaml
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
(* 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