type regex = Void | Eps | C of char
             | Alt of regex * regex | Seq of regex * regex | Rep of regex

let rec haseps = function
  | Void | C _ -> false
  | Eps -> true
  | Alt(e1, e2) -> haseps e1 || haseps e2
  | Seq(e1, e2) -> haseps e1 && haseps e2
  | Rep e -> simplify e <> Void
and simplify = function
  | Alt (e1, e2) -> (match (simplify e1, simplify e2) with
    | (Void, e) | (e, Void) -> e
    | (Eps, e) | (e, Eps) when haseps e -> e
    | (e1, e2) -> Alt (e1, e2))
  | Seq (e1, e2) -> (match (simplify e1, simplify e2) with
    | (Void, _) | (_, Void) -> Void
    | (Eps, e) | (e, Eps) -> e
    | (e1, e2) -> Seq (e1, e2))
  | Rep e -> (match simplify e with
    | (Eps | Void) as e -> e
    | e -> Rep e)
  | e -> e

let deriv r c = 
  let rec derivr = function
    | C c1 when c = c1 -> Eps
    | Void | Eps | C _ -> Void
    | Alt(e1, e2) -> Alt(derivr e1, derivr e2)
    | Seq(e1, e2) -> let r = Seq(derivr e1, e2) in
                      if haseps e1 then Alt(r, derivr e2) else r
    | Rep e -> Seq(derivr e, Rep e)
  in simplify (derivr r)

let comp f g x = f (g x)

let accept r = comp haseps (List.fold_left deriv r)

let re = Alt(Seq(Seq(Rep(Seq(C '0', C '1')), C '1'),
                  Seq(C '1', C '1')),
                  Rep(Alt(Seq(C '0', C '0'), C '1')))
;;

simplify (Alt(Alt(Eps, Void), Alt(Void,Eps)));;

accept re ['0';'1';'1';'1';'1'];;

This document was generated using caml2html