automata in OCaml

Question

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?

Answer 1

A clean representation for a finite deterministic automaton would be:

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

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

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.