软件基础：weak_pumping 引理证明

Question

继续我在软件基础方面的工作，我遇到了 weak_pumping 引理。我设法解决了几乎所有问题，但找不到 MStarApp 案例的解决方案。

这是引理：

  s =~ re ->
  pumping_constant re <= length s ->
  exists s1 s2 s3,
    s = s1 ++ s2 ++ s3 /\
    s2 <> [] /\
    forall m, s1 ++ napp m s2 ++ s3 =~ re.

(** You are to fill in the proof. Several of the lemmas about
    [le] that were in an optional exercise earlier in this chapter
    may be useful. *)
Proof.
  intros T re s Hmatch.
  induction Hmatch
    as [ | x | s1 re1 s2 re2 Hmatch1 IH1 Hmatch2 IH2
       | s1 re1 re2 Hmatch IH | re1 s2 re2 Hmatch IH
       | re | s1 s2 re Hmatch1 IH1 Hmatch2 IH2 ].

除了最后一个，我已经设法解决了所有案例。这是当前状态：

1 subgoal (ID 918)
  
  T : Type
  s1, s2 : list T
  re : reg_exp T
  Hmatch1 : s1 =~ re
  Hmatch2 : s2 =~ Star re
  IH1 : pumping_constant re <= length s1 ->
        exists s2 s3 s4 : list T,
          s1 = s2 ++ s3 ++ s4 /\
          s3 <> [ ] /\ (forall m : nat, s2 ++ napp m s3 ++ s4 =~ re)
  IH2 : pumping_constant (Star re) <= length s2 ->
        exists s1 s3 s4 : list T,
          s2 = s1 ++ s3 ++ s4 /\
          s3 <> [ ] /\ (forall m : nat, s1 ++ napp m s3 ++ s4 =~ Star re)
  H : pumping_constant (Star re) <= length s1 + length s2
  ============================
  exists s0 s4 s5 : list T,
    s1 ++ s2 = s0 ++ s4 ++ s5 /\
    s4 <> [ ] /\ (forall m : nat, s0 ++ napp m s4 ++ s5 =~ Star re)

在我看来，如果我能找到一种方法将 H 拆分为 pumping_constant re <= length s1 \/ pumping_constant (Star re) <= length s2，那么我就有了前进的方向（通过将 H 拆分为 H1 和H2 并将相关的 IHk 应用到匹配的 Hk，然后进行一个 destruct、三个 exists，依此类推。

但我找不到允许我按照建议拆分 H 的引理。

我还有什么可以做的吗？

谢谢

Answer 1

在其中一种情况下，尝试破坏 s1 并再次查看引理 napp_star。

软件基础：weak_pumping 引理证明

Software Foundations: weak_pumping lemma proof

coq

coq-tactic