Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- open Core
- type ('a, 'b) dfa = {
- alphabet: 'a list;
- transition: ('b * 'a * 'b) list;
- initial: 'b;
- accept: 'b list;
- }
- let alphabet = [0; 1;]
- let transition = [
- (0, 0, 1);
- (0, 1, 0);
- (1, 1, 1);
- (1, 0, 0);
- ]
- let initial = 0
- let accept = [0]
- let automata = { alphabet; transition; initial; accept; }
- let rec find transition state symbol =
- match transition with
- | [] -> None
- | (x, y, z) :: _ when x = state && y = symbol -> Some z
- | _::tl -> find tl state symbol
- let run automata seq =
- let rec step state = function
- | [] ->
- if List.mem automata.accept state ~equal:(=) then
- Ok state
- else
- Or_error.error_string "not accepted"
- | symbol::tl ->
- match find automata.transition state symbol with
- | None -> Or_error.error_string "no transition"
- | Some next -> step next tl
- in
- step automata.initial seq
- let () =
- match run automata [1; 0; 0; 1;] with
- | Ok state -> Printf.printf "accept %d\n" state
- | Error e -> Printf.printf "failed %s\n" (Error.to_string_hum e)
Add Comment
Please, Sign In to add comment