(** * Coq codes *)
(** ** Dependencies *)

Require Export RegExp.Utility.
Require Export RegExp.Definitions.
Require Export RegExp.Boolean.

(** ** [Cat] is morphism *)

Lemma Cat_morphism_s : forall s r0 r1 r0' r1', 
  r0 =R= r1 -> r0' =R= r1' -> (r0 ++ r0') ~= s = (r1 ++ r1') ~= s. 
Proof.
(* Goal: forall (s : string) (r r' r'' : RegExp), @eq bool (matches (Cat (Or r r') r'') s) (matches (Or (Cat r r'') (Cat r' r'')) s) *)
  induction s.
    (* ""%string *)
(* Goal: forall (r0 r1 r0' r1' : RegExp) (_ : re_eq r0 r1) (_ : re_eq r0' r1'), @eq bool (matches (Cat r0 r0') (String a s)) (matches (Cat r1 r1') (String a s)) *)
    intros r0 r1 r0' r1' H H'.  simpl.  rewrite <- (nu_morphism r0 r1 H).  
(* Goal: @eq bool (andb (nu r0) (nu r0')) (andb (nu r0) (nu r1')) *)
(* Goal: forall (r0 r1 r0' r1' : RegExp) (_ : re_eq r0 r1) (_ : re_eq r0' r1'), @eq bool (matches (Cat r0 r0') (String a s)) (matches (Cat r1 r1') (String a s)) *)
    rewrite <- (nu_morphism r0' r1' H').  auto.
    (* String a s *)
(* Goal: forall (r0 r1 r0' r1' : RegExp) (_ : re_eq r0 r1) (_ : re_eq r0' r1'), @eq bool (matches (Cat r0 r0') (String a s)) (matches (Cat r1 r1') (String a s)) *)
    intros r0 r1 r0' r1' H H'.  simpl.  rewrite <- (nu_morphism r0 r1 H).  
(* Goal: @eq bool (matches (if nu r0 then Or (Cat (derive a r0) r0') (derive a r0') else Cat (derive a r0) r0') s) (matches (if nu r0 then Or (Cat (derive a r1) r1') (derive a r1') else Cat (derive a r1) r1') s) *)
    destruct (nu r0).
      (* true *)
(* Goal: @eq bool (orb (matches (Or (Cat (derive a r) r'') (Cat (derive a r') r'')) s) (matches (derive a r'') s)) (matches (Or (Cat (derive a r) r'') (Or (Cat (derive a r') r'') (derive a r''))) s) *)
(* Goal: @eq bool (matches (Cat (Or (derive a r) (derive a r')) r'') s) (matches (Or (Cat (derive a r) r'') (Cat (derive a r') r'')) s) *)
      repeat erewrite matches_Or.  
(* Goal: @eq bool (orb (matches (Cat (derive a r0) r0') s) (matches (derive a r0') s)) (orb (matches (Cat (derive a r1) r1') s) (matches (derive a r1') s)) *)
(* Goal: @eq bool (matches (Cat (derive a r0) r0') s) (matches (Cat (derive a r1) r1') s) *)
      replace (r1' / a ~= s) with (r0' / a ~= s).
(* Goal: @eq bool (orb (matches (Cat (derive a r0) r0') s) (matches (derive a r0') s)) (orb (matches (Cat (derive a r1) r1') s) (matches (derive a r0') s)) *)
(* Goal: @eq bool (matches (derive a r0') s) (matches (derive a r1') s) *)
(* Goal: @eq bool (matches (Cat (derive a r0) r0') s) (matches (Cat (derive a r1) r1') s) *)
      replace ((r1 / a ++ r1') ~= s) with ((r0 / a ++ r0') ~= s).
(* Goal: @eq bool (orb (matches (Cat (derive a r) r'') s) (matches (Cat (derive a r') r'') s)) (orb (matches (Cat (derive a r) r'') s) (matches (Cat (derive a r') r'') s)) *)
      auto.
        (* proof for replace *)
(* Goal: @eq bool (orb (matches (Cat (derive a r) r'') s) (matches (Cat (derive a r') r'') s)) (orb (matches (Cat (derive a r) r'') s) (matches (Cat (derive a r') r'') s)) *)
        eapply IHs; try auto.  eapply derive_morphism; try auto.
(* Goal: @eq bool (orb (matches (Cat (derive a r) r'') s) (matches (Cat (derive a r') r'') s)) (orb (matches (Cat (derive a r) r'') s) (matches (Cat (derive a r') r'') s)) *)
        unfold ascii_eq; auto.  
        (* proof for replace *)
(* Goal: @eq bool (orb (matches (Cat (derive a r) r'') s) (matches (Cat (derive a r') r'') s)) (orb (matches (Cat (derive a r) r'') s) (matches (Cat (derive a r') r'') s)) *)
        eapply derive_morphism; try auto.  unfold ascii_eq; auto.  
      (* false *)
(* Goal: @eq bool (orb (matches (Cat (derive a r) r'') s) (matches (Cat (derive a r') r'') s)) (orb (matches (Cat (derive a r) r'') s) (matches (Cat (derive a r') r'') s)) *)
      eapply IHs; try auto.  eapply derive_morphism; try auto.  
(* Goal: @eq bool (orb (matches (Cat (derive a r) r'') s) (matches (Cat (derive a r') r'') s)) (orb (matches (Cat (derive a r) r'') s) (matches (Cat (derive a r') r'') s)) *)
      unfold ascii_eq; auto.  
Qed.

Add Parametric Morphism : Cat with
signature re_eq ==> re_eq ==> re_eq as Cat_mor.
Proof.
(* Goal: @eq bool (orb (matches (Cat (derive a r) r'') s) (matches (Cat (derive a r') r'') s)) (orb (matches (Cat (derive a r) r'') s) (matches (Cat (derive a r') r'') s)) *)
  intros x y H x0 y0 H0.  unfold re_eq.  intro s.  eapply Cat_morphism_s; auto.
Qed.

(** ** [Empty] *)
(** [Empty] corresponds to 0 in Kleene algebra. *)

Lemma Cat_left_zero_s : forall s r, (Empty ++ r) ~= s = false.
Proof.
(* Goal: @eq bool (orb (matches (Cat (derive a r) r'') s) (matches (Cat (derive a r') r'') s)) (orb (matches (Cat (derive a r) r'') s) (matches (Cat (derive a r') r'') s)) *)
  induction s; simpl; auto.
Qed.

Theorem Cat_left_zero : forall r, Empty ++ r =R= Empty.
Proof.
(* Goal: forall r r' r'' : RegExp, re_eq (Cat (Or r r') r'') (Or (Cat r r'') (Cat r' r'')) *)
  unfold re_eq.  intros r s.  erewrite Empty_false.  
(* Goal: @eq bool (matches (Cat Empty r) s) false *)
  eapply Cat_left_zero_s.
Qed.

Lemma Cat_right_zero_s : forall s r, (r ++ Empty) ~= s = false.
Proof.
(* Goal: @eq bool (matches (Cat (Or r r') r'') (String a s)) (matches (Or (Cat r r'') (Cat r' r'')) (String a s)) *)
  induction s; intro r; simpl.
(* Goal: @eq bool (orb (matches (Cat (derive a r) r'') s) (matches (Cat (derive a r') r'') s)) (orb (matches (Cat (derive a r) r'') s) (matches (Cat (derive a r') r'') s)) *)
    destruct (nu r); simpl; auto.
(* Goal: @eq bool (matches (if nu r then Or (Cat (derive a r) Eps) Empty else Cat (derive a r) Eps) s) false *)
    case_eq (nu r); intro nu_r'.
(* Goal: @eq bool (orb (matches (Cat (derive a r) r'') s) (matches (Cat (derive a r') r'') s)) (orb (matches (Cat (derive a r) r'') s) (matches (Cat (derive a r') r'') s)) *)
      erewrite matches_Or.  erewrite IHs.  erewrite Empty_false.  simpl; auto.
(* Goal: @eq bool (orb (matches (Cat (derive a r) r'') s) (matches (Cat (derive a r') r'') s)) (orb (matches (Cat (derive a r) r'') s) (matches (Cat (derive a r') r'') s)) *)
      erewrite IHs.  auto.
Qed.

Theorem Cat_right_zero : forall r, r ++ Empty =R= Empty.
Proof.
(* Goal: forall r r' r'' : RegExp, re_eq (Cat (Or r r') r'') (Or (Cat r r'') (Cat r' r'')) *)
  unfold re_eq.  intros r s.  erewrite Empty_false.  
(* Goal: @eq bool (matches (Cat r Empty) s) false *)
  eapply Cat_right_zero_s.
Qed.

(** ** [Cat] matches concatination of strings. *) 

Lemma matches_Cat : forall s s' r r', 
  r ~==s -> r' ~== s' -> (r ++ r') ~== (s ++ s')%string.
Proof.
(* Goal: forall (s : string) (r r' r'' : RegExp), @eq bool (matches (Cat (Or r r') r'') s) (matches (Or (Cat r r'') (Cat r' r'')) s) *)
  induction s.
    (* s = ""%string *)
(* Goal: forall (s' : string) (r r' : RegExp) (_ : @eq bool (matches r EmptyString) true) (_ : @eq bool (matches r' s') true), @eq bool (matches (Cat r r') (append EmptyString s')) true *)
(* Goal: forall (s' : string) (r r' : RegExp) (_ : @eq bool (matches r (String a s)) true) (_ : @eq bool (matches r' s') true), @eq bool (matches (Cat r r') (append (String a s) s')) true *)
    induction s'.
      (* s' = ""%string *)
(* Goal: @eq bool (matches (Cat (Or r r') r'') (String a s)) (matches (Or (Cat r r'') (Cat r' r'')) (String a s)) *)
      simpl. intros r r' nu_r nu_r'. rewrite nu_r. rewrite nu_r'. simpl; auto.
      (* s' = String a s *)
(* Goal: @eq bool (matches (Cat (Or r r') r'') (String a s)) (matches (Or (Cat r r'') (Cat r' r'')) (String a s)) *)
      simpl. intros r r' nu_r Hra.  rewrite nu_r.  erewrite matches_Or.
(* Goal: @eq bool (orb (matches (Cat (derive a r) r'') s) (matches (Cat (derive a r') r'') s)) (orb (matches (Cat (derive a r) r'') s) (matches (Cat (derive a r') r'') s)) *)
      rewrite Hra.  destruct ((r / a ++ r') ~= s'); simpl; auto.
    (* s = String a s *)
(* Goal: forall (s' : string) (r r' : RegExp) (_ : @eq bool (matches r (String a s)) true) (_ : @eq bool (matches r' s') true), @eq bool (matches (Cat r r') (append (String a s) s')) true *)
    intros s' r r' Hr Hr'.
(* Goal: @eq bool (matches (Cat r r') (append (String a s) s')) true *)
    replace (String a s ++ s')%string with (String a (s ++ s'))%string.
(* Goal: @eq bool (matches (Cat (Or r r') r'') (String a s)) (matches (Or (Cat r r'') (Cat r' r'')) (String a s)) *)
    rewrite derivation.  simpl.  case_eq (nu r); intro nu_r'.
      (* nu r' = true *)
(* Goal: @eq bool (matches (Or (Cat (derive a r) r'') (Cat (derive a r') r'')) s) (matches (Or (Cat (derive a r) r'') (Cat (derive a r') r'')) s) *)
      rewrite derivation in Hr.  erewrite matches_Or.
(* Goal: @eq bool (orb (matches (Cat (derive a r) r'') s) (matches (Cat (derive a r') r'') s)) (orb (matches (Cat (derive a r) r'') s) (matches (Cat (derive a r') r'') s)) *)
      specialize (IHs s' (r/a) r' Hr Hr').  rewrite IHs.  simpl; auto.
      (* nu r' = false *)
(* Goal: @eq bool (orb (matches (Cat (derive a r) r'') s) (matches (Cat (derive a r') r'') s)) (orb (matches (Cat (derive a r) r'') s) (matches (Cat (derive a r') r'') s)) *)
      rewrite derivation in Hr.  specialize (IHs s' (r/a) r' Hr Hr').  auto.  
      (* proof for replace *)
(* Goal: @eq bool (orb (matches (Cat (derive a r) r'') s) (matches (Cat (derive a r') r'') s)) (orb (matches (Cat (derive a r) r'') s) (matches (Cat (derive a r') r'') s)) *)
      simpl; auto.
Qed.

(** If [Cat] matches a string, the string can be divided into two strings which match the two [RegExp] respectively. *)
 
Lemma divide_Cat : forall s r' r'', (r' ++ r'') ~== s -> 
  {s':string & {s'':string | s = (s' ++ s'')%string /\ r' ~== s' /\ r'' ~== s'' }}.
Proof.
(* Goal: forall (s : string) (r r' r'' : RegExp), @eq bool (matches (Cat (Or r r') r'') s) (matches (Or (Cat r r'') (Cat r' r'')) s) *)
  induction s.
    (* s = ""%string *)
(* Goal: @eq bool (matches (Cat (Or r r') r'') (String a s)) (matches (Or (Cat r r'') (Cat r' r'')) (String a s)) *)
    intros r' r'' H.  exists ""%string.  exists ""%string.  simpl.
(* Goal: @eq bool (orb (matches (Cat (derive a r) r'') s) (matches (Cat (derive a r') r'') s)) (orb (matches (Cat (derive a r) r'') s) (matches (Cat (derive a r') r'') s)) *)
    split.  auto.  simpl in H.  
(* Goal: and (@eq bool (nu r') true) (@eq bool (nu r'') true) *)
(* Goal: forall (r' r'' : RegExp) (_ : @eq bool (matches (Cat r' r'') (String a s)) true), @sigT string (fun s' : string => @sig string (fun s'' : string => and (@eq string (String a s) (append s' s'')) (and (@eq bool (matches r' s') true) (@eq bool (matches r'' s'') true)))) *)
    destruct (nu r'); destruct (nu r''); split; simpl; auto; inversion H.
    (* s = String a s *)
(* Goal: forall (r' r'' : RegExp) (_ : @eq bool (matches (Cat r' r'') (String a s)) true), @sigT string (fun s' : string => @sig string (fun s'' : string => and (@eq string (String a s) (append s' s'')) (and (@eq bool (matches r' s') true) (@eq bool (matches r'' s'') true)))) *)
    intros r' r'' H.  simpl in H.  
(* Goal: @sigT string (fun s' : string => @sig string (fun s'' : string => and (@eq string (String a s) (append s' s'')) (and (@eq bool (matches r' s') true) (@eq bool (matches r'' s'') true)))) *)
(* Goal: @sigT string (fun s' : string => @sig string (fun s'' : string => and (@eq string (String a s) (append s' s'')) (and (@eq bool (matches r' s') true) (@eq bool (matches r'' s'') true)))) *)
    case_eq (nu r'); intro nu_r'; rewrite nu_r' in H; simpl in H.
      (* nu r' = true *)
(* Goal: @sigT string (fun s' : string => @sig string (fun s'' : string => and (@eq string (String a s) (append s' s'')) (and (@eq bool (matches r' s') true) (@eq bool (matches r'' s'') true)))) *)
(* Goal: @sigT string (fun s' : string => @sig string (fun s'' : string => and (@eq string (String a s) (append s' s'')) (and (@eq bool (matches r' s') true) (@eq bool (matches r'' s'') true)))) *)
      erewrite matches_Or in H.  
      case_eq ((r' / a ++ r'') ~= s); case_eq (r'' / a ~= s); 
(* Goal: @sigT string (fun s' : string => @sig string (fun s'' : string => and (@eq string (String a s) (append s' s'')) (and (@eq bool (matches r' s') true) (@eq bool (matches r'' s'') true)))) *)
(* Goal: @sigT string (fun s' : string => @sig string (fun s'' : string => and (@eq string (String a s) (append s' s'')) (and (@eq bool (matches r' s') true) (@eq bool (matches r'' s'') true)))) *)
      intros Hr''_a Hr'_r''_a; simpl in H.
        (* true true -> (String a s') ++ s'' *)
(* Goal: @sigT string (fun s' : string => @sig string (fun s'' : string => and (@eq string (String a s) (append s' s'')) (and (@eq bool (matches r' s') true) (@eq bool (matches r'' s'') true)))) *)
(* Goal: @sigT string (fun s' : string => @sig string (fun s'' : string => and (@eq string (String a s) (append s' s'')) (and (@eq bool (matches r' s') true) (@eq bool (matches r'' s'') true)))) *)
(* Goal: @sigT string (fun s' : string => @sig string (fun s'' : string => and (@eq string (String a s) (append s' s'')) (and (@eq bool (matches r' s') true) (@eq bool (matches r'' s'') true)))) *)
(* Goal: @sigT string (fun s' : string => @sig string (fun s'' : string => and (@eq string (String a s) (append s' s'')) (and (@eq bool (matches r' s') true) (@eq bool (matches r'' s'') true)))) *)
        specialize (IHs (r'/a) r'' Hr'_r''_a).
(* Goal: @sigT string (fun s' : string => @sig string (fun s'' : string => and (@eq string (String a s) (append s' s'')) (and (@eq bool (matches r' s') true) (@eq bool (matches r'' s'') true)))) *)
        destruct IHs as [s' [s'' [H1 [H2 H3]]]].
(* Goal: @sigT string (fun s' : string => @sig string (fun s'' : string => and (@eq string (String a s) (append s' s'')) (and (@eq bool (matches r' s') true) (@eq bool (matches r'' s'') true)))) *)
        exists (String a s').  exists s''.
(* Goal: @eq bool (matches (Cat (Or r r') r'') (String a s)) (matches (Or (Cat r r'') (Cat r' r'')) (String a s)) *)
        split.  simpl.  rewrite <- H1.  auto.  split; auto.
        (* (r' / a ++ r'') ~== s *)
(* Goal: @sigT string (fun s' : string => @sig string (fun s'' : string => and (@eq string (String a s) (append s' s'')) (and (@eq bool (matches r' s') true) (@eq bool (matches r'' s'') true)))) *)
(* Goal: @sigT string (fun s' : string => @sig string (fun s'' : string => and (@eq string (String a s) (append s' s'')) (and (@eq bool (matches r' s') true) (@eq bool (matches r'' s'') true)))) *)
(* Goal: @sigT string (fun s' : string => @sig string (fun s'' : string => and (@eq string (String a s) (append s' s'')) (and (@eq bool (matches r' s') true) (@eq bool (matches r'' s'') true)))) *)
(* Goal: @sigT string (fun s' : string => @sig string (fun s'' : string => and (@eq string (String a s) (append s' s'')) (and (@eq bool (matches r' s') true) (@eq bool (matches r'' s'') true)))) *)
        specialize (IHs (r'/a) r'' Hr'_r''_a).
(* Goal: @sigT string (fun s' : string => @sig string (fun s'' : string => and (@eq string (String a s) (append s' s'')) (and (@eq bool (matches r' s') true) (@eq bool (matches r'' s'') true)))) *)
        destruct IHs as [s' [s'' [H1 [H2 H3]]]].
(* Goal: @sigT string (fun s' : string => @sig string (fun s'' : string => and (@eq string (String a s) (append s' s'')) (and (@eq bool (matches r' s') true) (@eq bool (matches r'' s'') true)))) *)
        exists (String a s').  exists s''.
(* Goal: @eq bool (matches (Cat (Or r r') r'') (String a s)) (matches (Or (Cat r r'') (Cat r' r'')) (String a s)) *)
        split.  simpl.  rewrite <- H1.  auto.  split; auto.
        (* r'' / a ~== s *)
(* Goal: @sigT string (fun s' : string => @sig string (fun s'' : string => and (@eq string (String a s) (append s' s'')) (and (@eq bool (matches r' s') true) (@eq bool (matches r'' s'') true)))) *)
(* Goal: @sigT string (fun s' : string => @sig string (fun s'' : string => and (@eq string (String a s) (append s' s'')) (and (@eq bool (matches r' s') true) (@eq bool (matches r'' s'') true)))) *)
(* Goal: @sigT string (fun s' : string => @sig string (fun s'' : string => and (@eq string (String a s) (append s' s'')) (and (@eq bool (matches r' s') true) (@eq bool (matches r'' s'') true)))) *)
        exists ""%string.  exists (String a s).
