坚持关于正则表达式的简单证明
Stuck on a simple proof about regular expressions
我正在尝试使用 Coq 将正则表达式 (RE) 的某些属性形式化。但是,我有一些麻烦来证明一个相当简单的 属性:
For all strings s, if s is in the language of (epsilon)* RE, then s =
"", where epsilon and * denotes the empty string RE and Kleene star
operation.
这似乎是归纳/反转策略的明显应用,但我无法使其发挥作用。
带有问题引理的最小工作代码在下面gist。
任何关于我应该如何进行的提示都将不胜感激。
编辑:
我的一个尝试是这样的:
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
这让我有了以下目标:
s' : string
H4 : s' <<- (#1 ^*)
============================
s' = ""
至少在我看来,使用归纳似乎可以完成证明,因为我可以在归纳假设中使用 H4 来完成证明,但是当我使用
开始证明时
induction H
而不是
inverts* H
我有一些(至少对我而言)毫无意义的目标。在 Idris / Agda 中,这种证明只是在 s <<- (#1 ^*) 的结构上进行模式匹配和递归。我的观点是如何在 Coq 中进行这种递归。
我稍微修改了你的 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
create a new hypothesis Heqr
which, combined with inversion
将有助于摆脱无法提供此证明的情况(事实上所有情况减去^*
在结论中的情况)。
不幸的是,这种推理路径不适用于您对 in_regex
谓词的定义,因为它会为归纳假设创建一个不可满足的条件。这就是为什么我也修改了你的归纳谓词。
修改后的归纳法试图给出一个更基本的定义(e ^*)
。在语义上,我认为这是等价的。
我有兴趣阅读原始问题的证明。
这是原始问题的一种可能解决方案:
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.
主要思想是在上下文中引入一个类似于典型 Idris 证明中的递归调用的术语。 remember
和 dependent induction
的方法效果不佳(不修改 in_regex
),因为它们引入了不可能满足的方程作为归纳假设的前提。
注意:检查这个引理可能需要一段时间(在 Coq 8.5pl3 下我的机器上大约需要 40 秒)。我认为这是因为 inversion
策略倾向于生成大证明项。
这个问题困扰了我一个星期,终于找到了一个我觉得优雅的解决方案。
我已经读过,当归纳原理不适合您的需要时,您可以编写并证明另一个更适合您的问题的原理。这就是我在这种情况下所做的。我们想要的是使用 中给出的更自然的定义时获得的那个。通过这样做,我们可以保持相同的定义(例如,如果改变它意味着太多的改变)并且更容易推理它。
这是归纳原理的证明(我使用一个部分来精确指定隐式参数,否则我会观察到它们的奇怪行为,但这里根本不需要部分机制)。
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.
我正在尝试使用 Coq 将正则表达式 (RE) 的某些属性形式化。但是,我有一些麻烦来证明一个相当简单的 属性:
For all strings s, if s is in the language of (epsilon)* RE, then s = "", where epsilon and * denotes the empty string RE and Kleene star operation.
这似乎是归纳/反转策略的明显应用,但我无法使其发挥作用。
带有问题引理的最小工作代码在下面gist。 任何关于我应该如何进行的提示都将不胜感激。
编辑:
我的一个尝试是这样的:
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
这让我有了以下目标:
s' : string
H4 : s' <<- (#1 ^*)
============================
s' = ""
至少在我看来,使用归纳似乎可以完成证明,因为我可以在归纳假设中使用 H4 来完成证明,但是当我使用
开始证明时induction H
而不是
inverts* H
我有一些(至少对我而言)毫无意义的目标。在 Idris / Agda 中,这种证明只是在 s <<- (#1 ^*) 的结构上进行模式匹配和递归。我的观点是如何在 Coq 中进行这种递归。
我稍微修改了你的 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
create a new hypothesisHeqr
which, combined withinversion
将有助于摆脱无法提供此证明的情况(事实上所有情况减去^*
在结论中的情况)。不幸的是,这种推理路径不适用于您对
in_regex
谓词的定义,因为它会为归纳假设创建一个不可满足的条件。这就是为什么我也修改了你的归纳谓词。修改后的归纳法试图给出一个更基本的定义
(e ^*)
。在语义上,我认为这是等价的。
我有兴趣阅读原始问题的证明。
这是原始问题的一种可能解决方案:
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.
主要思想是在上下文中引入一个类似于典型 Idris 证明中的递归调用的术语。 remember
和 dependent induction
的方法效果不佳(不修改 in_regex
),因为它们引入了不可能满足的方程作为归纳假设的前提。
注意:检查这个引理可能需要一段时间(在 Coq 8.5pl3 下我的机器上大约需要 40 秒)。我认为这是因为 inversion
策略倾向于生成大证明项。
这个问题困扰了我一个星期,终于找到了一个我觉得优雅的解决方案。
我已经读过,当归纳原理不适合您的需要时,您可以编写并证明另一个更适合您的问题的原理。这就是我在这种情况下所做的。我们想要的是使用
这是归纳原理的证明(我使用一个部分来精确指定隐式参数,否则我会观察到它们的奇怪行为,但这里根本不需要部分机制)。
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
产生了
与自然定义一样,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.