オートマトンの遷移関数

Question

私の目標は、OCamlに入力を取り込む遷移関数を実装することです。文字は正の論理式（真と偽を含む）を返します。ある ：\デルタ（Q0、A）= 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)のように表されます：あなたはどちらか、実際のOCamlの関数としての機能を表すことができる

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

：

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)' */*)