fonction de transition d'un automate

Question

Mon but est d'implémenter une fonction de transition dans OCaml qui prend en entrée un état et un caractère renvoie une formule booléenne positive (incluant vrai et faux). C'est: \ delta (q0, a) = q1 et (q2 ou q3)

mon problème est de savoir comment représenter une formule booléenne dans OCaml et comment mettre en œuvre la fonction de transition avec ce spécifique

Answer 1

Alternant automate fini hein?

Représentant une formule booléenne serait fait avec un type simple variante récursive (que je vais faire dans un type polymorphes parce que je ne veux pas préciser le type d'un état encore):

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

Ainsi, par exemple, q1 and (q2 or q3) serait représenté par:

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

Vous peut représenter la fonction que ce soit une fonction OCaml réelle:

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

Ou vous pouvez opter pour le stockage des transitions dans une carte (ce qui vous permet de construire votre automate à l'exécution):

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