Функция перехода автомата

Question

Моя цель - реализовать функцию перехода в OCaml, которая принимает входное состояние, а символ возвращает положительную булеву формулу (включая true и false). То есть: \ дельта (q0, а) = q1 и (q2 или q3)

моя проблема заключается в том, чтобы представлять булевы формулы в OCaml и как реализовать функцию перехода с этой конкретной

Answer 1

Переменный конечный автомат , а?

Представление булеву формулу будет сделан с помощью простого рекурсивного типа варианта (что я собираюсь сделать в полиморфный тип, потому что я не хочу, чтобы указать тип государства еще):

type ’state formula = 
    | And  of ’state formula list 
    | Or  of ’state formula list 
    | Literal of bool 
    | Variable of ’state 

так, например, q1 and (q2 or q3) будет представлена ​​как:

And [ Variable q1 ; Or [ Variable q2 ; Variable q3 ] ] 

Вы можете представить функцию в любой реальной функции OCaml:

type state = Q0 | Q1 | Q2 | Q3 
let delta : state * char -> state formula = function 
    | Q0, 'a' -> And [ Variable Q1 ; Or [ Variable Q2 ; Variable Q3 ] ] 
    | _ -> ... 

Или вы можете выбрать для хранения переходов в карте (это позволяет построить свой автомат во время выполнения):

type state = int 

module OrderedStateChar = struct 
    type = state * char 
    let compare = compare 
end 

module StateCharMap = Map.Make(OrderedStateChar) 

let transition_of_map map = 
    fun (state,char) -> 
    try StateCharMap.find (state,char) map 
    with Not_found -> Literal false 

let map = List.fold_left 
    (fun map (state,char,formula) -> StateCharMap.add (state,char) formula map) 
    StateCharMap.empty 
    [ 
    0, 'a', And [ Variable 1 ; Or [ Variable 2 ; Variable 3 ] ] ; 
    ... 
    ] 

let transition = transition_of_map map 

let _ = transition (0,'a') (*/* returns '1 and (2 or 3)' */*)