(* Goal: @eq bool (matches (Cat (Or r r') r'') (String a s)) (matches (Or (Cat r r'') (Cat r' r'')) (String a s)) *)
        split.  simpl.  auto.  split; simpl; auto.  
        (* false false *)
(* Goal: @sigT string (fun s' : string => @sig string (fun s'' : string => and (@eq string (String a s) (append s' s'')) (and (@eq bool (matches r' s') true) (@eq bool (matches r'' s'') true)))) *)
(* Goal: @sigT string (fun s' : string => @sig string (fun s'' : string => and (@eq string (String a s) (append s' s'')) (and (@eq bool (matches r' s') true) (@eq bool (matches r'' s'') true)))) *)
        rewrite Hr''_a in H.  rewrite Hr'_r''_a in H.  simpl in H.  inversion H.
      (* nu r' = false *)
(* Goal: @sigT string (fun s' : string => @sig string (fun s'' : string => and (@eq string (String a s) (append s' s'')) (and (@eq bool (matches r' s') true) (@eq bool (matches r'' s'') true)))) *)
      specialize (IHs (r'/a) r'' H).
(* Goal: @sigT string (fun s' : string => @sig string (fun s'' : string => and (@eq string (String a s) (append s' s'')) (and (@eq bool (matches r' s') true) (@eq bool (matches r'' s'') true)))) *)
      destruct IHs as [s' [s'' [H1 [H2 H3]]]].
(* Goal: @sigT string (fun s' : string => @sig string (fun s'' : string => and (@eq string (String a s) (append s' s'')) (and (@eq bool (matches r' s') true) (@eq bool (matches r'' s'') true)))) *)
      exists (String a s').  exists s''.
(* Goal: @eq bool (matches (Cat (Or r r') r'') (String a s)) (matches (Or (Cat r r'') (Cat r' r'')) (String a s)) *)
      split.  simpl.  rewrite <- H1.  auto.  split; auto.
Defined.

Lemma divide_Cat_false : forall s r' r'', (r' ++ r'') ~!= s -> 
  forall s' s'', ((s = s' ++ s'')%string -> r' ~!= s' \/ r'' ~!= s'').
