a little ocaml program to decide set inclusion for regular languages

regexp_subset.ml

type alphabet
type regexp =
  | Empty (* empty string! *)
  | Atom of alphabet
  | Star of regexp
  | Concat of regexp * regexp
  | Union of regexp * regexp

let rec core = function
  | Star r -> core r
  | r -> r

let rec size  = function
  | Star r -> 1 + size r
  | Atom _ -> 1
  | Empty -> 0
  | Concat (r1,r2) -> size r1 + size r2
  | Union (r1,r2) -> max (size r1) (size r2)
    
let rec is_subset (r1: regexp) (r2: regexp) =
  match r2 with
  | Empty ->
     begin
       match r1 with | Empty -> true | _ -> false
     end
  | Atom a2 ->
     begin
       match r1 with
       | Empty -> true
       | Atom a1 -> a1 = a2
       | _ -> false
     end
  | Star r2' ->
     let r2 = core r2' in
     let r1 = core r1 in
     let rec check acc =
       if is_subset r1 acc then
         true
       else
         if (size acc > size r1) then false
         else
           check (Concat(acc, r2))
     in check r2
  | Concat (r2L, r2R) ->
          begin 
            match r1 with
            | Concat (r1L, r1R) -> is_subset r1L r2L && is_subset r1R r2R
            | _ -> false
          end
  | Union (r2L, r2R) ->
     is_subset r1 r2L || is_subset r1 r2R