Моя цель - реализовать функцию перехода в OCaml, которая принимает на вход состояние, а символ возвращает положительную логическую формулу (включая true и false). То есть: \delta(q0,a) = q1 и (q2 или 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)' */*)