Proof.
(* Goal: forall (s : string) (r' r'' : RegExp) (_ : @eq bool (matches (Cat r' r'') s) false) (s' s'' : string) (_ : @eq string s (append s' s'')), or (@eq bool (matches r' s') false) (@eq bool (matches r'' s'') false) *)
  intros s r' r'' H0.
(* Goal: forall (s' s'' : string) (_ : @eq string s (append s' s'')), or (@eq bool (matches r' s') false) (@eq bool (matches r'' s'') false) *)
  intros s' s''.
(* Goal: @eq bool (orb (matches (Cat (derive a r) r'') s) (matches (Cat (derive a r') r'') s)) (orb (matches (Cat (derive a r) r'') s) (matches (Cat (derive a r') r'') s)) *)
  case_eq (r' ~= s'); case_eq (r'' ~= s''); intros Hr''s'' Hr's' Hs; try auto.
    (* true true *)
(* Goal: or (@eq bool true false) (@eq bool true false) *)
    specialize(matches_Cat s' s'' r' r'' Hr's' Hr''s'').  
(* Goal: forall _ : @eq bool (matches (Cat r' r'') (append s' s'')) true, or (@eq bool true false) (@eq bool true false) *)
    left.  rewrite <- Hs in H.  rewrite H0 in H.  discriminate H.
