我的目标是在 OCaml 中实现一个转换函数,它接受输入一个状态,一个字符返回一个正布尔公式(包括真假)。即:\delta(q0,a) = q1 and (q2 or q3)
我的问题是如何在 ocaml 中表示一个布尔公式以及如何用这个特定的方法实现转换函数
我的目标是在 OCaml 中实现一个转换函数,它接受输入一个状态,一个字符返回一个正布尔公式(包括真假)。即:\delta(q0,a) = q1 and (q2 or q3)
我的问题是如何在 ocaml 中表示一个布尔公式以及如何用这个特定的方法实现转换函数
交替有限自动机,嗯?
表示一个布尔公式可以用一个简单的递归变体类型来完成(我将把它变成多态类型,因为我还不想指定状态的类型):
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)' */*)