ocaml中的自动机 [英] automata in ocaml

问题描述

我对OCaml有点陌生.我想在ocaml中实现自动机的产品构造算法.我很困惑如何在ocaml中表示自动机.有人可以帮我吗?

I am a bit new to OCaml. I want to implement product construction algorithm for automata in ocaml. I am confused how to represent automata in ocaml. Can someone help me?

推荐答案

有限确定性自动机的简洁表示法是:

A clean representation for a finite deterministic automaton would be:

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

例如，确定单词是否包含奇数'a'的自动机可以表示为:

For instance, an automaton which determines whether a word contains an odd number of 'a' could be represented as such:

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

另一个示例是仅接受字符串"bbb"的自动化(是的，这些取自此在线讲义):

Another example is an automation which accepts onlythe string "bbb" (yes, these are taken from 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))
}

自动积在数学上被描述为使用状态集的笛卡尔积作为新集，以及最终和转移函数对该集的自然扩展:

Automaton product is described mathematically as using the cartesian product of the state sets as the new sets, and the natural extensions of the final and transition functions over that set:

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

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

This product automaton computes the intersection of two languages. You can also use || in lieu of && to implement the union of two languages.

这篇关于ocaml中的自动机的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！