Qed.

(** ** [Eps] *)
(** [Eps] corresponds to 1 in Kleene algebra. *)

Lemma Cat_left_id_s : forall s r, (Eps ++ r) ~= s = r ~= s.
Proof.
(* Goal: forall (s : string) (r r' r'' : RegExp), @eq bool (matches (Cat (Or r r') r'') s) (matches (Or (Cat r r'') (Cat r' r'')) s) *)
  induction s.
(* Goal: @eq bool (orb (matches (Cat (derive a r) r'') s) (matches (Cat (derive a r') r'') s)) (orb (matches (Cat (derive a r) r'') s) (matches (Cat (derive a r') r'') s)) *)
    simpl; auto.  
(* Goal: @eq bool (matches (Cat (Or r r') r'') (String a s)) (matches (Or (Cat r r'') (Cat r' r'')) (String a s)) *)
    simpl. intros r. erewrite matches_Or.  
(* Goal: @eq bool (orb (matches (Cat (derive a r) r'') s) (matches (Cat (derive a r') r'') s)) (orb (matches (Cat (derive a r) r'') s) (matches (Cat (derive a r') r'') s)) *)
    erewrite Cat_left_zero_s.  simpl; auto.
Qed.

Theorem Cat_left_id : forall r, Eps ++ r =R= r.
Proof.
(* Goal: forall r r' r'' : RegExp, re_eq (Cat (Or r r') r'') (Or (Cat r r'') (Cat r' r'')) *)
  unfold re_eq. intros r s. eapply Cat_left_id_s. 
Qed.

Lemma Cat_right_id_s : forall s r, (r ++ Eps) ~= s = r ~= s.
Proof.
(* Goal: forall (s : string) (r : RegExp), @eq bool (matches (Cat r Eps) s) (matches r s) *)
  intros s r.  case_eq (r ~= s); intro Hrs.
    (* r ~== s *)
(* Goal: @eq bool (matches (Cat r Eps) s) true *)
(* Goal: @eq bool (matches (Cat r Eps) s) false *)
    replace ((r ++ Eps) ~= s) with ((r ++ Eps) ~= (s ++ EmptyString)).
(* Goal: @eq bool (orb (matches (Cat (derive a r) r'') s) (matches (Cat (derive a r') r'') s)) (orb (matches (Cat (derive a r) r'') s) (matches (Cat (derive a r') r'') s)) *)
    eapply matches_Cat; auto.  
(* Goal: @eq bool (orb (matches (Cat (derive a r) r'') s) (matches (Cat (derive a r') r'') s)) (orb (matches (Cat (derive a r) r'') s) (matches (Cat (derive a r') r'') s)) *)
    erewrite string_right_id.  auto. 
    (* r ~!= s *)
(* Goal: @eq bool (matches (Cat r Eps) s) false *)
    generalize dependent r.  
(* Goal: forall (s : string) (r r' r'' : RegExp), @eq bool (matches (Cat (Or r r') r'') s) (matches (Or (Cat r r'') (Cat r' r'')) s) *)
    induction s.      
(* Goal: @eq bool (orb (matches (Cat (derive a r) r'') s) (matches (Cat (derive a r') r'') s)) (orb (matches (Cat (derive a r) r'') s) (matches (Cat (derive a r') r'') s)) *)
      intros r H.  simpl in *.  rewrite H.  auto.
(* Goal: @eq bool (matches (if nu r then Or (Cat (derive a r) Eps) Empty else Cat (derive a r) Eps) s) false *)
      intros r H.  simpl in *.  case_eq (nu r); intro nu_r'.
        (* nu r = true *)
(* Goal: @eq bool (orb (matches (Cat (derive a r) Eps) s) (matches Empty s)) false *)
(* Goal: @eq bool (matches (Cat (derive a r) Eps) s) false *)
        erewrite matches_Or.  erewrite Empty_false.
(* Goal: @eq bool (orb (matches (Cat (derive a r) Eps) s) false) false *)
(* Goal: @eq bool (matches (Cat (derive a r) Eps) s) false *)
        replace (((r / a ++ Eps) ~= s) || false)%bool with ((r / a ++ Eps) ~= s).
(* Goal: @eq bool (orb (matches (Cat (derive a r) r'') s) (matches (Cat (derive a r') r'') s)) (orb (matches (Cat (derive a r) r'') s) (matches (Cat (derive a r') r'') s)) *)
        erewrite IHs; auto.  
(* Goal: @eq bool (orb (matches (Cat (derive a r) r'') s) (matches (Cat (derive a r') r'') s)) (orb (matches (Cat (derive a r) r'') s) (matches (Cat (derive a r') r'') s)) *)
        destruct ((r / a ++ Eps) ~= s); auto.
        (* nu r = false *)
(* Goal: @eq bool (orb (matches (Cat (derive a r) r'') s) (matches (Cat (derive a r') r'') s)) (orb (matches (Cat (derive a r) r'') s) (matches (Cat (derive a r') r'') s)) *)
        erewrite IHs; auto.  
Qed.

Theorem Cat_right_id : forall r, r ++ Eps =R= r.
Proof.
(* Goal: forall r r' r'' : RegExp, re_eq (Cat (Or r r') r'') (Or (Cat r r'') (Cat r' r'')) *)
  unfold re_eq.  intros r s.  eapply Cat_right_id_s.
Qed.

(** ** [Cat] is associative. *)

Lemma matches_Cat_Cat_left : forall s s' s'' r r' r'',
  r ~== s -> r' ~== s' -> r'' ~== s'' -> 
  ((r ++ r') ++ r'') ~== ((s ++ s') ++ s'').
Proof.
(* Goal: forall (s s' s'' : string) (r r' r'' : RegExp) (_ : @eq bool (matches r s) true) (_ : @eq bool (matches r' s') true) (_ : @eq bool (matches r'' s'') true), @eq bool (matches (Cat r (Cat r' r'')) (append s (append s' s''))) true *)
  intros s s' s'' r r' r'' H H' H''.  
(* Goal: @eq bool (orb (matches (Cat (derive a r) r'') s) (matches (Cat (derive a r') r'') s)) (orb (matches (Cat (derive a r) r'') s) (matches (Cat (derive a r') r'') s)) *)
  repeat eapply matches_Cat; auto.  
Qed.

Lemma matches_Cat_Cat_right : forall s s' s'' r r' r'',
  r ~== s -> r' ~== s' -> r'' ~== s'' -> 
  (r ++ (r' ++ r'')) ~== (s ++ (s' ++ s'')).
Proof.
(* Goal: forall (s s' s'' : string) (r r' r'' : RegExp) (_ : @eq bool (matches r s) true) (_ : @eq bool (matches r' s') true) (_ : @eq bool (matches r'' s'') true), @eq bool (matches (Cat r (Cat r' r'')) (append s (append s' s''))) true *)
  intros s s' s'' r r' r'' H H' H''.  
(* Goal: @eq bool (orb (matches (Cat (derive a r) r'') s) (matches (Cat (derive a r') r'') s)) (orb (matches (Cat (derive a r) r'') s) (matches (Cat (derive a r') r'') s)) *)
  repeat eapply matches_Cat; auto.  
Qed.

Lemma Cat_assoc_s : forall s r r' r'', 
  ((r ++ r') ++ r'') ~= s = (r ++ (r' ++ r'')) ~= s.
Proof.
(* Goal: forall (s : string) (r r' r'' : RegExp), @eq bool (matches (Cat (Cat r r') r'') s) (matches (Cat r (Cat r' r'')) s) *)
  intros s r r' r''.  case_eq (((r ++ r') ++ r'') ~= s); intro H; symmetry. 
    (* true *)
(* Goal: @eq bool (matches (Cat r (Cat r' r'')) s) true *)
(* Goal: @eq bool (matches (Cat r (Cat r' r'')) s) false *)
    specialize(divide_Cat s (r ++ r') r'' H).  intro H0.
(* Goal: @eq bool (matches (Cat r (Cat r' r'')) s) true *)
(* Goal: @eq bool (matches (Cat r (Cat r' r'')) s) false *)
    destruct H0 as [srr' [s_'' [H01 [H02 Hs_''r'']]]].
(* Goal: forall _ : @sigT string (fun s' : string => @sig string (fun s'' : string => and (@eq string srr' (append s' s'')) (and (@eq bool (matches r s') true) (@eq bool (matches r' s'') true)))), @eq bool (matches (Cat r (Cat r' r'')) s) true *)
(* Goal: @eq bool (matches (Cat r (Cat r' r'')) s) false *)
    specialize(divide_Cat srr' r r' H02).  intro H0.
(* Goal: @eq bool (matches (Cat r (Cat r' r'')) s) true *)
(* Goal: @eq bool (matches (Cat r (Cat r' r'')) s) false *)
    destruct H0 as [s_ [s_' [Hs_s_' [Hs_r Hs_'r']]]].
(* Goal: @eq bool (matches (Cat r (Cat r' r'')) s) true *)
(* Goal: @eq bool (matches (Cat r (Cat r' r'')) s) false *)
    replace s with (s_ ++ (s_' ++ s_''))%string.
(* Goal: @eq bool (orb (matches (Cat (derive a r) r'') s) (matches (Cat (derive a r') r'') s)) (orb (matches (Cat (derive a r) r'') s) (matches (Cat (derive a r') r'') s)) *)
    eapply matches_Cat_Cat_right; auto.  
(* Goal: @eq bool (orb (matches (Cat (derive a r) r'') s) (matches (Cat (derive a r') r'') s)) (orb (matches (Cat (derive a r) r'') s) (matches (Cat (derive a r') r'') s)) *)
    rewrite <- string_assoc.  rewrite <- Hs_s_'.  rewrite <- H01.  auto.
    (* false *)
(* Goal: @eq bool (matches (Cat r (Cat r' r'')) s) false *)
    specialize(divide_Cat_false s (r ++ r') r'' H). intros H0.
(* Goal: @eq bool (matches (Cat r (Cat r' r'')) s) false *)
    case_eq ((r ++ r' ++ r'') ~= s); intro H1.
      (* true *)
(* Goal: @eq bool true false *)
(* Goal: @eq bool false false *)
      specialize(divide_Cat s r (r' ++ r'') H1). intros H2.
(* Goal: @eq bool true false *)
(* Goal: @eq bool false false *)
      destruct H2 as [s0 [s_ [Hs_ [Hrs Hs__]]]].
(* Goal: forall _ : @eq bool (matches (Cat r r') (append s0 s0')) true, @eq bool true false *)
(* Goal: @eq bool false false *)
      specialize (divide_Cat s_ r' r'' Hs__). intros H2.
(* Goal: @eq bool true false *)
(* Goal: @eq bool false false *)
      destruct H2 as [s0' [s0'' [Hs [Hrs' Hrs'']]]].
(* Goal: forall _ : @eq bool (matches (Cat r r') (append s0 s0')) true, @eq bool true false *)
(* Goal: @eq bool false false *)
      specialize (matches_Cat s0 s0' r r' Hrs Hrs'). intros H2.
(* Goal: @eq bool true false *)
(* Goal: @eq bool false false *)
      specialize (matches_Cat (s0 ++ s0')%string s0'' (r ++ r') r'' H2 Hrs''). 
(* Goal: forall _ : @eq bool (matches (Cat (Cat r r') r'') (append (append s0 s0') s0'')) true, @eq bool true false *)
(* Goal: @eq bool false false *)
      intros H3.
(* Goal: @eq bool true false *)
(* Goal: @eq bool false false *)
      replace (((s0 ++ s0') ++ s0'')%string) with s in H3.
(* Goal: @eq bool true false *)
(* Goal: @eq string s (append (append s0 s0') s0'') *)
(* Goal: @eq bool false false *)
      rewrite H in H3.  discriminate H3.
        (* proof for replace *)
(* Goal: @eq bool (orb (matches (Cat (derive a r) r'') s) (matches (Cat (derive a r') r'') s)) (orb (matches (Cat (derive a r) r'') s) (matches (Cat (derive a r') r'') s)) *)
        erewrite string_assoc.  rewrite <- Hs.  rewrite <- Hs_.  auto.
      (* false *)
(* Goal: @eq bool (orb (matches (Cat (derive a r) r'') s) (matches (Cat (derive a r') r'') s)) (orb (matches (Cat (derive a r) r'') s) (matches (Cat (derive a r') r'') s)) *)
      auto.
Qed.

Theorem Cat_assoc : forall r r' r'', (r ++ r') ++ r'' =R= r ++ (r' ++ r'').
Proof.
(* Goal: forall r r' r'' : RegExp, re_eq (Cat (Or r r') r'') (Or (Cat r r'') (Cat r' r'')) *)
  intros r r' r''.  unfold re_eq.  intro s.
(* Goal: @eq bool (matches (Cat (Cat r r') r'') s) (matches (Cat r (Cat r' r'')) s) *)
  eapply Cat_assoc_s.
Qed.

(** ** [Cat] distributes to [Or]. *)

Lemma Cat_left_distr_s : forall s r r' r'', 
  (r ++ (r' || r'')) ~= s = ((r ++ r') || (r ++ r'')) ~= s.
Proof.
(* Goal: forall (s : string) (r r' r'' : RegExp), @eq bool (matches (Cat (Or r r') r'') s) (matches (Or (Cat r r'') (Cat r' r'')) s) *)
  induction s.
    (* s = "" *)
(* Goal: @eq bool (matches (Cat (Or r r') r'') (String a s)) (matches (Or (Cat r r'') (Cat r' r'')) (String a s)) *)
    intros r r' r''.  simpl.  
(* Goal: @eq bool (orb (matches (Cat (derive a r) r'') s) (matches (Cat (derive a r') r'') s)) (orb (matches (Cat (derive a r) r'') s) (matches (Cat (derive a r') r'') s)) *)
    destruct(nu r); destruct(nu r'); destruct(nu r''); auto. 
    (* s = String a s *)
(* Goal: @eq bool (matches (Cat (Or r r') r'') (String a s)) (matches (Or (Cat r r'') (Cat r' r'')) (String a s)) *)
    intros r r' r''.  simpl.  case_eq (nu r); intro nu_r.
      (* nu r = true *)
(* Goal: @eq bool (matches (Or (Cat (derive a r) (Or r' r'')) (Or (derive a r') (derive a r''))) s) (matches (Or (Or (Cat (derive a r) r') (derive a r')) (Or (Cat (derive a r) r'') (derive a r''))) s) *)
(* Goal: @eq bool (matches (Cat (derive a r) (Or r' r'')) s) (matches (Or (Cat (derive a r) r') (Cat (derive a r) r'')) s) *)
      rewrite (matches_Or s (r / a ++ r' || r'') (r' / a || r'' / a)).
(* Goal: @eq bool (orb (matches (Cat (derive a r) (Or r' r'')) s) (matches (Or (derive a r') (derive a r'')) s)) (matches (Or (Or (Cat (derive a r) r') (derive a r')) (Or (Cat (derive a r) r'') (derive a r''))) s) *)
(* Goal: @eq bool (matches (Cat (derive a r) (Or r' r'')) s) (matches (Or (Cat (derive a r) r') (Cat (derive a r) r'')) s) *)
      rewrite (IHs (r / a) r' r'').
(* Goal: @eq bool (orb (matches (Or (Cat (derive a r) r'') (Cat (derive a r') r'')) s) (matches (derive a r'') s)) (matches (Or (Cat (derive a r) r'') (Or (Cat (derive a r') r'') (derive a r''))) s) *)
(* Goal: @eq bool (matches (Cat (Or (derive a r) (derive a r')) r'') s) (matches (Or (Cat (derive a r) r'') (Cat (derive a r') r'')) s) *)
      repeat erewrite matches_Or.  
      destruct ((r / a ++ r') ~= s); destruct ((r / a ++ r'') ~= s);
(* Goal: @eq bool (orb (matches (Cat (derive a r) r'') s) (matches (Cat (derive a r') r'') s)) (orb (matches (Cat (derive a r) r'') s) (matches (Cat (derive a r') r'') s)) *)
      destruct (r' / a ~= s); destruct (r'' / a ~= s); auto.
      (* nu r = false *)
(* Goal: @eq bool (matches (Cat (derive a r) (Or r' r'')) s) (matches (Or (Cat (derive a r) r') (Cat (derive a r) r'')) s) *)
      eapply IHs.
Qed.

Lemma Cat_left_distr : forall r r' r'', 
  (r ++ (r' || r'')) =R= ((r ++ r') || (r ++ r'')).
Proof.
(* Goal: forall r r' r'' : RegExp, re_eq (Cat (Or r r') r'') (Or (Cat r r'') (Cat r' r'')) *)
  unfold re_eq.  intros r r' r'' s.  eapply Cat_left_distr_s.
Qed.

Lemma Cat_right_distr_s : forall s r r' r'', 
  ((r || r') ++ r'') ~= s = ((r ++ r'') || (r' ++ r'')) ~= s.
Proof.
(* Goal: forall (s : string) (r r' r'' : RegExp), @eq bool (matches (Cat (Or r r') r'') s) (matches (Or (Cat r r'') (Cat r' r'')) s) *)
  induction s.
    (* s = "" *)
(* Goal: @eq bool (matches (Cat (Or r r') r'') (String a s)) (matches (Or (Cat r r'') (Cat r' r'')) (String a s)) *)
    intros r r' r''.  simpl.  
(* Goal: @eq bool (orb (matches (Cat (derive a r) r'') s) (matches (Cat (derive a r') r'') s)) (orb (matches (Cat (derive a r) r'') s) (matches (Cat (derive a r') r'') s)) *)
    destruct (nu r); destruct (nu r'); destruct (nu r''); auto.
    (* s = String a s *)
(* Goal: @eq bool (matches (Cat (Or r r') r'') (String a s)) (matches (Or (Cat r r'') (Cat r' r'')) (String a s)) *)
    intros r r' r''.  simpl.  
(* Goal: @eq bool (matches (Cat (Or r r') r'') (String a s)) (matches (Or (Cat r r'') (Cat r' r'')) (String a s)) *)
    case_eq (nu r); intro nu_r; case_eq (nu r'); intro nu_r'; simpl.
      (* true true *)
(* Goal: @eq bool (matches (Or (Cat (Or (derive a r) (derive a r')) r'') (derive a r'')) s) (matches (Or (Cat (derive a r) r'') (Or (Cat (derive a r') r'') (derive a r''))) s) *)
(* Goal: @eq bool (matches (Cat (Or (derive a r) (derive a r')) r'') s) (matches (Or (Cat (derive a r) r'') (Cat (derive a r') r'')) s) *)
      rewrite (matches_Or s (r / a || r' / a ++ r'') (r'' / a)).
(* Goal: @eq bool (matches (Cat (Or (derive a r) (derive a r')) r'') s) (matches (Or (Cat (derive a r) r'') (Cat (derive a r') r'')) s) *)
      rewrite (IHs (r / a) (r' / a) r'').
(* Goal: @eq bool (orb (matches (Or (Cat (derive a r) r'') (Cat (derive a r') r'')) s) (matches (derive a r'') s)) (matches (Or (Cat (derive a r) r'') (Or (Cat (derive a r') r'') (derive a r''))) s) *)
(* Goal: @eq bool (matches (Cat (Or (derive a r) (derive a r')) r'') s) (matches (Or (Cat (derive a r) r'') (Cat (derive a r') r'')) s) *)
      repeat erewrite matches_Or. 
      destruct ((r / a ++ r'') ~= s); destruct ((r' / a ++ r'') ~= s); 
(* Goal: @eq bool (orb (matches (Cat (derive a r) r'') s) (matches (Cat (derive a r') r'') s)) (orb (matches (Cat (derive a r) r'') s) (matches (Cat (derive a r') r'') s)) *)
      destruct (r'' / a ~= s); auto.
      (* true false *)
(* Goal: @eq bool (matches (Or (Cat (Or (derive a r) (derive a r')) r'') (derive a r'')) s) (matches (Or (Cat (derive a r) r'') (Or (Cat (derive a r') r'') (derive a r''))) s) *)
(* Goal: @eq bool (matches (Cat (Or (derive a r) (derive a r')) r'') s) (matches (Or (Cat (derive a r) r'') (Cat (derive a r') r'')) s) *)
      rewrite (matches_Or s (r / a || r' / a ++ r'') (r''/a)).
(* Goal: @eq bool (matches (Cat (Or (derive a r) (derive a r')) r'') s) (matches (Or (Cat (derive a r) r'') (Cat (derive a r') r'')) s) *)
      rewrite (IHs (r/a) (r'/a) r'').
(* Goal: @eq bool (orb (matches (Or (Cat (derive a r) r'') (Cat (derive a r') r'')) s) (matches (derive a r'') s)) (matches (Or (Cat (derive a r) r'') (Or (Cat (derive a r') r'') (derive a r''))) s) *)
(* Goal: @eq bool (matches (Cat (Or (derive a r) (derive a r')) r'') s) (matches (Or (Cat (derive a r) r'') (Cat (derive a r') r'')) s) *)
      repeat erewrite matches_Or. 
      destruct ((r / a ++ r'') ~= s); destruct ((r' / a ++ r'') ~= s); 
(* Goal: @eq bool (orb (matches (Cat (derive a r) r'') s) (matches (Cat (derive a r') r'') s)) (orb (matches (Cat (derive a r) r'') s) (matches (Cat (derive a r') r'') s)) *)
      destruct (r'' / a ~= s); auto.
      (* false true *)
(* Goal: @eq bool (matches (Or (Cat (Or (derive a r) (derive a r')) r'') (derive a r'')) s) (matches (Or (Cat (derive a r) r'') (Or (Cat (derive a r') r'') (derive a r''))) s) *)
(* Goal: @eq bool (matches (Cat (Or (derive a r) (derive a r')) r'') s) (matches (Or (Cat (derive a r) r'') (Cat (derive a r') r'')) s) *)
      rewrite (matches_Or s (r / a || r' / a ++ r'') (r''/a)).
(* Goal: @eq bool (matches (Cat (Or (derive a r) (derive a r')) r'') s) (matches (Or (Cat (derive a r) r'') (Cat (derive a r') r'')) s) *)
      rewrite (IHs (r/a) (r'/a) r'').
(* Goal: @eq bool (orb (matches (Or (Cat (derive a r) r'') (Cat (derive a r') r'')) s) (matches (derive a r'') s)) (matches (Or (Cat (derive a r) r'') (Or (Cat (derive a r') r'') (derive a r''))) s) *)
(* Goal: @eq bool (matches (Cat (Or (derive a r) (derive a r')) r'') s) (matches (Or (Cat (derive a r) r'') (Cat (derive a r') r'')) s) *)
      repeat erewrite matches_Or.
      destruct ((r / a ++ r'') ~= s); destruct ((r' / a ++ r'') ~= s); 
(* Goal: @eq bool (orb (matches (Cat (derive a r) r'') s) (matches (Cat (derive a r') r'') s)) (orb (matches (Cat (derive a r) r'') s) (matches (Cat (derive a r') r'') s)) *)
      destruct (r'' / a ~= s); auto.
      (* false false *)
(* Goal: @eq bool (matches (Cat (Or (derive a r) (derive a r')) r'') s) (matches (Or (Cat (derive a r) r'') (Cat (derive a r') r'')) s) *)
      rewrite (IHs (r/a) (r'/a) r'').
(* Goal: @eq bool (orb (matches (Cat (derive a r) r'') s) (matches (Cat (derive a r') r'') s)) (orb (matches (Cat (derive a r) r'') s) (matches (Cat (derive a r') r'') s)) *)
      erewrite matches_Or.  auto.
Qed.

Lemma Cat_right_distr : forall r r' r'', 
  ((r || r') ++ r'') =R= ((r ++ r'') || (r' ++ r'')).
Proof.
(* Goal: forall r r' r'' : RegExp, re_eq (Cat (Or r r') r'') (Or (Cat r r'') (Cat r' r'')) *)
  unfold re_eq.  intros r r' r'' s.  eapply Cat_right_distr_s.
Qed.
