```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