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"(是的,这些是从这个在线讲义中获取的):

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)
}

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