functional-programming - オートマトンの遷移関数

Question

私の目標は、状態を入力し、文字が正のブール式（trueとfalseを含む）を返す遷移関数をOCamlに実装することです。つまり、\ delta（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)ように表されます。

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