ocaml中的自动机

Question

我对OCaml有点新鲜。我想在ocaml中实现自动机的产品构造算法。我很困惑如何在ocaml中表示自动机。有人能帮我吗？

Answer 1

对于有限确定性自动清洁的表示是：

type ('state,'letter) automaton = { 
    initial : 'state ; 
    final  : 'state -> bool ; 
    transition : 'letter -> 'state -> 'state ; 
} 

例如，它确定一个字是否包含奇数个的'a'可以表示为这样的自动机：

let odd = { 
    initial = `even ; 
    final  = (function `odd -> true | _ -> false) ; 
    transition = (function 
    | 'a' -> (function `even -> `odd | `odd -> `even) 
    | _ -> (fun state -> state)) 
} 

另一个例子是只接受字符串"bbb"（是的，这些取自this online handout）的自动化：

let bbb = { 
    initial = `b0 ; 
    final = (function `b3 -> true | _ -> false) ; 
    transition = (function 
    | 'b' -> (function `b0 -> `b1 | `b1 -> `b2 | `b2 -> `b3 | _ -> `fail) 
    | _ -> (fun _ -> `fail)) 
} 

自动机产品在数学上被描述为使用状态集合作为新的组的笛卡儿积，并超过该组的最后和过渡函数的自然扩展：

let product a b = { 
    initial = (a.initial, b.initial) ; 
    final = (fun (x,y) -> a.final x && b.final y) ; 
    transition = (fun c (x,y) -> (a.transition c x, b.transition c y) 
} 

此产品自动机计算两种语言的交集。您也可以使用||代替&&来实现两种语言的联合。