当前位置：文江博客话题详情

自动机的转移函数

发布于 2024-10-05 07:00:35 字数 149 浏览 3 评论 0原文

我的目标是在 OCaml 中实现一个转换函数，它接受输入状态，并且字符返回正布尔公式（包括 true 和 false）。即： \delta(q0,a) = q1 和 (q2 或 q3)

我的问题是如何在 ocaml 中表示布尔公式以及如何用这个特定的函数实现转换函数

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

瞎闹 2024-10-12 07:00:35

交替有限自动机，是吗？

表示布尔公式可以使用简单的递归变体类型来完成（我将使其成为多态类型，因为我还不想指定状态的类型）：

type ’state formula = 
  | And      of ’state formula list
  | Or       of ’state formula list
  | Literal  of bool
  | Variable of ’state

例如，q1和 (q2 或 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)' */*)

Alternating finite automaton, eh?

Representing a boolean formula would be done with a simple recursive variant type (that I'm going to make into a polymorphic type because I don't want to specify the type of a state yet):

type ’state formula = 
  | And      of ’state formula list
  | Or       of ’state formula list
  | Literal  of bool
  | Variable of ’state

So, for instance, q1 and (q2 or q3) would be represented as:

And [ Variable q1 ; Or [ Variable q2 ; Variable q3 ] ]

You may represent the function as either an actual OCaml function:

type state = Q0 | Q1 | Q2 | Q3
let delta : state * char -> state formula = function 
  | Q0, 'a' -> And [ Variable Q1 ; Or [ Variable Q2 ; Variable Q3 ] ]
  | _ -> ...

Or you may opt for storing the transitions in a map (this lets you build your automaton at runtime):

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

回复收藏 0 原文

~没有更多了~