自动机的转换函数

Question

我的目标是在OCaml中实现一个转换函数，它接受输入一个状态并且一个字符返回一个正的布尔公式（包括true和false）。 即：\增量（Q0，A）= q1和（Q2或Q3）

我的问题是如何表示一个布尔公式OCaml中，以及如何实现与此特定

Answer 1

转换函数交替有限自动机，呃？

代表一个布尔公式将用一个简单的递归variant类型来完成（即我要制作成多态的类型，因为我不想尚未指定状态的类型）：

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