Stuck on simple proof of regular expressions

Question

I am trying to formalize some regular expression (RE) properties with Coq. But I have some problems to prove a fairly simple property:

For all strings s, if s is in the language (epsilon) * RE, then s = "", where epsilon and * denotes the empty string RE and Kleene star operations.

This seems like an obvious use of induction / inversion tactics, but I couldn't get it to work.

Minimal working code with a problematic lemma is provided in gist . Any advice on how to proceed should be appreciated.

EDIT

One of my attempts was something like this:

Lemma star_lemma : forall s, s <<- (#1 ^*) -> s = "".
Proof.  
  intros s H.
  inverts* H.
  inverts* H2.
  inverts* H1.
  inverts* H1.
  inverts* H2.
  simpl in *.
  -- stuck here

which leave me with the following purpose:

s' : string
H4 : s' <<- (#1 ^*)
============================
s' = ""

, , , H4 , , ,

induction H

inverts* H

( ) . / s < - (# 1 ^ *). , ​​ Coq.

Answer 1

:

Lemma star_lemma : forall s,
    s <<- (#1 ^*) -> s = "".
Proof.
  refine (fix star_lemma s prf {struct prf} : s = "" := _).
  inversion_clear prf; subst.
  inversion_clear H; subst.
  - now inversion H0.
  - inversion_clear H0; subst. inversion_clear H; subst.
    rewrite (star_lemma s' H1).
    reflexivity.
Qed.

, , . remember dependent induction ( in_regex), .

. ( 40 Coq 8.5pl3). , , inversion .

Answer 2

in_regex:

Inductive in_regex : string -> regex -> Prop :=
| InEps
  : "" <<- #1
| InChr
  : forall c
  , (String c EmptyString) <<- ($ c)
| InCat
  :  forall e e' s s' s1
  ,  s <<- e
  -> s' <<- e'
  -> s1 = s ++ s'
  -> s1 <<- (e @ e')
| InLeft
  :  forall s e e'
  ,  s <<- e
  -> s <<- (e :+: e')
| InRight
  :  forall s' e e'
  ,  s' <<- e'
  -> s' <<- (e :+: e')
| InStarLeft
  : forall e
  , "" <<- (e ^*)
| InStarRight
  :  forall s s' e
  ,  s <<- e
  -> s' <<- (e ^*)
  -> (s ++ s') <<- (e ^*)
where "s '<<-' e" := (in_regex s e).

:

Lemma star_lemma : forall s, s <<- (#1 ^*) -> s = "".
Proof.
  intros s H.
  remember (#1 ^*) as r.
  induction H; inversion Heqr; clear Heqr; trivial.
  subst e.
  rewrite IHin_regex2; trivial.
  inversion H; trivial.
Qed.

.

• H. : s <<- (#1 ^*), ...

• remember Heqr, inversion , ( , ^* .

• , , in_regex, . .

• (e ^*). , , .

.

Answer 3

, , .

, , , , . , . , , . , ( , ), .

( , , , ).

Section induction_principle.

Context (P : string -> regex -> Prop)
  (H_InEps : P "" #1)
  (H_InChr : forall c, P (String c "") ($ c))
  (H_InCat : forall {e e' s s' s1}, s <<- e -> P s e -> s' <<- e' ->
    P s' e' -> s1 = s ++ s' -> P s1 (e @ e'))
  (H_InLeft : forall {s e e'}, s <<- e -> P s e -> P s (e :+: e'))
  (H_InRight : forall {s' e e'}, s' <<- e' -> P s' e' -> P s' (e :+: e'))
  (H_InStar_Eps : forall e, P "" (e ^*))
  (H_InStar_Cat : forall {s1 s2 e}, s1 <<- e -> s2 <<- (e ^*) ->
    P s1 e -> P s2 (e ^*) -> P (s1++s2) (e ^*)).

Arguments H_InCat {_ _ _ _ _} _ _ _ _ _.
Arguments H_InLeft {_ _ _} _ _.
Arguments H_InRight {_ _ _} _ _.
Arguments H_InStar_Cat {_ _ _} _ _ _ _.

Definition in_regex_ind2 : forall (s : string) (r : regex), s <<- r -> P s r.
Proof.
  refine (fix in_regex_ind2 {s r} prf {struct prf} : P s r :=
    match prf with
    | InEps => H_InEps
    | InChr c => H_InChr c
    | InCat prf1 prf2 eq1 =>
        H_InCat prf1 (in_regex_ind2 prf1) prf2 (in_regex_ind2 prf2) eq1
    | InLeft _ prf => H_InLeft prf (in_regex_ind2 prf)
    | InRight _ prf => H_InRight prf (in_regex_ind2 prf)
    | InStar prf => _
    end).
  inversion prf; subst.
  - inversion H1. apply H_InStar_Eps.
  - inversion H1; subst.
    apply H_InStar_Cat; try assumption; apply in_regex_ind2; assumption.
Qed.

End induction_principle.

, Qed (, - inversion, , ), 1 (, , ).

star_lemma , ( remember), .

Lemma star_lemma : forall s, s <<- (#1 ^*) -> s = "".
Proof.
  intros s H. remember (#1 ^*) as r.
  induction H using in_regex_ind2; try discriminate.
  - reflexivity.
  - inversion Heqr; subst.
    inversion H. rewrite IHin_regex2 by reflexivity. reflexivity.
Qed.