type regexp = Void | Eps | Char of char
              | Alt of regexp * regexp | Seq of regexp * regexp | Star of regexp

(* poate o expresie regulata sa produca sirul vid ? *)
let rec haseps = function
  | Void | Char _ -> false
  | Eps | Star _ -> true
  | Alt (e1, e2) -> haseps e1 || haseps e2
  | Seq (e1, e2) -> haseps e1 && haseps e2

let rec simplify = function
  | Alt (Void, r) | Alt (r, Void) -> simplify r
  | Alt (Eps, r) | Alt (r, Eps) ->
    if haseps r then simplify r else Alt(Eps, simplify r)
  | Alt (r1, r2) -> Alt (simplify r1, simplify r2)
  | Seq (Void, _) -> Void
  | Seq (Eps, r) -> simplify r
  | Seq (r1, r2) -> Seq (simplify r1, simplify r2)
  | Star r -> Star (simplify r)
  | r -> r

(* daca primul caracter e c, ce expresie regulata ramane ?
   deriv r c = { w | cw \in r } *)
let deriv r c = 
  let rec derivr = function        (* c e fixat din functia exterioara *)
    | Char c1 when c = c1 -> Eps
    | Void | Eps | Char _ -> Void
    | Seq (e1, e2) -> let r = Seq(derivr e1, e2)
                      in if haseps e1 then Alt(r, Seq(e1, derivr e2)) else r
  | Alt (e1, e2) -> Alt (derivr e1, derivr e2)
  | Star e -> Seq(derivr e, Star e)
  in simplify (derivr r)

let comp f g x = f (g x)

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

This document was generated using caml2html