internlm/Lean-Github huggingface dataset:
Theorem: Regex.NFA.pathToNext_of_matches.alternateLeft
Proof state before:
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Data.Expr
nfa'✝ : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq✝ : nfa.pushRegex next (r₁.alternate r₂) = nfa'✝
ih :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {nfa' : { nfa' // nfa.nodes.size < nfa'.nodes.size }},
    nfa.pushRegex next r₁ = nfa' → (↑nfa').pathToNext (↑next) nfa.nodes.size (↑(↑nfa').start) cs
nfa₁ : { nfa' // nfa.nodes.size < nfa'.nodes.size }
start₁ : Fin (↑nfa₁).nodes.size
nfa₂ : { nfa' // (↑nfa₁).nodes.size < nfa'.nodes.size }
start₂ : Fin (↑nfa₂).nodes.size
inBounds✝ : (Node.split ↑start₁ ↑start₂).inBounds ((↑nfa₂).nodes.size + 1)
nfa' : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑nfa').nodes.size
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
a✝ : start₂ = (↑nfa₂).start
eq₅ : nfa' = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds✝
eq : nfa'✝ = ⟨↑nfa', property⟩
this : (↑nfa₁).pathToNext (↑next) nfa.nodes.size (↑(↑nfa₁).start) cs
⊢ ∀ (i : ℕ),
    nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₁).nodes.size), ∃ (h' : i < (↑nfa').nodes.size), (↑nfa₁)[i] = (↑nfa')[i]
Tactic:
intro i _ h₂
Proof state after:
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Data.Expr
nfa'✝ : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq✝ : nfa.pushRegex next (r₁.alternate r₂) = nfa'✝
ih :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {nfa' : { nfa' // nfa.nodes.size < nfa'.nodes.size }},
    nfa.pushRegex next r₁ = nfa' → (↑nfa').pathToNext (↑next) nfa.nodes.size (↑(↑nfa').start) cs
nfa₁ : { nfa' // nfa.nodes.size < nfa'.nodes.size }
start₁ : Fin (↑nfa₁).nodes.size
nfa₂ : { nfa' // (↑nfa₁).nodes.size < nfa'.nodes.size }
start₂ : Fin (↑nfa₂).nodes.size
inBounds✝ : (Node.split ↑start₁ ↑start₂).inBounds ((↑nfa₂).nodes.size + 1)
nfa' : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑nfa').nodes.size
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
a✝ : start₂ = (↑nfa₂).start
eq₅ : nfa' = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds✝
eq : nfa'✝ = ⟨↑nfa', property⟩
this : (↑nfa₁).pathToNext (↑next) nfa.nodes.size (↑(↑nfa₁).start) cs
i : ℕ
h₁✝ : nfa.nodes.size ≤ i
h₂ : i < (↑nfa₁).nodes.size
⊢ ∃ (h' : i < (↑nfa').nodes.size), (↑nfa₁)[i] = (↑nfa')[i]
Theorem: Regex.NFA.pathToNext_of_matches.alternateLeft
Proof state before:
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Data.Expr
nfa'✝ : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq✝ : nfa.pushRegex next (r₁.alternate r₂) = nfa'✝
ih :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {nfa' : { nfa' // nfa.nodes.size < nfa'.nodes.size }},
    nfa.pushRegex next r₁ = nfa' → (↑nfa').pathToNext (↑next) nfa.nodes.size (↑(↑nfa').start) cs
nfa₁ : { nfa' // nfa.nodes.size < nfa'.nodes.size }
start₁ : Fin (↑nfa₁).nodes.size
nfa₂ : { nfa' // (↑nfa₁).nodes.size < nfa'.nodes.size }
start₂ : Fin (↑nfa₂).nodes.size
inBounds✝ : (Node.split ↑start₁ ↑start₂).inBounds ((↑nfa₂).nodes.size + 1)
nfa' : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑nfa').nodes.size
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
a✝ : start₂ = (↑nfa₂).start
eq₅ : nfa' = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds✝
eq : nfa'✝ = ⟨↑nfa', property⟩
this : (↑nfa₁).pathToNext (↑next) nfa.nodes.size (↑(↑nfa₁).start) cs
i : ℕ
h₁✝ : nfa.nodes.size ≤ i
h₂ : i < (↑nfa₁).nodes.size
⊢ ∃ (h' : i < (↑nfa').nodes.size), (↑nfa₁)[i] = (↑nfa')[i]
Tactic:
have lt₂ : i < nfa₂.val.nodes.size := Nat.lt_trans h₂ nfa₂.property
Proof state after:
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Data.Expr
nfa'✝ : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq✝ : nfa.pushRegex next (r₁.alternate r₂) = nfa'✝
ih :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {nfa' : { nfa' // nfa.nodes.size < nfa'.nodes.size }},
    nfa.pushRegex next r₁ = nfa' → (↑nfa').pathToNext (↑next) nfa.nodes.size (↑(↑nfa').start) cs
nfa₁ : { nfa' // nfa.nodes.size < nfa'.nodes.size }
start₁ : Fin (↑nfa₁).nodes.size
nfa₂ : { nfa' // (↑nfa₁).nodes.size < nfa'.nodes.size }
start₂ : Fin (↑nfa₂).nodes.size
inBounds✝ : (Node.split ↑start₁ ↑start₂).inBounds ((↑nfa₂).nodes.size + 1)
nfa' : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑nfa').nodes.size
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
a✝ : start₂ = (↑nfa₂).start
eq₅ : nfa' = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds✝
eq : nfa'✝ = ⟨↑nfa', property⟩
this : (↑nfa₁).pathToNext (↑next) nfa.nodes.size (↑(↑nfa₁).start) cs
i : ℕ
h₁✝ : nfa.nodes.size ≤ i
h₂ : i < (↑nfa₁).nodes.size
lt₂ : i < (↑nfa₂).nodes.size
⊢ ∃ (h' : i < (↑nfa').nodes.size), (↑nfa₁)[i] = (↑nfa')[i]
Theorem: Regex.NFA.pathToNext_of_matches.alternateLeft
Proof state before:
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Data.Expr
nfa'✝ : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq✝ : nfa.pushRegex next (r₁.alternate r₂) = nfa'✝
ih :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {nfa' : { nfa' // nfa.nodes.size < nfa'.nodes.size }},
    nfa.pushRegex next r₁ = nfa' → (↑nfa').pathToNext (↑next) nfa.nodes.size (↑(↑nfa').start) cs
nfa₁ : { nfa' // nfa.nodes.size < nfa'.nodes.size }
start₁ : Fin (↑nfa₁).nodes.size
nfa₂ : { nfa' // (↑nfa₁).nodes.size < nfa'.nodes.size }
start₂ : Fin (↑nfa₂).nodes.size
inBounds✝ : (Node.split ↑start₁ ↑start₂).inBounds ((↑nfa₂).nodes.size + 1)
nfa' : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑nfa').nodes.size
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
a✝ : start₂ = (↑nfa₂).start
eq₅ : nfa' = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds✝
eq : nfa'✝ = ⟨↑nfa', property⟩
this : (↑nfa₁).pathToNext (↑next) nfa.nodes.size (↑(↑nfa₁).start) cs
i : ℕ
h₁✝ : nfa.nodes.size ≤ i
h₂ : i < (↑nfa₁).nodes.size
lt₂ : i < (↑nfa₂).nodes.size
⊢ ∃ (h' : i < (↑nfa').nodes.size), (↑nfa₁)[i] = (↑nfa')[i]
Tactic:
have : i < nfa'.val.nodes.size := Nat.lt_trans lt₂ nfa'.property
Proof state after:
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Data.Expr
nfa'✝ : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq✝ : nfa.pushRegex next (r₁.alternate r₂) = nfa'✝
ih :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {nfa' : { nfa' // nfa.nodes.size < nfa'.nodes.size }},
    nfa.pushRegex next r₁ = nfa' → (↑nfa').pathToNext (↑next) nfa.nodes.size (↑(↑nfa').start) cs
nfa₁ : { nfa' // nfa.nodes.size < nfa'.nodes.size }
start₁ : Fin (↑nfa₁).nodes.size
nfa₂ : { nfa' // (↑nfa₁).nodes.size < nfa'.nodes.size }
start₂ : Fin (↑nfa₂).nodes.size
inBounds✝ : (Node.split ↑start₁ ↑start₂).inBounds ((↑nfa₂).nodes.size + 1)
nfa' : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑nfa').nodes.size
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
a✝ : start₂ = (↑nfa₂).start
eq₅ : nfa' = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds✝
eq : nfa'✝ = ⟨↑nfa', property⟩
this✝ : (↑nfa₁).pathToNext (↑next) nfa.nodes.size (↑(↑nfa₁).start) cs
i : ℕ
h₁✝ : nfa.nodes.size ≤ i
h₂ : i < (↑nfa₁).nodes.size
lt₂ : i < (↑nfa₂).nodes.size
this : i < (↑nfa').nodes.size
⊢ ∃ (h' : i < (↑nfa').nodes.size), (↑nfa₁)[i] = (↑nfa')[i]
Theorem: Regex.NFA.pathToNext_of_matches.alternateLeft
Proof state before:
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Data.Expr
nfa'✝ : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq✝ : nfa.pushRegex next (r₁.alternate r₂) = nfa'✝
ih :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {nfa' : { nfa' // nfa.nodes.size < nfa'.nodes.size }},
    nfa.pushRegex next r₁ = nfa' → (↑nfa').pathToNext (↑next) nfa.nodes.size (↑(↑nfa').start) cs
nfa₁ : { nfa' // nfa.nodes.size < nfa'.nodes.size }
start₁ : Fin (↑nfa₁).nodes.size
nfa₂ : { nfa' // (↑nfa₁).nodes.size < nfa'.nodes.size }
start₂ : Fin (↑nfa₂).nodes.size
inBounds✝ : (Node.split ↑start₁ ↑start₂).inBounds ((↑nfa₂).nodes.size + 1)
nfa' : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑nfa').nodes.size
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
a✝ : start₂ = (↑nfa₂).start
eq₅ : nfa' = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds✝
eq : nfa'✝ = ⟨↑nfa', property⟩
this✝ : (↑nfa₁).pathToNext (↑next) nfa.nodes.size (↑(↑nfa₁).start) cs
i : ℕ
h₁✝ : nfa.nodes.size ≤ i
h₂ : i < (↑nfa₁).nodes.size
lt₂ : i < (↑nfa₂).nodes.size
this : i < (↑nfa').nodes.size
⊢ ∃ (h' : i < (↑nfa').nodes.size), (↑nfa₁)[i] = (↑nfa')[i]
Tactic:
exists this
Proof state after:
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Data.Expr
nfa'✝ : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq✝ : nfa.pushRegex next (r₁.alternate r₂) = nfa'✝
ih :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {nfa' : { nfa' // nfa.nodes.size < nfa'.nodes.size }},
    nfa.pushRegex next r₁ = nfa' → (↑nfa').pathToNext (↑next) nfa.nodes.size (↑(↑nfa').start) cs
nfa₁ : { nfa' // nfa.nodes.size < nfa'.nodes.size }
start₁ : Fin (↑nfa₁).nodes.size
nfa₂ : { nfa' // (↑nfa₁).nodes.size < nfa'.nodes.size }
start₂ : Fin (↑nfa₂).nodes.size
inBounds✝ : (Node.split ↑start₁ ↑start₂).inBounds ((↑nfa₂).nodes.size + 1)
nfa' : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑nfa').nodes.size
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
a✝ : start₂ = (↑nfa₂).start
eq₅ : nfa' = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds✝
eq : nfa'✝ = ⟨↑nfa', property⟩
this✝ : (↑nfa₁).pathToNext (↑next) nfa.nodes.size (↑(↑nfa₁).start) cs
i : ℕ
h₁✝ : nfa.nodes.size ≤ i
h₂ : i < (↑nfa₁).nodes.size
lt₂ : i < (↑nfa₂).nodes.size
this : i < (↑nfa').nodes.size
⊢ (↑nfa₁)[i] = (↑nfa')[i]
Theorem: Regex.NFA.pathToNext_of_matches.alternateLeft
Proof state before:
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Data.Expr
nfa'✝ : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq✝ : nfa.pushRegex next (r₁.alternate r₂) = nfa'✝
ih :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {nfa' : { nfa' // nfa.nodes.size < nfa'.nodes.size }},
    nfa.pushRegex next r₁ = nfa' → (↑nfa').pathToNext (↑next) nfa.nodes.size (↑(↑nfa').start) cs
nfa₁ : { nfa' // nfa.nodes.size < nfa'.nodes.size }
start₁ : Fin (↑nfa₁).nodes.size
nfa₂ : { nfa' // (↑nfa₁).nodes.size < nfa'.nodes.size }
start₂ : Fin (↑nfa₂).nodes.size
inBounds✝ : (Node.split ↑start₁ ↑start₂).inBounds ((↑nfa₂).nodes.size + 1)
nfa' : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑nfa').nodes.size
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
a✝ : start₂ = (↑nfa₂).start
eq₅ : nfa' = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds✝
eq : nfa'✝ = ⟨↑nfa', property⟩
this✝ : (↑nfa₁).pathToNext (↑next) nfa.nodes.size (↑(↑nfa₁).start) cs
i : ℕ
h₁✝ : nfa.nodes.size ≤ i
h₂ : i < (↑nfa₁).nodes.size
lt₂ : i < (↑nfa₂).nodes.size
this : i < (↑nfa').nodes.size
⊢ (↑nfa₁)[i] = (↑nfa')[i]
Tactic:
simp [eq₅]
Proof state after:
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Data.Expr
nfa'✝ : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq✝ : nfa.pushRegex next (r₁.alternate r₂) = nfa'✝
ih :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {nfa' : { nfa' // nfa.nodes.size < nfa'.nodes.size }},
    nfa.pushRegex next r₁ = nfa' → (↑nfa').pathToNext (↑next) nfa.nodes.size (↑(↑nfa').start) cs
nfa₁ : { nfa' // nfa.nodes.size < nfa'.nodes.size }
start₁ : Fin (↑nfa₁).nodes.size
nfa₂ : { nfa' // (↑nfa₁).nodes.size < nfa'.nodes.size }
start₂ : Fin (↑nfa₂).nodes.size
inBounds✝ : (Node.split ↑start₁ ↑start₂).inBounds ((↑nfa₂).nodes.size + 1)
nfa' : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑nfa').nodes.size
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
a✝ : start₂ = (↑nfa₂).start
eq₅ : nfa' = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds✝
eq : nfa'✝ = ⟨↑nfa', property⟩
this✝ : (↑nfa₁).pathToNext (↑next) nfa.nodes.size (↑(↑nfa₁).start) cs
i : ℕ
h₁✝ : nfa.nodes.size ≤ i
h₂ : i < (↑nfa₁).nodes.size
lt₂ : i < (↑nfa₂).nodes.size
this : i < (↑nfa').nodes.size
⊢ (↑nfa₁)[i] = (↑((↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds✝))[i]
Theorem: Regex.NFA.pathToNext_of_matches.alternateLeft
Proof state before:
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Data.Expr
nfa'✝ : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq✝ : nfa.pushRegex next (r₁.alternate r₂) = nfa'✝
ih :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {nfa' : { nfa' // nfa.nodes.size < nfa'.nodes.size }},
    nfa.pushRegex next r₁ = nfa' → (↑nfa').pathToNext (↑next) nfa.nodes.size (↑(↑nfa').start) cs
nfa₁ : { nfa' // nfa.nodes.size < nfa'.nodes.size }
start₁ : Fin (↑nfa₁).nodes.size
nfa₂ : { nfa' // (↑nfa₁).nodes.size < nfa'.nodes.size }
start₂ : Fin (↑nfa₂).nodes.size
inBounds✝ : (Node.split ↑start₁ ↑start₂).inBounds ((↑nfa₂).nodes.size + 1)
nfa' : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑nfa').nodes.size
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
a✝ : start₂ = (↑nfa₂).start
eq₅ : nfa' = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds✝
eq : nfa'✝ = ⟨↑nfa', property⟩
this✝ : (↑nfa₁).pathToNext (↑next) nfa.nodes.size (↑(↑nfa₁).start) cs
i : ℕ
h₁✝ : nfa.nodes.size ≤ i
h₂ : i < (↑nfa₁).nodes.size
lt₂ : i < (↑nfa₂).nodes.size
this : i < (↑nfa').nodes.size
⊢ (↑nfa₁)[i] = (↑((↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds✝))[i]
Tactic:
rw [pushNode_get_lt _ lt₂]
Proof state after:
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Data.Expr
nfa'✝ : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq✝ : nfa.pushRegex next (r₁.alternate r₂) = nfa'✝
ih :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {nfa' : { nfa' // nfa.nodes.size < nfa'.nodes.size }},
    nfa.pushRegex next r₁ = nfa' → (↑nfa').pathToNext (↑next) nfa.nodes.size (↑(↑nfa').start) cs
nfa₁ : { nfa' // nfa.nodes.size < nfa'.nodes.size }
start₁ : Fin (↑nfa₁).nodes.size
nfa₂ : { nfa' // (↑nfa₁).nodes.size < nfa'.nodes.size }
start₂ : Fin (↑nfa₂).nodes.size
inBounds✝ : (Node.split ↑start₁ ↑start₂).inBounds ((↑nfa₂).nodes.size + 1)
nfa' : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑nfa').nodes.size
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
a✝ : start₂ = (↑nfa₂).start
eq₅ : nfa' = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds✝
eq : nfa'✝ = ⟨↑nfa', property⟩
this✝ : (↑nfa₁).pathToNext (↑next) nfa.nodes.size (↑(↑nfa₁).start) cs
i : ℕ
h₁✝ : nfa.nodes.size ≤ i
h₂ : i < (↑nfa₁).nodes.size
lt₂ : i < (↑nfa₂).nodes.size
this : i < (↑nfa').nodes.size
⊢ (↑nfa₁)[i] = (↑nfa₂)[i]
Theorem: Regex.NFA.pathToNext_of_matches.alternateLeft
Proof state before:
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Data.Expr
nfa'✝ : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq✝ : nfa.pushRegex next (r₁.alternate r₂) = nfa'✝
ih :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {nfa' : { nfa' // nfa.nodes.size < nfa'.nodes.size }},
    nfa.pushRegex next r₁ = nfa' → (↑nfa').pathToNext (↑next) nfa.nodes.size (↑(↑nfa').start) cs
nfa₁ : { nfa' // nfa.nodes.size < nfa'.nodes.size }
start₁ : Fin (↑nfa₁).nodes.size
nfa₂ : { nfa' // (↑nfa₁).nodes.size < nfa'.nodes.size }
start₂ : Fin (↑nfa₂).nodes.size
inBounds✝ : (Node.split ↑start₁ ↑start₂).inBounds ((↑nfa₂).nodes.size + 1)
nfa' : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑nfa').nodes.size
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
a✝ : start₂ = (↑nfa₂).start
eq₅ : nfa' = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds✝
eq : nfa'✝ = ⟨↑nfa', property⟩
this✝ : (↑nfa₁).pathToNext (↑next) nfa.nodes.size (↑(↑nfa₁).start) cs
i : ℕ
h₁✝ : nfa.nodes.size ≤ i
h₂ : i < (↑nfa₁).nodes.size
lt₂ : i < (↑nfa₂).nodes.size
this : i < (↑nfa').nodes.size
⊢ (↑nfa₁)[i] = (↑nfa₂)[i]
Tactic:
rw [pushRegex_get_lt eq₃.symm _ h₂]
Proof state after:
no goals
Theorem: Regex.NFA.pathToNext_of_matches.alternateLeft
Proof state before:
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Data.Expr
nfa'✝ : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq✝ : nfa.pushRegex next (r₁.alternate r₂) = nfa'✝
ih :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {nfa' : { nfa' // nfa.nodes.size < nfa'.nodes.size }},
    nfa.pushRegex next r₁ = nfa' → (↑nfa').pathToNext (↑next) nfa.nodes.size (↑(↑nfa').start) cs
nfa₁ : { nfa' // nfa.nodes.size < nfa'.nodes.size }
start₁ : Fin (↑nfa₁).nodes.size
nfa₂ : { nfa' // (↑nfa₁).nodes.size < nfa'.nodes.size }
start₂ : Fin (↑nfa₂).nodes.size
inBounds✝ : (Node.split ↑start₁ ↑start₂).inBounds ((↑nfa₂).nodes.size + 1)
nfa' : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑nfa').nodes.size
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
a✝ : start₂ = (↑nfa₂).start
eq₅ : nfa' = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds✝
eq : nfa'✝ = ⟨↑nfa', property⟩
this✝ : (↑nfa₁).pathToNext (↑next) nfa.nodes.size (↑(↑nfa₁).start) cs
this : (↑nfa').pathToNext (↑next) nfa.nodes.size (↑(↑nfa₁).start) cs
⊢ nfa.nodes.size ≤ ↑(↑nfa').start
Tactic:
rw [eq₅]
Proof state after:
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Data.Expr
nfa'✝ : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq✝ : nfa.pushRegex next (r₁.alternate r₂) = nfa'✝
ih :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {nfa' : { nfa' // nfa.nodes.size < nfa'.nodes.size }},
    nfa.pushRegex next r₁ = nfa' → (↑nfa').pathToNext (↑next) nfa.nodes.size (↑(↑nfa').start) cs
nfa₁ : { nfa' // nfa.nodes.size < nfa'.nodes.size }
start₁ : Fin (↑nfa₁).nodes.size
nfa₂ : { nfa' // (↑nfa₁).nodes.size < nfa'.nodes.size }
start₂ : Fin (↑nfa₂).nodes.size
inBounds✝ : (Node.split ↑start₁ ↑start₂).inBounds ((↑nfa₂).nodes.size + 1)
nfa' : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑nfa').nodes.size
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
a✝ : start₂ = (↑nfa₂).start
eq₅ : nfa' = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds✝
eq : nfa'✝ = ⟨↑nfa', property⟩
this✝ : (↑nfa₁).pathToNext (↑next) nfa.nodes.size (↑(↑nfa₁).start) cs
this : (↑nfa').pathToNext (↑next) nfa.nodes.size (↑(↑nfa₁).start) cs
⊢ nfa.nodes.size ≤ ↑(↑((↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds✝)).start
Theorem: Regex.NFA.pathToNext_of_matches.alternateLeft
Proof state before:
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Data.Expr
nfa'✝ : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq✝ : nfa.pushRegex next (r₁.alternate r₂) = nfa'✝
ih :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {nfa' : { nfa' // nfa.nodes.size < nfa'.nodes.size }},
    nfa.pushRegex next r₁ = nfa' → (↑nfa').pathToNext (↑next) nfa.nodes.size (↑(↑nfa').start) cs
nfa₁ : { nfa' // nfa.nodes.size < nfa'.nodes.size }
start₁ : Fin (↑nfa₁).nodes.size
nfa₂ : { nfa' // (↑nfa₁).nodes.size < nfa'.nodes.size }
start₂ : Fin (↑nfa₂).nodes.size
inBounds✝ : (Node.split ↑start₁ ↑start₂).inBounds ((↑nfa₂).nodes.size + 1)
nfa' : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑nfa').nodes.size
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
a✝ : start₂ = (↑nfa₂).start
eq₅ : nfa' = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds✝
eq : nfa'✝ = ⟨↑nfa', property⟩
this✝ : (↑nfa₁).pathToNext (↑next) nfa.nodes.size (↑(↑nfa₁).start) cs
this : (↑nfa').pathToNext (↑next) nfa.nodes.size (↑(↑nfa₁).start) cs
⊢ nfa.nodes.size ≤ ↑(↑((↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds✝)).start
Tactic:
simp
Proof state after:
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Data.Expr
nfa'✝ : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq✝ : nfa.pushRegex next (r₁.alternate r₂) = nfa'✝
ih :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {nfa' : { nfa' // nfa.nodes.size < nfa'.nodes.size }},
    nfa.pushRegex next r₁ = nfa' → (↑nfa').pathToNext (↑next) nfa.nodes.size (↑(↑nfa').start) cs
nfa₁ : { nfa' // nfa.nodes.size < nfa'.nodes.size }
start₁ : Fin (↑nfa₁).nodes.size
nfa₂ : { nfa' // (↑nfa₁).nodes.size < nfa'.nodes.size }
start₂ : Fin (↑nfa₂).nodes.size
inBounds✝ : (Node.split ↑start₁ ↑start₂).inBounds ((↑nfa₂).nodes.size + 1)
nfa' : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑nfa').nodes.size
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
a✝ : start₂ = (↑nfa₂).start
eq₅ : nfa' = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds✝
eq : nfa'✝ = ⟨↑nfa', property⟩
this✝ : (↑nfa₁).pathToNext (↑next) nfa.nodes.size (↑(↑nfa₁).start) cs
this : (↑nfa').pathToNext (↑next) nfa.nodes.size (↑(↑nfa₁).start) cs
⊢ nfa.nodes.size ≤ (↑nfa₂).nodes.size
Theorem: Regex.NFA.pathToNext_of_matches.alternateLeft
Proof state before:
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Data.Expr
nfa'✝ : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq✝ : nfa.pushRegex next (r₁.alternate r₂) = nfa'✝
ih :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {nfa' : { nfa' // nfa.nodes.size < nfa'.nodes.size }},
    nfa.pushRegex next r₁ = nfa' → (↑nfa').pathToNext (↑next) nfa.nodes.size (↑(↑nfa').start) cs
nfa₁ : { nfa' // nfa.nodes.size < nfa'.nodes.size }
start₁ : Fin (↑nfa₁).nodes.size
nfa₂ : { nfa' // (↑nfa₁).nodes.size < nfa'.nodes.size }
start₂ : Fin (↑nfa₂).nodes.size
inBounds✝ : (Node.split ↑start₁ ↑start₂).inBounds ((↑nfa₂).nodes.size + 1)
nfa' : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑nfa').nodes.size
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
a✝ : start₂ = (↑nfa₂).start
eq₅ : nfa' = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds✝
eq : nfa'✝ = ⟨↑nfa', property⟩
this✝ : (↑nfa₁).pathToNext (↑next) nfa.nodes.size (↑(↑nfa₁).start) cs
this : (↑nfa').pathToNext (↑next) nfa.nodes.size (↑(↑nfa₁).start) cs
⊢ nfa.nodes.size ≤ (↑nfa₂).nodes.size
Tactic:
exact Nat.le_of_lt (Nat.lt_trans nfa₁.property nfa₂.property)
Proof state after:
no goals