Theorem: Regex.NFA.matches_of_path.alternate (RegexCorrectness/NFA/Transition/Path/Equivalence/MatchOfPath.lean)

State before:
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Expr
result : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq : nfa.pushRegex next (r₁.alternate r₂) = result
path : (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs
ih₁ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₁ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₁
ih₂ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₂ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₂
⊢ Expr.matches cs (r₁.alternate r₂)
Tactic:
apply pushRegex.alternate eq
State after:
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Expr
result : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq : nfa.pushRegex next (r₁.alternate r₂) = result
path : (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs
ih₁ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₁ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₁
ih₂ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₂ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₂
⊢ ∀ (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),
    nfa₁ = nfa.pushRegex next r₁ →
      start₁ = (↑nfa₁).start →
        nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂ →
          start₂ = (↑nfa₂).start →
            nfa' = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds →
              result = ⟨↑nfa', property⟩ → Expr.matches cs (r₁.alternate r₂)

State before:
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Expr
result : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq : nfa.pushRegex next (r₁.alternate r₂) = result
path : (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs
ih₁ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₁ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₁
ih₂ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₂ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₂
⊢ ∀ (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),
    nfa₁ = nfa.pushRegex next r₁ →
      start₁ = (↑nfa₁).start →
        nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂ →
          start₂ = (↑nfa₂).start →
            nfa' = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds →
              result = ⟨↑nfa', property⟩ → Expr.matches cs (r₁.alternate r₂)
Tactic:
intro nfa₁ start₁ nfa₂ start₂ inBounds final property eq₁ eq₂ eq₃ eq₄ eq₅ eq'
State after:
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Expr
result : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq : nfa.pushRegex next (r₁.alternate r₂) = result
path : (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs
ih₁ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₁ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₁
ih₂ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₂ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₂
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)
final : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑final).nodes.size
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
eq₄ : start₂ = (↑nfa₂).start
eq₅ : final = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds
eq' : result = ⟨↑final, property⟩
⊢ Expr.matches cs (r₁.alternate r₂)

State before:
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Expr
result : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq : nfa.pushRegex next (r₁.alternate r₂) = result
path : (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs
ih₁ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₁ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₁
ih₂ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₂ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₂
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)
final : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑final).nodes.size
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
eq₄ : start₂ = (↑nfa₂).start
eq₅ : final = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds
eq' : result = ⟨↑final, property⟩
⊢ Expr.matches cs (r₁.alternate r₂)
Tactic:
rw [eq'] at path
State after:
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Expr
result : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq : nfa.pushRegex next (r₁.alternate r₂) = result
ih₁ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₁ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₁
ih₂ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₂ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₂
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)
final : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑final).nodes.size
path : (↑⟨↑final, property⟩).pathToNext (↑next) nfa.nodes.size (↑(↑⟨↑final, property⟩).start) cs
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
eq₄ : start₂ = (↑nfa₂).start
eq₅ : final = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds
eq' : result = ⟨↑final, property⟩
⊢ Expr.matches cs (r₁.alternate r₂)

State before:
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Expr
result : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq : nfa.pushRegex next (r₁.alternate r₂) = result
ih₁ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₁ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₁
ih₂ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₂ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₂
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)
final : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑final).nodes.size
path : (↑⟨↑final, property⟩).pathToNext (↑next) nfa.nodes.size (↑(↑⟨↑final, property⟩).start) cs
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
eq₄ : start₂ = (↑nfa₂).start
eq₅ : final = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds
eq' : result = ⟨↑final, property⟩
⊢ Expr.matches cs (r₁.alternate r₂)
Tactic:
simp at path
State after:
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Expr
result : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq : nfa.pushRegex next (r₁.alternate r₂) = result
ih₁ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₁ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₁
ih₂ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₂ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₂
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)
final : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑final).nodes.size
path : (↑final).pathToNext (↑next) nfa.nodes.size (↑(↑final).start) cs
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
eq₄ : start₂ = (↑nfa₂).start
eq₅ : final = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds
eq' : result = ⟨↑final, property⟩
⊢ Expr.matches cs (r₁.alternate r₂)

State before:
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Expr
result : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq : nfa.pushRegex next (r₁.alternate r₂) = result
ih₁ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₁ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₁
ih₂ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₂ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₂
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)
final : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑final).nodes.size
path : (↑final).pathToNext (↑next) nfa.nodes.size (↑(↑final).start) cs
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
eq₄ : start₂ = (↑nfa₂).start
eq₅ : final = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds
eq' : result = ⟨↑final, property⟩
⊢ Expr.matches cs (r₁.alternate r₂)
Tactic:
have startNode : final.val[final.val.start.val] = .split start₁ start₂ := by
  rw [eq₅]
  simp
State after:
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Expr
result : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq : nfa.pushRegex next (r₁.alternate r₂) = result
ih₁ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₁ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₁
ih₂ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₂ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₂
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)
final : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑final).nodes.size
path : (↑final).pathToNext (↑next) nfa.nodes.size (↑(↑final).start) cs
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
eq₄ : start₂ = (↑nfa₂).start
eq₅ : final = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds
eq' : result = ⟨↑final, property⟩
startNode : (↑final)[↑(↑final).start] = Node.split ↑start₁ ↑start₂
⊢ Expr.matches cs (r₁.alternate r₂)

State before:
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Expr
result : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq : nfa.pushRegex next (r₁.alternate r₂) = result
ih₁ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₁ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₁
ih₂ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₂ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₂
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)
final : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑final).nodes.size
path : (↑final).pathToNext (↑next) nfa.nodes.size (↑(↑final).start) cs
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
eq₄ : start₂ = (↑nfa₂).start
eq₅ : final = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds
eq' : result = ⟨↑final, property⟩
startNode : (↑final)[↑(↑final).start] = Node.split ↑start₁ ↑start₂
⊢ Expr.matches cs (r₁.alternate r₂)
Tactic:
have neStart₁ : next.val ≠ start₁.val := by
  apply Nat.ne_of_lt
  apply Nat.lt_of_lt_of_le next.isLt
  exact eq₂ ▸ ge_pushRegex_start eq₁.symm
State after:
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Expr
result : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq : nfa.pushRegex next (r₁.alternate r₂) = result
ih₁ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₁ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₁
ih₂ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₂ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₂
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)
final : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑final).nodes.size
path : (↑final).pathToNext (↑next) nfa.nodes.size (↑(↑final).start) cs
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
eq₄ : start₂ = (↑nfa₂).start
eq₅ : final = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds
eq' : result = ⟨↑final, property⟩
startNode : (↑final)[↑(↑final).start] = Node.split ↑start₁ ↑start₂
neStart₁ : ↑next ≠ ↑start₁
⊢ Expr.matches cs (r₁.alternate r₂)

State before:
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Expr
result : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq : nfa.pushRegex next (r₁.alternate r₂) = result
ih₁ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₁ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₁
ih₂ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₂ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₂
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)
final : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑final).nodes.size
path : (↑final).pathToNext (↑next) nfa.nodes.size (↑(↑final).start) cs
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
eq₄ : start₂ = (↑nfa₂).start
eq₅ : final = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds
eq' : result = ⟨↑final, property⟩
startNode : (↑final)[↑(↑final).start] = Node.split ↑start₁ ↑start₂
neStart₁ : ↑next ≠ ↑start₁
⊢ Expr.matches cs (r₁.alternate r₂)
Tactic:
have neStart₂ : next.val ≠ start₂.val := by
  apply Nat.ne_of_lt
  apply Nat.lt_of_lt_of_le (Nat.lt_trans next.isLt nfa₁.property)
  exact eq₄ ▸ ge_pushRegex_start eq₃.symm
State after:
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Expr
result : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq : nfa.pushRegex next (r₁.alternate r₂) = result
ih₁ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₁ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₁
ih₂ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₂ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₂
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)
final : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑final).nodes.size
path : (↑final).pathToNext (↑next) nfa.nodes.size (↑(↑final).start) cs
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
eq₄ : start₂ = (↑nfa₂).start
eq₅ : final = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds
eq' : result = ⟨↑final, property⟩
startNode : (↑final)[↑(↑final).start] = Node.split ↑start₁ ↑start₂
neStart₁ : ↑next ≠ ↑start₁
neStart₂ : ↑next ≠ ↑start₂
⊢ Expr.matches cs (r₁.alternate r₂)

State before:
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Expr
result : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq : nfa.pushRegex next (r₁.alternate r₂) = result
ih₁ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₁ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₁
ih₂ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₂ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₂
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)
final : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑final).nodes.size
path : (↑final).pathToNext (↑next) nfa.nodes.size (↑(↑final).start) cs
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
eq₄ : start₂ = (↑nfa₂).start
eq₅ : final = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds
eq' : result = ⟨↑final, property⟩
startNode : (↑final)[↑(↑final).start] = Node.split ↑start₁ ↑start₂
neStart₁ : ↑next ≠ ↑start₁
neStart₂ : ↑next ≠ ↑start₂
⊢ Expr.matches cs (r₁.alternate r₂)
Tactic:
have get₂ (i : Nat) (_ : nfa.nodes.size ≤ i) (h₂: i < nfa₂.val.nodes.size) :
  nfa₂.val[i] = final.val[i]'(Nat.lt_trans h₂ final.property) := by
  simp [eq₅]
  rw [pushNode_get_lt]
State after:
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Expr
result : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq : nfa.pushRegex next (r₁.alternate r₂) = result
ih₁ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₁ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₁
ih₂ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₂ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₂
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)
final : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑final).nodes.size
path : (↑final).pathToNext (↑next) nfa.nodes.size (↑(↑final).start) cs
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
eq₄ : start₂ = (↑nfa₂).start
eq₅ : final = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds
eq' : result = ⟨↑final, property⟩
startNode : (↑final)[↑(↑final).start] = Node.split ↑start₁ ↑start₂
neStart₁ : ↑next ≠ ↑start₁
neStart₂ : ↑next ≠ ↑start₂
get₂ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₂).nodes.size), (↑nfa₂)[i] = (↑final)[i]
⊢ Expr.matches cs (r₁.alternate r₂)

State before:
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Expr
result : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq : nfa.pushRegex next (r₁.alternate r₂) = result
ih₁ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₁ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₁
ih₂ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₂ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₂
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)
final : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑final).nodes.size
path : (↑final).pathToNext (↑next) nfa.nodes.size (↑(↑final).start) cs
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
eq₄ : start₂ = (↑nfa₂).start
eq₅ : final = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds
eq' : result = ⟨↑final, property⟩
startNode : (↑final)[↑(↑final).start] = Node.split ↑start₁ ↑start₂
neStart₁ : ↑next ≠ ↑start₁
neStart₂ : ↑next ≠ ↑start₂
get₂ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₂).nodes.size), (↑nfa₂)[i] = (↑final)[i]
⊢ Expr.matches cs (r₁.alternate r₂)
Tactic:
have get₁ (i : Nat) (h₁ : nfa.nodes.size ≤ i) (h₂: i < nfa₁.val.nodes.size) :
  nfa₁.val[i] = final.val[i]'(Nat.lt_trans (Nat.lt_trans h₂ nfa₂.property) final.property) := by
  rw [←get₂ i h₁ (Nat.lt_trans h₂ nfa₂.property)]
  rw [pushRegex_get_lt eq₃.symm]
State after:
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Expr
result : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq : nfa.pushRegex next (r₁.alternate r₂) = result
ih₁ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₁ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₁
ih₂ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₂ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₂
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)
final : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑final).nodes.size
path : (↑final).pathToNext (↑next) nfa.nodes.size (↑(↑final).start) cs
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
eq₄ : start₂ = (↑nfa₂).start
eq₅ : final = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds
eq' : result = ⟨↑final, property⟩
startNode : (↑final)[↑(↑final).start] = Node.split ↑start₁ ↑start₂
neStart₁ : ↑next ≠ ↑start₁
neStart₂ : ↑next ≠ ↑start₂
get₂ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₂).nodes.size), (↑nfa₂)[i] = (↑final)[i]
get₁ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₁).nodes.size), (↑nfa₁)[i] = (↑final)[i]
⊢ Expr.matches cs (r₁.alternate r₂)

State before:
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Expr
result : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq : nfa.pushRegex next (r₁.alternate r₂) = result
ih₁ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₁ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₁
ih₂ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₂ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₂
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)
final : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑final).nodes.size
path : (↑final).pathToNext (↑next) nfa.nodes.size (↑(↑final).start) cs
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
eq₄ : start₂ = (↑nfa₂).start
eq₅ : final = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds
eq' : result = ⟨↑final, property⟩
startNode : (↑final)[↑(↑final).start] = Node.split ↑start₁ ↑start₂
neStart₁ : ↑next ≠ ↑start₁
neStart₂ : ↑next ≠ ↑start₂
get₂ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₂).nodes.size), (↑nfa₂)[i] = (↑final)[i]
get₁ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₁).nodes.size), (↑nfa₁)[i] = (↑final)[i]
⊢ Expr.matches cs (r₁.alternate r₂)
Tactic:
obtain ⟨i, cs₁, cs₂, eqs, path, step⟩ := path
State after:
case intro.intro.intro.intro.intro
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Expr
result : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq : nfa.pushRegex next (r₁.alternate r₂) = result
ih₁ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₁ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₁
ih₂ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₂ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₂
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)
final : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑final).nodes.size
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
eq₄ : start₂ = (↑nfa₂).start
eq₅ : final = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds
eq' : result = ⟨↑final, property⟩
startNode : (↑final)[↑(↑final).start] = Node.split ↑start₁ ↑start₂
neStart₁ : ↑next ≠ ↑start₁
neStart₂ : ↑next ≠ ↑start₂
get₂ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₂).nodes.size), (↑nfa₂)[i] = (↑final)[i]
get₁ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₁).nodes.size), (↑nfa₁)[i] = (↑final)[i]
i : ℕ
cs₁ cs₂ : List Char
eqs : cs = cs₁ ++ cs₂
path : (↑final).pathIn nfa.nodes.size (↑(↑final).start) i cs₁
step : (↑final).stepIn nfa.nodes.size i (↑next) cs₂
⊢ Expr.matches cs (r₁.alternate r₂)

State before:
case intro.intro.intro.intro.intro
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Expr
result : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq : nfa.pushRegex next (r₁.alternate r₂) = result
ih₁ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₁ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₁
ih₂ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₂ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₂
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)
final : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑final).nodes.size
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
eq₄ : start₂ = (↑nfa₂).start
eq₅ : final = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds
eq' : result = ⟨↑final, property⟩
startNode : (↑final)[↑(↑final).start] = Node.split ↑start₁ ↑start₂
neStart₁ : ↑next ≠ ↑start₁
neStart₂ : ↑next ≠ ↑start₂
get₂ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₂).nodes.size), (↑nfa₂)[i] = (↑final)[i]
get₁ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₁).nodes.size), (↑nfa₁)[i] = (↑final)[i]
i : ℕ
cs₁ cs₂ : List Char
eqs : cs = cs₁ ++ cs₂
path : (↑final).pathIn nfa.nodes.size (↑(↑final).start) i cs₁
step : (↑final).stepIn nfa.nodes.size i (↑next) cs₂
⊢ Expr.matches cs (r₁.alternate r₂)
Tactic:
cases path with
| base _ =>
  cases step with
  | charStep _ _ step => simp [NFA.Node.charStep, startNode] at step
  | εStep _ _ step =>
    simp [NFA.Node.εStep, startNode] at step
    cases step <;> simp only [neStart₁, neStart₂] at *
| @step _ _ _ cs₃ cs₄ step rest =>
  cases step with
  | charStep _ _ step => simp [NFA.Node.charStep, startNode] at step
  | εStep _ _ step =>
    simp at eqs
    simp [NFA.Node.εStep, startNode] at step
    cases step with
    | inl eqs₁ =>
      rw [eqs₁] at rest
      have : pathToNext final next nfa.nodes.size nfa₁.val.start.val cs :=
        ⟨i, cs₄, cs₂, eqs, eq₂ ▸ rest, step⟩
      have : pathToNext nfa₁ next nfa.nodes.size nfa₁.val.start.val cs := by
        apply this.cast' nfa₁.val.start.isLt
          (Nat.le_of_lt (Nat.lt_trans nfa₂.property final.property))
          get₁
      exact .alternateLeft (ih₁ eq₁.symm this)
    | inr eqs₂ =>
      rw [eqs₂] at rest
      have : pathToNext final next nfa.nodes.size nfa₂.val.start.val cs :=
        ⟨i, cs₄, cs₂, eqs, eq₄ ▸ rest, step⟩
      have : pathToNext nfa₂ next nfa.nodes.size nfa₂.val.start.val cs := by
        apply this.cast' nfa₂.val.start.isLt (Nat.le_of_lt final.property) get₂
      have : pathToNext nfa₂ next nfa₁.val.nodes.size nfa₂.val.start.val cs := by
        apply this.castLE (ge_pushRegex_start eq₃.symm)
        intro i j h₁ h₂ step hj
        have := eq_or_ge_of_step_pushRegex eq₃.symm h₁ h₂ step
        simp at this
        cases this with
        | inl eq =>
          exfalso
          rw [eq] at hj
          exact Nat.not_le_of_gt next.isLt hj
        | inr ge => exact ge
      exact .alternateRight (ih₂ eq₃.symm this)
State after:
no goals

State before:
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Expr
result : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq : nfa.pushRegex next (r₁.alternate r₂) = result
ih₁ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₁ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₁
ih₂ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₂ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₂
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)
final : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑final).nodes.size
path : (↑final).pathToNext (↑next) nfa.nodes.size (↑(↑final).start) cs
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
eq₄ : start₂ = (↑nfa₂).start
eq₅ : final = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds
eq' : result = ⟨↑final, property⟩
⊢ (↑final)[↑(↑final).start] = Node.split ↑start₁ ↑start₂
Tactic:
rw [eq₅]
State after:
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Expr
result : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq : nfa.pushRegex next (r₁.alternate r₂) = result
ih₁ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₁ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₁
ih₂ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₂ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₂
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)
final : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑final).nodes.size
path : (↑final).pathToNext (↑next) nfa.nodes.size (↑(↑final).start) cs
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
eq₄ : start₂ = (↑nfa₂).start
eq₅ : final = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds
eq' : result = ⟨↑final, property⟩
⊢ (↑((↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂)
          inBounds))[↑(↑((↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds)).start] =
    Node.split ↑start₁ ↑start₂

State before:
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Expr
result : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq : nfa.pushRegex next (r₁.alternate r₂) = result
ih₁ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₁ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₁
ih₂ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₂ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₂
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)
final : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑final).nodes.size
path : (↑final).pathToNext (↑next) nfa.nodes.size (↑(↑final).start) cs
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
eq₄ : start₂ = (↑nfa₂).start
eq₅ : final = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds
eq' : result = ⟨↑final, property⟩
⊢ (↑((↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂)
          inBounds))[↑(↑((↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds)).start] =
    Node.split ↑start₁ ↑start₂
Tactic:
simp
State after:
no goals

State before:
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Expr
result : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq : nfa.pushRegex next (r₁.alternate r₂) = result
ih₁ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₁ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₁
ih₂ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₂ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₂
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)
final : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑final).nodes.size
path : (↑final).pathToNext (↑next) nfa.nodes.size (↑(↑final).start) cs
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
eq₄ : start₂ = (↑nfa₂).start
eq₅ : final = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds
eq' : result = ⟨↑final, property⟩
startNode : (↑final)[↑(↑final).start] = Node.split ↑start₁ ↑start₂
⊢ ↑next ≠ ↑start₁
Tactic:
apply Nat.ne_of_lt
State after:
case h
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Expr
result : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq : nfa.pushRegex next (r₁.alternate r₂) = result
ih₁ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₁ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₁
ih₂ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₂ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₂
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)
final : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑final).nodes.size
path : (↑final).pathToNext (↑next) nfa.nodes.size (↑(↑final).start) cs
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
eq₄ : start₂ = (↑nfa₂).start
eq₅ : final = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds
eq' : result = ⟨↑final, property⟩
startNode : (↑final)[↑(↑final).start] = Node.split ↑start₁ ↑start₂
⊢ ↑next < ↑start₁

State before:
case h
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Expr
result : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq : nfa.pushRegex next (r₁.alternate r₂) = result
ih₁ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₁ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₁
ih₂ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₂ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₂
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)
final : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑final).nodes.size
path : (↑final).pathToNext (↑next) nfa.nodes.size (↑(↑final).start) cs
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
eq₄ : start₂ = (↑nfa₂).start
eq₅ : final = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds
eq' : result = ⟨↑final, property⟩
startNode : (↑final)[↑(↑final).start] = Node.split ↑start₁ ↑start₂
⊢ ↑next < ↑start₁
Tactic:
apply Nat.lt_of_lt_of_le next.isLt
State after:
case h
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Expr
result : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq : nfa.pushRegex next (r₁.alternate r₂) = result
ih₁ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₁ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₁
ih₂ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₂ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₂
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)
final : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑final).nodes.size
path : (↑final).pathToNext (↑next) nfa.nodes.size (↑(↑final).start) cs
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
eq₄ : start₂ = (↑nfa₂).start
eq₅ : final = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds
eq' : result = ⟨↑final, property⟩
startNode : (↑final)[↑(↑final).start] = Node.split ↑start₁ ↑start₂
⊢ nfa.nodes.size ≤ ↑start₁

State before:
case h
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Expr
result : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq : nfa.pushRegex next (r₁.alternate r₂) = result
ih₁ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₁ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₁
ih₂ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₂ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₂
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)
final : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑final).nodes.size
path : (↑final).pathToNext (↑next) nfa.nodes.size (↑(↑final).start) cs
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
eq₄ : start₂ = (↑nfa₂).start
eq₅ : final = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds
eq' : result = ⟨↑final, property⟩
startNode : (↑final)[↑(↑final).start] = Node.split ↑start₁ ↑start₂
⊢ nfa.nodes.size ≤ ↑start₁
Tactic:
exact eq₂ ▸ ge_pushRegex_start eq₁.symm
State after:
no goals

State before:
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Expr
result : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq : nfa.pushRegex next (r₁.alternate r₂) = result
ih₁ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₁ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₁
ih₂ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₂ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₂
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)
final : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑final).nodes.size
path : (↑final).pathToNext (↑next) nfa.nodes.size (↑(↑final).start) cs
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
eq₄ : start₂ = (↑nfa₂).start
eq₅ : final = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds
eq' : result = ⟨↑final, property⟩
startNode : (↑final)[↑(↑final).start] = Node.split ↑start₁ ↑start₂
neStart₁ : ↑next ≠ ↑start₁
⊢ ↑next ≠ ↑start₂
Tactic:
apply Nat.ne_of_lt
State after:
case h
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Expr
result : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq : nfa.pushRegex next (r₁.alternate r₂) = result
ih₁ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₁ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₁
ih₂ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₂ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₂
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)
final : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑final).nodes.size
path : (↑final).pathToNext (↑next) nfa.nodes.size (↑(↑final).start) cs
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
eq₄ : start₂ = (↑nfa₂).start
eq₅ : final = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds
eq' : result = ⟨↑final, property⟩
startNode : (↑final)[↑(↑final).start] = Node.split ↑start₁ ↑start₂
neStart₁ : ↑next ≠ ↑start₁
⊢ ↑next < ↑start₂

State before:
case h
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Expr
result : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq : nfa.pushRegex next (r₁.alternate r₂) = result
ih₁ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₁ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₁
ih₂ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₂ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₂
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)
final : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑final).nodes.size
path : (↑final).pathToNext (↑next) nfa.nodes.size (↑(↑final).start) cs
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
eq₄ : start₂ = (↑nfa₂).start
eq₅ : final = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds
eq' : result = ⟨↑final, property⟩
startNode : (↑final)[↑(↑final).start] = Node.split ↑start₁ ↑start₂
neStart₁ : ↑next ≠ ↑start₁
⊢ ↑next < ↑start₂
Tactic:
apply Nat.lt_of_lt_of_le (Nat.lt_trans next.isLt nfa₁.property)
State after:
case h
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Expr
result : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq : nfa.pushRegex next (r₁.alternate r₂) = result
ih₁ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₁ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₁
ih₂ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₂ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₂
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)
final : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑final).nodes.size
path : (↑final).pathToNext (↑next) nfa.nodes.size (↑(↑final).start) cs
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
eq₄ : start₂ = (↑nfa₂).start
eq₅ : final = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds
eq' : result = ⟨↑final, property⟩
startNode : (↑final)[↑(↑final).start] = Node.split ↑start₁ ↑start₂
neStart₁ : ↑next ≠ ↑start₁
⊢ (↑nfa₁).nodes.size ≤ ↑start₂

State before:
case h
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Expr
result : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq : nfa.pushRegex next (r₁.alternate r₂) = result
ih₁ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₁ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₁
ih₂ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₂ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₂
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)
final : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑final).nodes.size
path : (↑final).pathToNext (↑next) nfa.nodes.size (↑(↑final).start) cs
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
eq₄ : start₂ = (↑nfa₂).start
eq₅ : final = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds
eq' : result = ⟨↑final, property⟩
startNode : (↑final)[↑(↑final).start] = Node.split ↑start₁ ↑start₂
neStart₁ : ↑next ≠ ↑start₁
⊢ (↑nfa₁).nodes.size ≤ ↑start₂
Tactic:
exact eq₄ ▸ ge_pushRegex_start eq₃.symm
State after:
no goals

State before:
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Expr
result : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq : nfa.pushRegex next (r₁.alternate r₂) = result
ih₁ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₁ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₁
ih₂ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₂ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₂
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)
final : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑final).nodes.size
path : (↑final).pathToNext (↑next) nfa.nodes.size (↑(↑final).start) cs
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
eq₄ : start₂ = (↑nfa₂).start
eq₅ : final = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds
eq' : result = ⟨↑final, property⟩
startNode : (↑final)[↑(↑final).start] = Node.split ↑start₁ ↑start₂
neStart₁ : ↑next ≠ ↑start₁
neStart₂ : ↑next ≠ ↑start₂
i : ℕ
x✝ : nfa.nodes.size ≤ i
h₂ : i < (↑nfa₂).nodes.size
⊢ (↑nfa₂)[i] = (↑final)[i]
Tactic:
simp [eq₅]
State after:
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Expr
result : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq : nfa.pushRegex next (r₁.alternate r₂) = result
ih₁ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₁ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₁
ih₂ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₂ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₂
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)
final : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑final).nodes.size
path : (↑final).pathToNext (↑next) nfa.nodes.size (↑(↑final).start) cs
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
eq₄ : start₂ = (↑nfa₂).start
eq₅ : final = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds
eq' : result = ⟨↑final, property⟩
startNode : (↑final)[↑(↑final).start] = Node.split ↑start₁ ↑start₂
neStart₁ : ↑next ≠ ↑start₁
neStart₂ : ↑next ≠ ↑start₂
i : ℕ
x✝ : nfa.nodes.size ≤ i
h₂ : i < (↑nfa₂).nodes.size
⊢ (↑nfa₂)[i] = (↑((↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds))[i]

State before:
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Expr
result : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq : nfa.pushRegex next (r₁.alternate r₂) = result
ih₁ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₁ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₁
ih₂ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₂ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₂
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)
final : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑final).nodes.size
path : (↑final).pathToNext (↑next) nfa.nodes.size (↑(↑final).start) cs
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
eq₄ : start₂ = (↑nfa₂).start
eq₅ : final = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds
eq' : result = ⟨↑final, property⟩
startNode : (↑final)[↑(↑final).start] = Node.split ↑start₁ ↑start₂
neStart₁ : ↑next ≠ ↑start₁
neStart₂ : ↑next ≠ ↑start₂
i : ℕ
x✝ : nfa.nodes.size ≤ i
h₂ : i < (↑nfa₂).nodes.size
⊢ (↑nfa₂)[i] = (↑((↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds))[i]
Tactic:
rw [pushNode_get_lt]
State after:
no goals

State before:
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Expr
result : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq : nfa.pushRegex next (r₁.alternate r₂) = result
ih₁ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₁ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₁
ih₂ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₂ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₂
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)
final : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑final).nodes.size
path : (↑final).pathToNext (↑next) nfa.nodes.size (↑(↑final).start) cs
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
eq₄ : start₂ = (↑nfa₂).start
eq₅ : final = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds
eq' : result = ⟨↑final, property⟩
startNode : (↑final)[↑(↑final).start] = Node.split ↑start₁ ↑start₂
neStart₁ : ↑next ≠ ↑start₁
neStart₂ : ↑next ≠ ↑start₂
get₂ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₂).nodes.size), (↑nfa₂)[i] = (↑final)[i]
i : ℕ
h₁ : nfa.nodes.size ≤ i
h₂ : i < (↑nfa₁).nodes.size
⊢ (↑nfa₁)[i] = (↑final)[i]
Tactic:
rw [←get₂ i h₁ (Nat.lt_trans h₂ nfa₂.property)]
State after:
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Expr
result : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq : nfa.pushRegex next (r₁.alternate r₂) = result
ih₁ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₁ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₁
ih₂ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₂ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₂
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)
final : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑final).nodes.size
path : (↑final).pathToNext (↑next) nfa.nodes.size (↑(↑final).start) cs
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
eq₄ : start₂ = (↑nfa₂).start
eq₅ : final = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds
eq' : result = ⟨↑final, property⟩
startNode : (↑final)[↑(↑final).start] = Node.split ↑start₁ ↑start₂
neStart₁ : ↑next ≠ ↑start₁
neStart₂ : ↑next ≠ ↑start₂
get₂ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₂).nodes.size), (↑nfa₂)[i] = (↑final)[i]
i : ℕ
h₁ : nfa.nodes.size ≤ i
h₂ : i < (↑nfa₁).nodes.size
⊢ (↑nfa₁)[i] = (↑nfa₂)[i]

State before:
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Expr
result : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq : nfa.pushRegex next (r₁.alternate r₂) = result
ih₁ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₁ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₁
ih₂ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₂ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₂
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)
final : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑final).nodes.size
path : (↑final).pathToNext (↑next) nfa.nodes.size (↑(↑final).start) cs
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
eq₄ : start₂ = (↑nfa₂).start
eq₅ : final = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds
eq' : result = ⟨↑final, property⟩
startNode : (↑final)[↑(↑final).start] = Node.split ↑start₁ ↑start₂
neStart₁ : ↑next ≠ ↑start₁
neStart₂ : ↑next ≠ ↑start₂
get₂ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₂).nodes.size), (↑nfa₂)[i] = (↑final)[i]
i : ℕ
h₁ : nfa.nodes.size ≤ i
h₂ : i < (↑nfa₁).nodes.size
⊢ (↑nfa₁)[i] = (↑nfa₂)[i]
Tactic:
rw [pushRegex_get_lt eq₃.symm]
State after:
no goals

State before:
case intro.intro.intro.intro.intro.base
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Expr
result : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq : nfa.pushRegex next (r₁.alternate r₂) = result
ih₁ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₁ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₁
ih₂ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₂ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₂
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)
final : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑final).nodes.size
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
eq₄ : start₂ = (↑nfa₂).start
eq₅ : final = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds
eq' : result = ⟨↑final, property⟩
startNode : (↑final)[↑(↑final).start] = Node.split ↑start₁ ↑start₂
neStart₁ : ↑next ≠ ↑start₁
neStart₂ : ↑next ≠ ↑start₂
get₂ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₂).nodes.size), (↑nfa₂)[i] = (↑final)[i]
get₁ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₁).nodes.size), (↑nfa₁)[i] = (↑final)[i]
cs₂ : List Char
h✝ : nfa.nodes.size ≤ ↑(↑final).start
step : (↑final).stepIn nfa.nodes.size (↑(↑final).start) (↑next) cs₂
eqs : cs = [] ++ cs₂
⊢ Expr.matches cs (r₁.alternate r₂)
Tactic:
cases step with
| charStep _ _ step => simp [NFA.Node.charStep, startNode] at step
| εStep _ _ step =>
  simp [NFA.Node.εStep, startNode] at step
  cases step <;> simp only [neStart₁, neStart₂] at *
State after:
no goals

State before:
case intro.intro.intro.intro.intro.base.charStep
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Expr
result : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq : nfa.pushRegex next (r₁.alternate r₂) = result
ih₁ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₁ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₁
ih₂ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₂ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₂
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)
final : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑final).nodes.size
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
eq₄ : start₂ = (↑nfa₂).start
eq₅ : final = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds
eq' : result = ⟨↑final, property⟩
startNode : (↑final)[↑(↑final).start] = Node.split ↑start₁ ↑start₂
neStart₁ : ↑next ≠ ↑start₁
neStart₂ : ↑next ≠ ↑start₂
get₂ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₂).nodes.size), (↑nfa₂)[i] = (↑final)[i]
get₁ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₁).nodes.size), (↑nfa₁)[i] = (↑final)[i]
h✝ : nfa.nodes.size ≤ ↑(↑final).start
c✝ : Char
h₁✝ : nfa.nodes.size ≤ ↑(↑final).start
h₂✝ : ↑(↑final).start < (↑final).nodes.size
step : ↑next ∈ (↑final)[↑(↑final).start].charStep c✝
eqs : cs = [] ++ [c✝]
⊢ Expr.matches cs (r₁.alternate r₂)
Tactic:
simp [NFA.Node.charStep, startNode] at step
State after:
no goals

State before:
case intro.intro.intro.intro.intro.base.εStep
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Expr
result : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq : nfa.pushRegex next (r₁.alternate r₂) = result
ih₁ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₁ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₁
ih₂ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₂ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₂
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)
final : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑final).nodes.size
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
eq₄ : start₂ = (↑nfa₂).start
eq₅ : final = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds
eq' : result = ⟨↑final, property⟩
startNode : (↑final)[↑(↑final).start] = Node.split ↑start₁ ↑start₂
neStart₁ : ↑next ≠ ↑start₁
neStart₂ : ↑next ≠ ↑start₂
get₂ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₂).nodes.size), (↑nfa₂)[i] = (↑final)[i]
get₁ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₁).nodes.size), (↑nfa₁)[i] = (↑final)[i]
h✝ h₁✝ : nfa.nodes.size ≤ ↑(↑final).start
h₂✝ : ↑(↑final).start < (↑final).nodes.size
step : ↑next ∈ (↑final)[↑(↑final).start].εStep
eqs : cs = [] ++ []
⊢ Expr.matches cs (r₁.alternate r₂)
Tactic:
simp [NFA.Node.εStep, startNode] at step
State after:
case intro.intro.intro.intro.intro.base.εStep
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Expr
result : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq : nfa.pushRegex next (r₁.alternate r₂) = result
ih₁ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₁ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₁
ih₂ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₂ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₂
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)
final : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑final).nodes.size
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
eq₄ : start₂ = (↑nfa₂).start
eq₅ : final = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds
eq' : result = ⟨↑final, property⟩
startNode : (↑final)[↑(↑final).start] = Node.split ↑start₁ ↑start₂
neStart₁ : ↑next ≠ ↑start₁
neStart₂ : ↑next ≠ ↑start₂
get₂ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₂).nodes.size), (↑nfa₂)[i] = (↑final)[i]
get₁ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₁).nodes.size), (↑nfa₁)[i] = (↑final)[i]
h✝ h₁✝ : nfa.nodes.size ≤ ↑(↑final).start
h₂✝ : ↑(↑final).start < (↑final).nodes.size
eqs : cs = [] ++ []
step : ↑next = ↑start₁ ∨ ↑next = ↑start₂
⊢ Expr.matches cs (r₁.alternate r₂)

State before:
case intro.intro.intro.intro.intro.base.εStep
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Expr
result : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq : nfa.pushRegex next (r₁.alternate r₂) = result
ih₁ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₁ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₁
ih₂ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₂ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₂
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)
final : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑final).nodes.size
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
eq₄ : start₂ = (↑nfa₂).start
eq₅ : final = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds
eq' : result = ⟨↑final, property⟩
startNode : (↑final)[↑(↑final).start] = Node.split ↑start₁ ↑start₂
neStart₁ : ↑next ≠ ↑start₁
neStart₂ : ↑next ≠ ↑start₂
get₂ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₂).nodes.size), (↑nfa₂)[i] = (↑final)[i]
get₁ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₁).nodes.size), (↑nfa₁)[i] = (↑final)[i]
h✝ h₁✝ : nfa.nodes.size ≤ ↑(↑final).start
h₂✝ : ↑(↑final).start < (↑final).nodes.size
eqs : cs = [] ++ []
step : ↑next = ↑start₁ ∨ ↑next = ↑start₂
⊢ Expr.matches cs (r₁.alternate r₂)
Tactic:
cases step <;> simp only [neStart₁, neStart₂] at *
State after:
no goals

State before:
case intro.intro.intro.intro.intro.step
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Expr
result : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq : nfa.pushRegex next (r₁.alternate r₂) = result
ih₁ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₁ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₁
ih₂ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₂ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₂
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)
final : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑final).nodes.size
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
eq₄ : start₂ = (↑nfa₂).start
eq₅ : final = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds
eq' : result = ⟨↑final, property⟩
startNode : (↑final)[↑(↑final).start] = Node.split ↑start₁ ↑start₂
neStart₁ : ↑next ≠ ↑start₁
neStart₂ : ↑next ≠ ↑start₂
get₂ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₂).nodes.size), (↑nfa₂)[i] = (↑final)[i]
get₁ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₁).nodes.size), (↑nfa₁)[i] = (↑final)[i]
i : ℕ
cs₂ : List Char
step✝ : (↑final).stepIn nfa.nodes.size i (↑next) cs₂
j✝ : ℕ
cs₃ cs₄ : List Char
step : (↑final).stepIn nfa.nodes.size (↑(↑final).start) j✝ cs₃
rest : (↑final).pathIn nfa.nodes.size j✝ i cs₄
eqs : cs = cs₃ ++ cs₄ ++ cs₂
⊢ Expr.matches cs (r₁.alternate r₂)
Tactic:
cases step with
| charStep _ _ step => simp [NFA.Node.charStep, startNode] at step
| εStep _ _ step =>
  simp at eqs
  simp [NFA.Node.εStep, startNode] at step
  cases step with
  | inl eqs₁ =>
    rw [eqs₁] at rest
    have : pathToNext final next nfa.nodes.size nfa₁.val.start.val cs :=
      ⟨i, cs₄, cs₂, eqs, eq₂ ▸ rest, step⟩
    have : pathToNext nfa₁ next nfa.nodes.size nfa₁.val.start.val cs := by
      apply this.cast' nfa₁.val.start.isLt
        (Nat.le_of_lt (Nat.lt_trans nfa₂.property final.property))
        get₁
    exact .alternateLeft (ih₁ eq₁.symm this)
  | inr eqs₂ =>
    rw [eqs₂] at rest
    have : pathToNext final next nfa.nodes.size nfa₂.val.start.val cs :=
      ⟨i, cs₄, cs₂, eqs, eq₄ ▸ rest, step⟩
    have : pathToNext nfa₂ next nfa.nodes.size nfa₂.val.start.val cs := by
      apply this.cast' nfa₂.val.start.isLt (Nat.le_of_lt final.property) get₂
    have : pathToNext nfa₂ next nfa₁.val.nodes.size nfa₂.val.start.val cs := by
      apply this.castLE (ge_pushRegex_start eq₃.symm)
      intro i j h₁ h₂ step hj
      have := eq_or_ge_of_step_pushRegex eq₃.symm h₁ h₂ step
      simp at this
      cases this with
      | inl eq =>
        exfalso
        rw [eq] at hj
        exact Nat.not_le_of_gt next.isLt hj
      | inr ge => exact ge
    exact .alternateRight (ih₂ eq₃.symm this)
State after:
no goals

State before:
case intro.intro.intro.intro.intro.step.charStep
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Expr
result : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq : nfa.pushRegex next (r₁.alternate r₂) = result
ih₁ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₁ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₁
ih₂ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₂ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₂
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)
final : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑final).nodes.size
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
eq₄ : start₂ = (↑nfa₂).start
eq₅ : final = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds
eq' : result = ⟨↑final, property⟩
startNode : (↑final)[↑(↑final).start] = Node.split ↑start₁ ↑start₂
neStart₁ : ↑next ≠ ↑start₁
neStart₂ : ↑next ≠ ↑start₂
get₂ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₂).nodes.size), (↑nfa₂)[i] = (↑final)[i]
get₁ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₁).nodes.size), (↑nfa₁)[i] = (↑final)[i]
i : ℕ
cs₂ : List Char
step✝ : (↑final).stepIn nfa.nodes.size i (↑next) cs₂
j✝ : ℕ
cs₄ : List Char
rest : (↑final).pathIn nfa.nodes.size j✝ i cs₄
c✝ : Char
h₁✝ : nfa.nodes.size ≤ ↑(↑final).start
h₂✝ : ↑(↑final).start < (↑final).nodes.size
step : j✝ ∈ (↑final)[↑(↑final).start].charStep c✝
eqs : cs = [c✝] ++ cs₄ ++ cs₂
⊢ Expr.matches cs (r₁.alternate r₂)
Tactic:
simp [NFA.Node.charStep, startNode] at step
State after:
no goals

State before:
case intro.intro.intro.intro.intro.step.εStep
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Expr
result : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq : nfa.pushRegex next (r₁.alternate r₂) = result
ih₁ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₁ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₁
ih₂ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₂ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₂
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)
final : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑final).nodes.size
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
eq₄ : start₂ = (↑nfa₂).start
eq₅ : final = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds
eq' : result = ⟨↑final, property⟩
startNode : (↑final)[↑(↑final).start] = Node.split ↑start₁ ↑start₂
neStart₁ : ↑next ≠ ↑start₁
neStart₂ : ↑next ≠ ↑start₂
get₂ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₂).nodes.size), (↑nfa₂)[i] = (↑final)[i]
get₁ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₁).nodes.size), (↑nfa₁)[i] = (↑final)[i]
i : ℕ
cs₂ : List Char
step✝ : (↑final).stepIn nfa.nodes.size i (↑next) cs₂
j✝ : ℕ
cs₄ : List Char
rest : (↑final).pathIn nfa.nodes.size j✝ i cs₄
h₁✝ : nfa.nodes.size ≤ ↑(↑final).start
h₂✝ : ↑(↑final).start < (↑final).nodes.size
step : j✝ ∈ (↑final)[↑(↑final).start].εStep
eqs : cs = [] ++ cs₄ ++ cs₂
⊢ Expr.matches cs (r₁.alternate r₂)
Tactic:
simp at eqs
State after:
case intro.intro.intro.intro.intro.step.εStep
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Expr
result : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq : nfa.pushRegex next (r₁.alternate r₂) = result
ih₁ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₁ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₁
ih₂ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₂ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₂
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)
final : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑final).nodes.size
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
eq₄ : start₂ = (↑nfa₂).start
eq₅ : final = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds
eq' : result = ⟨↑final, property⟩
startNode : (↑final)[↑(↑final).start] = Node.split ↑start₁ ↑start₂
neStart₁ : ↑next ≠ ↑start₁
neStart₂ : ↑next ≠ ↑start₂
get₂ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₂).nodes.size), (↑nfa₂)[i] = (↑final)[i]
get₁ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₁).nodes.size), (↑nfa₁)[i] = (↑final)[i]
i : ℕ
cs₂ : List Char
step✝ : (↑final).stepIn nfa.nodes.size i (↑next) cs₂
j✝ : ℕ
cs₄ : List Char
rest : (↑final).pathIn nfa.nodes.size j✝ i cs₄
h₁✝ : nfa.nodes.size ≤ ↑(↑final).start
h₂✝ : ↑(↑final).start < (↑final).nodes.size
step : j✝ ∈ (↑final)[↑(↑final).start].εStep
eqs : cs = cs₄ ++ cs₂
⊢ Expr.matches cs (r₁.alternate r₂)

State before:
case intro.intro.intro.intro.intro.step.εStep
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Expr
result : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq : nfa.pushRegex next (r₁.alternate r₂) = result
ih₁ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₁ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₁
ih₂ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₂ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₂
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)
final : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑final).nodes.size
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
eq₄ : start₂ = (↑nfa₂).start
eq₅ : final = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds
eq' : result = ⟨↑final, property⟩
startNode : (↑final)[↑(↑final).start] = Node.split ↑start₁ ↑start₂
neStart₁ : ↑next ≠ ↑start₁
neStart₂ : ↑next ≠ ↑start₂
get₂ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₂).nodes.size), (↑nfa₂)[i] = (↑final)[i]
get₁ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₁).nodes.size), (↑nfa₁)[i] = (↑final)[i]
i : ℕ
cs₂ : List Char
step✝ : (↑final).stepIn nfa.nodes.size i (↑next) cs₂
j✝ : ℕ
cs₄ : List Char
rest : (↑final).pathIn nfa.nodes.size j✝ i cs₄
h₁✝ : nfa.nodes.size ≤ ↑(↑final).start
h₂✝ : ↑(↑final).start < (↑final).nodes.size
step : j✝ ∈ (↑final)[↑(↑final).start].εStep
eqs : cs = cs₄ ++ cs₂
⊢ Expr.matches cs (r₁.alternate r₂)
Tactic:
simp [NFA.Node.εStep, startNode] at step
State after:
case intro.intro.intro.intro.intro.step.εStep
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Expr
result : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq : nfa.pushRegex next (r₁.alternate r₂) = result
ih₁ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₁ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₁
ih₂ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₂ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₂
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)
final : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑final).nodes.size
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
eq₄ : start₂ = (↑nfa₂).start
eq₅ : final = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds
eq' : result = ⟨↑final, property⟩
startNode : (↑final)[↑(↑final).start] = Node.split ↑start₁ ↑start₂
neStart₁ : ↑next ≠ ↑start₁
neStart₂ : ↑next ≠ ↑start₂
get₂ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₂).nodes.size), (↑nfa₂)[i] = (↑final)[i]
get₁ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₁).nodes.size), (↑nfa₁)[i] = (↑final)[i]
i : ℕ
cs₂ : List Char
step✝ : (↑final).stepIn nfa.nodes.size i (↑next) cs₂
j✝ : ℕ
cs₄ : List Char
rest : (↑final).pathIn nfa.nodes.size j✝ i cs₄
h₁✝ : nfa.nodes.size ≤ ↑(↑final).start
h₂✝ : ↑(↑final).start < (↑final).nodes.size
eqs : cs = cs₄ ++ cs₂
step : j✝ = ↑start₁ ∨ j✝ = ↑start₂
⊢ Expr.matches cs (r₁.alternate r₂)

State before:
case intro.intro.intro.intro.intro.step.εStep
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Expr
result : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq : nfa.pushRegex next (r₁.alternate r₂) = result
ih₁ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₁ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₁
ih₂ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₂ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₂
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)
final : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑final).nodes.size
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
eq₄ : start₂ = (↑nfa₂).start
eq₅ : final = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds
eq' : result = ⟨↑final, property⟩
startNode : (↑final)[↑(↑final).start] = Node.split ↑start₁ ↑start₂
neStart₁ : ↑next ≠ ↑start₁
neStart₂ : ↑next ≠ ↑start₂
get₂ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₂).nodes.size), (↑nfa₂)[i] = (↑final)[i]
get₁ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₁).nodes.size), (↑nfa₁)[i] = (↑final)[i]
i : ℕ
cs₂ : List Char
step✝ : (↑final).stepIn nfa.nodes.size i (↑next) cs₂
j✝ : ℕ
cs₄ : List Char
rest : (↑final).pathIn nfa.nodes.size j✝ i cs₄
h₁✝ : nfa.nodes.size ≤ ↑(↑final).start
h₂✝ : ↑(↑final).start < (↑final).nodes.size
eqs : cs = cs₄ ++ cs₂
step : j✝ = ↑start₁ ∨ j✝ = ↑start₂
⊢ Expr.matches cs (r₁.alternate r₂)
Tactic:
cases step with
| inl eqs₁ =>
  rw [eqs₁] at rest
  have : pathToNext final next nfa.nodes.size nfa₁.val.start.val cs :=
    ⟨i, cs₄, cs₂, eqs, eq₂ ▸ rest, step⟩
  have : pathToNext nfa₁ next nfa.nodes.size nfa₁.val.start.val cs := by
    apply this.cast' nfa₁.val.start.isLt
      (Nat.le_of_lt (Nat.lt_trans nfa₂.property final.property))
      get₁
  exact .alternateLeft (ih₁ eq₁.symm this)
| inr eqs₂ =>
  rw [eqs₂] at rest
  have : pathToNext final next nfa.nodes.size nfa₂.val.start.val cs :=
    ⟨i, cs₄, cs₂, eqs, eq₄ ▸ rest, step⟩
  have : pathToNext nfa₂ next nfa.nodes.size nfa₂.val.start.val cs := by
    apply this.cast' nfa₂.val.start.isLt (Nat.le_of_lt final.property) get₂
  have : pathToNext nfa₂ next nfa₁.val.nodes.size nfa₂.val.start.val cs := by
    apply this.castLE (ge_pushRegex_start eq₃.symm)
    intro i j h₁ h₂ step hj
    have := eq_or_ge_of_step_pushRegex eq₃.symm h₁ h₂ step
    simp at this
    cases this with
    | inl eq =>
      exfalso
      rw [eq] at hj
      exact Nat.not_le_of_gt next.isLt hj
    | inr ge => exact ge
  exact .alternateRight (ih₂ eq₃.symm this)
State after:
no goals

State before:
case intro.intro.intro.intro.intro.step.εStep.inl
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Expr
result : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq : nfa.pushRegex next (r₁.alternate r₂) = result
ih₁ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₁ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₁
ih₂ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₂ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₂
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)
final : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑final).nodes.size
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
eq₄ : start₂ = (↑nfa₂).start
eq₅ : final = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds
eq' : result = ⟨↑final, property⟩
startNode : (↑final)[↑(↑final).start] = Node.split ↑start₁ ↑start₂
neStart₁ : ↑next ≠ ↑start₁
neStart₂ : ↑next ≠ ↑start₂
get₂ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₂).nodes.size), (↑nfa₂)[i] = (↑final)[i]
get₁ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₁).nodes.size), (↑nfa₁)[i] = (↑final)[i]
i : ℕ
cs₂ : List Char
step : (↑final).stepIn nfa.nodes.size i (↑next) cs₂
j✝ : ℕ
cs₄ : List Char
rest : (↑final).pathIn nfa.nodes.size j✝ i cs₄
h₁✝ : nfa.nodes.size ≤ ↑(↑final).start
h₂✝ : ↑(↑final).start < (↑final).nodes.size
eqs : cs = cs₄ ++ cs₂
eqs₁ : j✝ = ↑start₁
⊢ Expr.matches cs (r₁.alternate r₂)
Tactic:
rw [eqs₁] at rest
State after:
case intro.intro.intro.intro.intro.step.εStep.inl
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Expr
result : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq : nfa.pushRegex next (r₁.alternate r₂) = result
ih₁ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₁ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₁
ih₂ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₂ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₂
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)
final : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑final).nodes.size
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
eq₄ : start₂ = (↑nfa₂).start
eq₅ : final = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds
eq' : result = ⟨↑final, property⟩
startNode : (↑final)[↑(↑final).start] = Node.split ↑start₁ ↑start₂
neStart₁ : ↑next ≠ ↑start₁
neStart₂ : ↑next ≠ ↑start₂
get₂ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₂).nodes.size), (↑nfa₂)[i] = (↑final)[i]
get₁ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₁).nodes.size), (↑nfa₁)[i] = (↑final)[i]
i : ℕ
cs₂ : List Char
step : (↑final).stepIn nfa.nodes.size i (↑next) cs₂
j✝ : ℕ
cs₄ : List Char
rest : (↑final).pathIn nfa.nodes.size (↑start₁) i cs₄
h₁✝ : nfa.nodes.size ≤ ↑(↑final).start
h₂✝ : ↑(↑final).start < (↑final).nodes.size
eqs : cs = cs₄ ++ cs₂
eqs₁ : j✝ = ↑start₁
⊢ Expr.matches cs (r₁.alternate r₂)

State before:
case intro.intro.intro.intro.intro.step.εStep.inl
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Expr
result : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq : nfa.pushRegex next (r₁.alternate r₂) = result
ih₁ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₁ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₁
ih₂ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₂ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₂
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)
final : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑final).nodes.size
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
eq₄ : start₂ = (↑nfa₂).start
eq₅ : final = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds
eq' : result = ⟨↑final, property⟩
startNode : (↑final)[↑(↑final).start] = Node.split ↑start₁ ↑start₂
neStart₁ : ↑next ≠ ↑start₁
neStart₂ : ↑next ≠ ↑start₂
get₂ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₂).nodes.size), (↑nfa₂)[i] = (↑final)[i]
get₁ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₁).nodes.size), (↑nfa₁)[i] = (↑final)[i]
i : ℕ
cs₂ : List Char
step : (↑final).stepIn nfa.nodes.size i (↑next) cs₂
j✝ : ℕ
cs₄ : List Char
rest : (↑final).pathIn nfa.nodes.size (↑start₁) i cs₄
h₁✝ : nfa.nodes.size ≤ ↑(↑final).start
h₂✝ : ↑(↑final).start < (↑final).nodes.size
eqs : cs = cs₄ ++ cs₂
eqs₁ : j✝ = ↑start₁
⊢ Expr.matches cs (r₁.alternate r₂)
Tactic:
have : pathToNext final next nfa.nodes.size nfa₁.val.start.val cs :=
  ⟨i, cs₄, cs₂, eqs, eq₂ ▸ rest, step⟩
State after:
case intro.intro.intro.intro.intro.step.εStep.inl
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Expr
result : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq : nfa.pushRegex next (r₁.alternate r₂) = result
ih₁ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₁ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₁
ih₂ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₂ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₂
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)
final : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑final).nodes.size
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
eq₄ : start₂ = (↑nfa₂).start
eq₅ : final = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds
eq' : result = ⟨↑final, property⟩
startNode : (↑final)[↑(↑final).start] = Node.split ↑start₁ ↑start₂
neStart₁ : ↑next ≠ ↑start₁
neStart₂ : ↑next ≠ ↑start₂
get₂ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₂).nodes.size), (↑nfa₂)[i] = (↑final)[i]
get₁ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₁).nodes.size), (↑nfa₁)[i] = (↑final)[i]
i : ℕ
cs₂ : List Char
step : (↑final).stepIn nfa.nodes.size i (↑next) cs₂
j✝ : ℕ
cs₄ : List Char
rest : (↑final).pathIn nfa.nodes.size (↑start₁) i cs₄
h₁✝ : nfa.nodes.size ≤ ↑(↑final).start
h₂✝ : ↑(↑final).start < (↑final).nodes.size
eqs : cs = cs₄ ++ cs₂
eqs₁ : j✝ = ↑start₁
this : (↑final).pathToNext (↑next) nfa.nodes.size (↑(↑nfa₁).start) cs
⊢ Expr.matches cs (r₁.alternate r₂)

State before:
case intro.intro.intro.intro.intro.step.εStep.inl
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Expr
result : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq : nfa.pushRegex next (r₁.alternate r₂) = result
ih₁ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₁ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₁
ih₂ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₂ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₂
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)
final : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑final).nodes.size
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
eq₄ : start₂ = (↑nfa₂).start
eq₅ : final = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds
eq' : result = ⟨↑final, property⟩
startNode : (↑final)[↑(↑final).start] = Node.split ↑start₁ ↑start₂
neStart₁ : ↑next ≠ ↑start₁
neStart₂ : ↑next ≠ ↑start₂
get₂ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₂).nodes.size), (↑nfa₂)[i] = (↑final)[i]
get₁ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₁).nodes.size), (↑nfa₁)[i] = (↑final)[i]
i : ℕ
cs₂ : List Char
step : (↑final).stepIn nfa.nodes.size i (↑next) cs₂
j✝ : ℕ
cs₄ : List Char
rest : (↑final).pathIn nfa.nodes.size (↑start₁) i cs₄
h₁✝ : nfa.nodes.size ≤ ↑(↑final).start
h₂✝ : ↑(↑final).start < (↑final).nodes.size
eqs : cs = cs₄ ++ cs₂
eqs₁ : j✝ = ↑start₁
this : (↑final).pathToNext (↑next) nfa.nodes.size (↑(↑nfa₁).start) cs
⊢ Expr.matches cs (r₁.alternate r₂)
Tactic:
have : pathToNext nfa₁ next nfa.nodes.size nfa₁.val.start.val cs := by
  apply this.cast' nfa₁.val.start.isLt
    (Nat.le_of_lt (Nat.lt_trans nfa₂.property final.property))
    get₁
State after:
case intro.intro.intro.intro.intro.step.εStep.inl
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Expr
result : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq : nfa.pushRegex next (r₁.alternate r₂) = result
ih₁ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₁ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₁
ih₂ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₂ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₂
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)
final : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑final).nodes.size
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
eq₄ : start₂ = (↑nfa₂).start
eq₅ : final = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds
eq' : result = ⟨↑final, property⟩
startNode : (↑final)[↑(↑final).start] = Node.split ↑start₁ ↑start₂
neStart₁ : ↑next ≠ ↑start₁
neStart₂ : ↑next ≠ ↑start₂
get₂ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₂).nodes.size), (↑nfa₂)[i] = (↑final)[i]
get₁ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₁).nodes.size), (↑nfa₁)[i] = (↑final)[i]
i : ℕ
cs₂ : List Char
step : (↑final).stepIn nfa.nodes.size i (↑next) cs₂
j✝ : ℕ
cs₄ : List Char
rest : (↑final).pathIn nfa.nodes.size (↑start₁) i cs₄
h₁✝ : nfa.nodes.size ≤ ↑(↑final).start
h₂✝ : ↑(↑final).start < (↑final).nodes.size
eqs : cs = cs₄ ++ cs₂
eqs₁ : j✝ = ↑start₁
this✝ : (↑final).pathToNext (↑next) nfa.nodes.size (↑(↑nfa₁).start) cs
this : (↑nfa₁).pathToNext (↑next) nfa.nodes.size (↑(↑nfa₁).start) cs
⊢ Expr.matches cs (r₁.alternate r₂)

State before:
case intro.intro.intro.intro.intro.step.εStep.inl
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Expr
result : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq : nfa.pushRegex next (r₁.alternate r₂) = result
ih₁ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₁ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₁
ih₂ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₂ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₂
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)
final : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑final).nodes.size
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
eq₄ : start₂ = (↑nfa₂).start
eq₅ : final = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds
eq' : result = ⟨↑final, property⟩
startNode : (↑final)[↑(↑final).start] = Node.split ↑start₁ ↑start₂
neStart₁ : ↑next ≠ ↑start₁
neStart₂ : ↑next ≠ ↑start₂
get₂ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₂).nodes.size), (↑nfa₂)[i] = (↑final)[i]
get₁ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₁).nodes.size), (↑nfa₁)[i] = (↑final)[i]
i : ℕ
cs₂ : List Char
step : (↑final).stepIn nfa.nodes.size i (↑next) cs₂
j✝ : ℕ
cs₄ : List Char
rest : (↑final).pathIn nfa.nodes.size (↑start₁) i cs₄
h₁✝ : nfa.nodes.size ≤ ↑(↑final).start
h₂✝ : ↑(↑final).start < (↑final).nodes.size
eqs : cs = cs₄ ++ cs₂
eqs₁ : j✝ = ↑start₁
this✝ : (↑final).pathToNext (↑next) nfa.nodes.size (↑(↑nfa₁).start) cs
this : (↑nfa₁).pathToNext (↑next) nfa.nodes.size (↑(↑nfa₁).start) cs
⊢ Expr.matches cs (r₁.alternate r₂)
Tactic:
exact .alternateLeft (ih₁ eq₁.symm this)
State after:
no goals

State before:
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Expr
result : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq : nfa.pushRegex next (r₁.alternate r₂) = result
ih₁ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₁ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₁
ih₂ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₂ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₂
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)
final : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑final).nodes.size
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
eq₄ : start₂ = (↑nfa₂).start
eq₅ : final = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds
eq' : result = ⟨↑final, property⟩
startNode : (↑final)[↑(↑final).start] = Node.split ↑start₁ ↑start₂
neStart₁ : ↑next ≠ ↑start₁
neStart₂ : ↑next ≠ ↑start₂
get₂ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₂).nodes.size), (↑nfa₂)[i] = (↑final)[i]
get₁ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₁).nodes.size), (↑nfa₁)[i] = (↑final)[i]
i : ℕ
cs₂ : List Char
step : (↑final).stepIn nfa.nodes.size i (↑next) cs₂
j✝ : ℕ
cs₄ : List Char
rest : (↑final).pathIn nfa.nodes.size (↑start₁) i cs₄
h₁✝ : nfa.nodes.size ≤ ↑(↑final).start
h₂✝ : ↑(↑final).start < (↑final).nodes.size
eqs : cs = cs₄ ++ cs₂
eqs₁ : j✝ = ↑start₁
this : (↑final).pathToNext (↑next) nfa.nodes.size (↑(↑nfa₁).start) cs
⊢ (↑nfa₁).pathToNext (↑next) nfa.nodes.size (↑(↑nfa₁).start) cs
Tactic:
apply this.cast' nfa₁.val.start.isLt
  (Nat.le_of_lt (Nat.lt_trans nfa₂.property final.property))
  get₁
State after:
no goals

State before:
case intro.intro.intro.intro.intro.step.εStep.inr
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Expr
result : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq : nfa.pushRegex next (r₁.alternate r₂) = result
ih₁ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₁ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₁
ih₂ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₂ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₂
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)
final : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑final).nodes.size
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
eq₄ : start₂ = (↑nfa₂).start
eq₅ : final = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds
eq' : result = ⟨↑final, property⟩
startNode : (↑final)[↑(↑final).start] = Node.split ↑start₁ ↑start₂
neStart₁ : ↑next ≠ ↑start₁
neStart₂ : ↑next ≠ ↑start₂
get₂ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₂).nodes.size), (↑nfa₂)[i] = (↑final)[i]
get₁ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₁).nodes.size), (↑nfa₁)[i] = (↑final)[i]
i : ℕ
cs₂ : List Char
step : (↑final).stepIn nfa.nodes.size i (↑next) cs₂
j✝ : ℕ
cs₄ : List Char
rest : (↑final).pathIn nfa.nodes.size j✝ i cs₄
h₁✝ : nfa.nodes.size ≤ ↑(↑final).start
h₂✝ : ↑(↑final).start < (↑final).nodes.size
eqs : cs = cs₄ ++ cs₂
eqs₂ : j✝ = ↑start₂
⊢ Expr.matches cs (r₁.alternate r₂)
Tactic:
rw [eqs₂] at rest
State after:
case intro.intro.intro.intro.intro.step.εStep.inr
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Expr
result : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq : nfa.pushRegex next (r₁.alternate r₂) = result
ih₁ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₁ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₁
ih₂ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₂ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₂
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)
final : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑final).nodes.size
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
eq₄ : start₂ = (↑nfa₂).start
eq₅ : final = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds
eq' : result = ⟨↑final, property⟩
startNode : (↑final)[↑(↑final).start] = Node.split ↑start₁ ↑start₂
neStart₁ : ↑next ≠ ↑start₁
neStart₂ : ↑next ≠ ↑start₂
get₂ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₂).nodes.size), (↑nfa₂)[i] = (↑final)[i]
get₁ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₁).nodes.size), (↑nfa₁)[i] = (↑final)[i]
i : ℕ
cs₂ : List Char
step : (↑final).stepIn nfa.nodes.size i (↑next) cs₂
j✝ : ℕ
cs₄ : List Char
rest : (↑final).pathIn nfa.nodes.size (↑start₂) i cs₄
h₁✝ : nfa.nodes.size ≤ ↑(↑final).start
h₂✝ : ↑(↑final).start < (↑final).nodes.size
eqs : cs = cs₄ ++ cs₂
eqs₂ : j✝ = ↑start₂
⊢ Expr.matches cs (r₁.alternate r₂)

State before:
case intro.intro.intro.intro.intro.step.εStep.inr
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Expr
result : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq : nfa.pushRegex next (r₁.alternate r₂) = result
ih₁ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₁ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₁
ih₂ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₂ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₂
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)
final : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑final).nodes.size
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
eq₄ : start₂ = (↑nfa₂).start
eq₅ : final = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds
eq' : result = ⟨↑final, property⟩
startNode : (↑final)[↑(↑final).start] = Node.split ↑start₁ ↑start₂
neStart₁ : ↑next ≠ ↑start₁
neStart₂ : ↑next ≠ ↑start₂
get₂ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₂).nodes.size), (↑nfa₂)[i] = (↑final)[i]
get₁ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₁).nodes.size), (↑nfa₁)[i] = (↑final)[i]
i : ℕ
cs₂ : List Char
step : (↑final).stepIn nfa.nodes.size i (↑next) cs₂
j✝ : ℕ
cs₄ : List Char
rest : (↑final).pathIn nfa.nodes.size (↑start₂) i cs₄
h₁✝ : nfa.nodes.size ≤ ↑(↑final).start
h₂✝ : ↑(↑final).start < (↑final).nodes.size
eqs : cs = cs₄ ++ cs₂
eqs₂ : j✝ = ↑start₂
⊢ Expr.matches cs (r₁.alternate r₂)
Tactic:
have : pathToNext final next nfa.nodes.size nfa₂.val.start.val cs :=
  ⟨i, cs₄, cs₂, eqs, eq₄ ▸ rest, step⟩
State after:
case intro.intro.intro.intro.intro.step.εStep.inr
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Expr
result : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq : nfa.pushRegex next (r₁.alternate r₂) = result
ih₁ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₁ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₁
ih₂ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₂ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₂
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)
final : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑final).nodes.size
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
eq₄ : start₂ = (↑nfa₂).start
eq₅ : final = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds
eq' : result = ⟨↑final, property⟩
startNode : (↑final)[↑(↑final).start] = Node.split ↑start₁ ↑start₂
neStart₁ : ↑next ≠ ↑start₁
neStart₂ : ↑next ≠ ↑start₂
get₂ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₂).nodes.size), (↑nfa₂)[i] = (↑final)[i]
get₁ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₁).nodes.size), (↑nfa₁)[i] = (↑final)[i]
i : ℕ
cs₂ : List Char
step : (↑final).stepIn nfa.nodes.size i (↑next) cs₂
j✝ : ℕ
cs₄ : List Char
rest : (↑final).pathIn nfa.nodes.size (↑start₂) i cs₄
h₁✝ : nfa.nodes.size ≤ ↑(↑final).start
h₂✝ : ↑(↑final).start < (↑final).nodes.size
eqs : cs = cs₄ ++ cs₂
eqs₂ : j✝ = ↑start₂
this : (↑final).pathToNext (↑next) nfa.nodes.size (↑(↑nfa₂).start) cs
⊢ Expr.matches cs (r₁.alternate r₂)

State before:
case intro.intro.intro.intro.intro.step.εStep.inr
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Expr
result : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq : nfa.pushRegex next (r₁.alternate r₂) = result
ih₁ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₁ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₁
ih₂ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₂ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₂
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)
final : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑final).nodes.size
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
eq₄ : start₂ = (↑nfa₂).start
eq₅ : final = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds
eq' : result = ⟨↑final, property⟩
startNode : (↑final)[↑(↑final).start] = Node.split ↑start₁ ↑start₂
neStart₁ : ↑next ≠ ↑start₁
neStart₂ : ↑next ≠ ↑start₂
get₂ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₂).nodes.size), (↑nfa₂)[i] = (↑final)[i]
get₁ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₁).nodes.size), (↑nfa₁)[i] = (↑final)[i]
i : ℕ
cs₂ : List Char
step : (↑final).stepIn nfa.nodes.size i (↑next) cs₂
j✝ : ℕ
cs₄ : List Char
rest : (↑final).pathIn nfa.nodes.size (↑start₂) i cs₄
h₁✝ : nfa.nodes.size ≤ ↑(↑final).start
h₂✝ : ↑(↑final).start < (↑final).nodes.size
eqs : cs = cs₄ ++ cs₂
eqs₂ : j✝ = ↑start₂
this : (↑final).pathToNext (↑next) nfa.nodes.size (↑(↑nfa₂).start) cs
⊢ Expr.matches cs (r₁.alternate r₂)
Tactic:
have : pathToNext nfa₂ next nfa.nodes.size nfa₂.val.start.val cs := by
  apply this.cast' nfa₂.val.start.isLt (Nat.le_of_lt final.property) get₂
State after:
case intro.intro.intro.intro.intro.step.εStep.inr
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Expr
result : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq : nfa.pushRegex next (r₁.alternate r₂) = result
ih₁ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₁ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₁
ih₂ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₂ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₂
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)
final : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑final).nodes.size
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
eq₄ : start₂ = (↑nfa₂).start
eq₅ : final = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds
eq' : result = ⟨↑final, property⟩
startNode : (↑final)[↑(↑final).start] = Node.split ↑start₁ ↑start₂
neStart₁ : ↑next ≠ ↑start₁
neStart₂ : ↑next ≠ ↑start₂
get₂ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₂).nodes.size), (↑nfa₂)[i] = (↑final)[i]
get₁ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₁).nodes.size), (↑nfa₁)[i] = (↑final)[i]
i : ℕ
cs₂ : List Char
step : (↑final).stepIn nfa.nodes.size i (↑next) cs₂
j✝ : ℕ
cs₄ : List Char
rest : (↑final).pathIn nfa.nodes.size (↑start₂) i cs₄
h₁✝ : nfa.nodes.size ≤ ↑(↑final).start
h₂✝ : ↑(↑final).start < (↑final).nodes.size
eqs : cs = cs₄ ++ cs₂
eqs₂ : j✝ = ↑start₂
this✝ : (↑final).pathToNext (↑next) nfa.nodes.size (↑(↑nfa₂).start) cs
this : (↑nfa₂).pathToNext (↑next) nfa.nodes.size (↑(↑nfa₂).start) cs
⊢ Expr.matches cs (r₁.alternate r₂)

State before:
case intro.intro.intro.intro.intro.step.εStep.inr
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Expr
result : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq : nfa.pushRegex next (r₁.alternate r₂) = result
ih₁ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₁ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₁
ih₂ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₂ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₂
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)
final : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑final).nodes.size
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
eq₄ : start₂ = (↑nfa₂).start
eq₅ : final = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds
eq' : result = ⟨↑final, property⟩
startNode : (↑final)[↑(↑final).start] = Node.split ↑start₁ ↑start₂
neStart₁ : ↑next ≠ ↑start₁
neStart₂ : ↑next ≠ ↑start₂
get₂ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₂).nodes.size), (↑nfa₂)[i] = (↑final)[i]
get₁ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₁).nodes.size), (↑nfa₁)[i] = (↑final)[i]
i : ℕ
cs₂ : List Char
step : (↑final).stepIn nfa.nodes.size i (↑next) cs₂
j✝ : ℕ
cs₄ : List Char
rest : (↑final).pathIn nfa.nodes.size (↑start₂) i cs₄
h₁✝ : nfa.nodes.size ≤ ↑(↑final).start
h₂✝ : ↑(↑final).start < (↑final).nodes.size
eqs : cs = cs₄ ++ cs₂
eqs₂ : j✝ = ↑start₂
this✝ : (↑final).pathToNext (↑next) nfa.nodes.size (↑(↑nfa₂).start) cs
this : (↑nfa₂).pathToNext (↑next) nfa.nodes.size (↑(↑nfa₂).start) cs
⊢ Expr.matches cs (r₁.alternate r₂)
Tactic:
have : pathToNext nfa₂ next nfa₁.val.nodes.size nfa₂.val.start.val cs := by
  apply this.castLE (ge_pushRegex_start eq₃.symm)
  intro i j h₁ h₂ step hj
  have := eq_or_ge_of_step_pushRegex eq₃.symm h₁ h₂ step
  simp at this
  cases this with
  | inl eq =>
    exfalso
    rw [eq] at hj
    exact Nat.not_le_of_gt next.isLt hj
  | inr ge => exact ge
State after:
case intro.intro.intro.intro.intro.step.εStep.inr
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Expr
result : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq : nfa.pushRegex next (r₁.alternate r₂) = result
ih₁ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₁ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₁
ih₂ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₂ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₂
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)
final : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑final).nodes.size
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
eq₄ : start₂ = (↑nfa₂).start
eq₅ : final = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds
eq' : result = ⟨↑final, property⟩
startNode : (↑final)[↑(↑final).start] = Node.split ↑start₁ ↑start₂
neStart₁ : ↑next ≠ ↑start₁
neStart₂ : ↑next ≠ ↑start₂
get₂ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₂).nodes.size), (↑nfa₂)[i] = (↑final)[i]
get₁ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₁).nodes.size), (↑nfa₁)[i] = (↑final)[i]
i : ℕ
cs₂ : List Char
step : (↑final).stepIn nfa.nodes.size i (↑next) cs₂
j✝ : ℕ
cs₄ : List Char
rest : (↑final).pathIn nfa.nodes.size (↑start₂) i cs₄
h₁✝ : nfa.nodes.size ≤ ↑(↑final).start
h₂✝ : ↑(↑final).start < (↑final).nodes.size
eqs : cs = cs₄ ++ cs₂
eqs₂ : j✝ = ↑start₂
this✝¹ : (↑final).pathToNext (↑next) nfa.nodes.size (↑(↑nfa₂).start) cs
this✝ : (↑nfa₂).pathToNext (↑next) nfa.nodes.size (↑(↑nfa₂).start) cs
this : (↑nfa₂).pathToNext (↑next) (↑nfa₁).nodes.size (↑(↑nfa₂).start) cs
⊢ Expr.matches cs (r₁.alternate r₂)

State before:
case intro.intro.intro.intro.intro.step.εStep.inr
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Expr
result : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq : nfa.pushRegex next (r₁.alternate r₂) = result
ih₁ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₁ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₁
ih₂ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₂ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₂
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)
final : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑final).nodes.size
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
eq₄ : start₂ = (↑nfa₂).start
eq₅ : final = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds
eq' : result = ⟨↑final, property⟩
startNode : (↑final)[↑(↑final).start] = Node.split ↑start₁ ↑start₂
neStart₁ : ↑next ≠ ↑start₁
neStart₂ : ↑next ≠ ↑start₂
get₂ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₂).nodes.size), (↑nfa₂)[i] = (↑final)[i]
get₁ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₁).nodes.size), (↑nfa₁)[i] = (↑final)[i]
i : ℕ
cs₂ : List Char
step : (↑final).stepIn nfa.nodes.size i (↑next) cs₂
j✝ : ℕ
cs₄ : List Char
rest : (↑final).pathIn nfa.nodes.size (↑start₂) i cs₄
h₁✝ : nfa.nodes.size ≤ ↑(↑final).start
h₂✝ : ↑(↑final).start < (↑final).nodes.size
eqs : cs = cs₄ ++ cs₂
eqs₂ : j✝ = ↑start₂
this✝¹ : (↑final).pathToNext (↑next) nfa.nodes.size (↑(↑nfa₂).start) cs
this✝ : (↑nfa₂).pathToNext (↑next) nfa.nodes.size (↑(↑nfa₂).start) cs
this : (↑nfa₂).pathToNext (↑next) (↑nfa₁).nodes.size (↑(↑nfa₂).start) cs
⊢ Expr.matches cs (r₁.alternate r₂)
Tactic:
exact .alternateRight (ih₂ eq₃.symm this)
State after:
no goals

State before:
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Expr
result : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq : nfa.pushRegex next (r₁.alternate r₂) = result
ih₁ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₁ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₁
ih₂ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₂ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₂
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)
final : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑final).nodes.size
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
eq₄ : start₂ = (↑nfa₂).start
eq₅ : final = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds
eq' : result = ⟨↑final, property⟩
startNode : (↑final)[↑(↑final).start] = Node.split ↑start₁ ↑start₂
neStart₁ : ↑next ≠ ↑start₁
neStart₂ : ↑next ≠ ↑start₂
get₂ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₂).nodes.size), (↑nfa₂)[i] = (↑final)[i]
get₁ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₁).nodes.size), (↑nfa₁)[i] = (↑final)[i]
i : ℕ
cs₂ : List Char
step : (↑final).stepIn nfa.nodes.size i (↑next) cs₂
j✝ : ℕ
cs₄ : List Char
rest : (↑final).pathIn nfa.nodes.size (↑start₂) i cs₄
h₁✝ : nfa.nodes.size ≤ ↑(↑final).start
h₂✝ : ↑(↑final).start < (↑final).nodes.size
eqs : cs = cs₄ ++ cs₂
eqs₂ : j✝ = ↑start₂
this : (↑final).pathToNext (↑next) nfa.nodes.size (↑(↑nfa₂).start) cs
⊢ (↑nfa₂).pathToNext (↑next) nfa.nodes.size (↑(↑nfa₂).start) cs
Tactic:
apply this.cast' nfa₂.val.start.isLt (Nat.le_of_lt final.property) get₂
State after:
no goals

State before:
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Expr
result : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq : nfa.pushRegex next (r₁.alternate r₂) = result
ih₁ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₁ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₁
ih₂ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₂ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₂
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)
final : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑final).nodes.size
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
eq₄ : start₂ = (↑nfa₂).start
eq₅ : final = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds
eq' : result = ⟨↑final, property⟩
startNode : (↑final)[↑(↑final).start] = Node.split ↑start₁ ↑start₂
neStart₁ : ↑next ≠ ↑start₁
neStart₂ : ↑next ≠ ↑start₂
get₂ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₂).nodes.size), (↑nfa₂)[i] = (↑final)[i]
get₁ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₁).nodes.size), (↑nfa₁)[i] = (↑final)[i]
i : ℕ
cs₂ : List Char
step : (↑final).stepIn nfa.nodes.size i (↑next) cs₂
j✝ : ℕ
cs₄ : List Char
rest : (↑final).pathIn nfa.nodes.size (↑start₂) i cs₄
h₁✝ : nfa.nodes.size ≤ ↑(↑final).start
h₂✝ : ↑(↑final).start < (↑final).nodes.size
eqs : cs = cs₄ ++ cs₂
eqs₂ : j✝ = ↑start₂
this✝ : (↑final).pathToNext (↑next) nfa.nodes.size (↑(↑nfa₂).start) cs
this : (↑nfa₂).pathToNext (↑next) nfa.nodes.size (↑(↑nfa₂).start) cs
⊢ (↑nfa₂).pathToNext (↑next) (↑nfa₁).nodes.size (↑(↑nfa₂).start) cs
Tactic:
apply this.castLE (ge_pushRegex_start eq₃.symm)
State after:
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Expr
result : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq : nfa.pushRegex next (r₁.alternate r₂) = result
ih₁ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₁ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₁
ih₂ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₂ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₂
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)
final : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑final).nodes.size
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
eq₄ : start₂ = (↑nfa₂).start
eq₅ : final = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds
eq' : result = ⟨↑final, property⟩
startNode : (↑final)[↑(↑final).start] = Node.split ↑start₁ ↑start₂
neStart₁ : ↑next ≠ ↑start₁
neStart₂ : ↑next ≠ ↑start₂
get₂ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₂).nodes.size), (↑nfa₂)[i] = (↑final)[i]
get₁ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₁).nodes.size), (↑nfa₁)[i] = (↑final)[i]
i : ℕ
cs₂ : List Char
step : (↑final).stepIn nfa.nodes.size i (↑next) cs₂
j✝ : ℕ
cs₄ : List Char
rest : (↑final).pathIn nfa.nodes.size (↑start₂) i cs₄
h₁✝ : nfa.nodes.size ≤ ↑(↑final).start
h₂✝ : ↑(↑final).start < (↑final).nodes.size
eqs : cs = cs₄ ++ cs₂
eqs₂ : j✝ = ↑start₂
this✝ : (↑final).pathToNext (↑next) nfa.nodes.size (↑(↑nfa₂).start) cs
this : (↑nfa₂).pathToNext (↑next) nfa.nodes.size (↑(↑nfa₂).start) cs
⊢ ∀ (i j : ℕ),
    (↑nfa₁).nodes.size ≤ i →
      ∀ (h₂ : i < (↑nfa₂).nodes.size),
        (∃ c, j ∈ (↑nfa₂)[i].charStep c) ∨ j ∈ (↑nfa₂)[i].εStep → nfa.nodes.size ≤ j → (↑nfa₁).nodes.size ≤ j

State before:
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Expr
result : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq : nfa.pushRegex next (r₁.alternate r₂) = result
ih₁ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₁ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₁
ih₂ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₂ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₂
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)
final : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑final).nodes.size
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
eq₄ : start₂ = (↑nfa₂).start
eq₅ : final = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds
eq' : result = ⟨↑final, property⟩
startNode : (↑final)[↑(↑final).start] = Node.split ↑start₁ ↑start₂
neStart₁ : ↑next ≠ ↑start₁
neStart₂ : ↑next ≠ ↑start₂
get₂ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₂).nodes.size), (↑nfa₂)[i] = (↑final)[i]
get₁ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₁).nodes.size), (↑nfa₁)[i] = (↑final)[i]
i : ℕ
cs₂ : List Char
step : (↑final).stepIn nfa.nodes.size i (↑next) cs₂
j✝ : ℕ
cs₄ : List Char
rest : (↑final).pathIn nfa.nodes.size (↑start₂) i cs₄
h₁✝ : nfa.nodes.size ≤ ↑(↑final).start
h₂✝ : ↑(↑final).start < (↑final).nodes.size
eqs : cs = cs₄ ++ cs₂
eqs₂ : j✝ = ↑start₂
this✝ : (↑final).pathToNext (↑next) nfa.nodes.size (↑(↑nfa₂).start) cs
this : (↑nfa₂).pathToNext (↑next) nfa.nodes.size (↑(↑nfa₂).start) cs
⊢ ∀ (i j : ℕ),
    (↑nfa₁).nodes.size ≤ i →
      ∀ (h₂ : i < (↑nfa₂).nodes.size),
        (∃ c, j ∈ (↑nfa₂)[i].charStep c) ∨ j ∈ (↑nfa₂)[i].εStep → nfa.nodes.size ≤ j → (↑nfa₁).nodes.size ≤ j
Tactic:
intro i j h₁ h₂ step hj
State after:
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Expr
result : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq : nfa.pushRegex next (r₁.alternate r₂) = result
ih₁ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₁ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₁
ih₂ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₂ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₂
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)
final : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑final).nodes.size
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
eq₄ : start₂ = (↑nfa₂).start
eq₅ : final = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds
eq' : result = ⟨↑final, property⟩
startNode : (↑final)[↑(↑final).start] = Node.split ↑start₁ ↑start₂
neStart₁ : ↑next ≠ ↑start₁
neStart₂ : ↑next ≠ ↑start₂
get₂ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₂).nodes.size), (↑nfa₂)[i] = (↑final)[i]
get₁ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₁).nodes.size), (↑nfa₁)[i] = (↑final)[i]
i✝ : ℕ
cs₂ : List Char
step✝ : (↑final).stepIn nfa.nodes.size i✝ (↑next) cs₂
j✝ : ℕ
cs₄ : List Char
rest : (↑final).pathIn nfa.nodes.size (↑start₂) i✝ cs₄
h₁✝ : nfa.nodes.size ≤ ↑(↑final).start
h₂✝ : ↑(↑final).start < (↑final).nodes.size
eqs : cs = cs₄ ++ cs₂
eqs₂ : j✝ = ↑start₂
this✝ : (↑final).pathToNext (↑next) nfa.nodes.size (↑(↑nfa₂).start) cs
this : (↑nfa₂).pathToNext (↑next) nfa.nodes.size (↑(↑nfa₂).start) cs
i j : ℕ
h₁ : (↑nfa₁).nodes.size ≤ i
h₂ : i < (↑nfa₂).nodes.size
step : (∃ c, j ∈ (↑nfa₂)[i].charStep c) ∨ j ∈ (↑nfa₂)[i].εStep
hj : nfa.nodes.size ≤ j
⊢ (↑nfa₁).nodes.size ≤ j

State before:
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Expr
result : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq : nfa.pushRegex next (r₁.alternate r₂) = result
ih₁ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₁ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₁
ih₂ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₂ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₂
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)
final : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑final).nodes.size
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
eq₄ : start₂ = (↑nfa₂).start
eq₅ : final = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds
eq' : result = ⟨↑final, property⟩
startNode : (↑final)[↑(↑final).start] = Node.split ↑start₁ ↑start₂
neStart₁ : ↑next ≠ ↑start₁
neStart₂ : ↑next ≠ ↑start₂
get₂ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₂).nodes.size), (↑nfa₂)[i] = (↑final)[i]
get₁ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₁).nodes.size), (↑nfa₁)[i] = (↑final)[i]
i✝ : ℕ
cs₂ : List Char
step✝ : (↑final).stepIn nfa.nodes.size i✝ (↑next) cs₂
j✝ : ℕ
cs₄ : List Char
rest : (↑final).pathIn nfa.nodes.size (↑start₂) i✝ cs₄
h₁✝ : nfa.nodes.size ≤ ↑(↑final).start
h₂✝ : ↑(↑final).start < (↑final).nodes.size
eqs : cs = cs₄ ++ cs₂
eqs₂ : j✝ = ↑start₂
this✝ : (↑final).pathToNext (↑next) nfa.nodes.size (↑(↑nfa₂).start) cs
this : (↑nfa₂).pathToNext (↑next) nfa.nodes.size (↑(↑nfa₂).start) cs
i j : ℕ
h₁ : (↑nfa₁).nodes.size ≤ i
h₂ : i < (↑nfa₂).nodes.size
step : (∃ c, j ∈ (↑nfa₂)[i].charStep c) ∨ j ∈ (↑nfa₂)[i].εStep
hj : nfa.nodes.size ≤ j
⊢ (↑nfa₁).nodes.size ≤ j
Tactic:
have := eq_or_ge_of_step_pushRegex eq₃.symm h₁ h₂ step
State after:
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Expr
result : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq : nfa.pushRegex next (r₁.alternate r₂) = result
ih₁ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₁ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₁
ih₂ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₂ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₂
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)
final : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑final).nodes.size
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
eq₄ : start₂ = (↑nfa₂).start
eq₅ : final = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds
eq' : result = ⟨↑final, property⟩
startNode : (↑final)[↑(↑final).start] = Node.split ↑start₁ ↑start₂
neStart₁ : ↑next ≠ ↑start₁
neStart₂ : ↑next ≠ ↑start₂
get₂ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₂).nodes.size), (↑nfa₂)[i] = (↑final)[i]
get₁ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₁).nodes.size), (↑nfa₁)[i] = (↑final)[i]
i✝ : ℕ
cs₂ : List Char
step✝ : (↑final).stepIn nfa.nodes.size i✝ (↑next) cs₂
j✝ : ℕ
cs₄ : List Char
rest : (↑final).pathIn nfa.nodes.size (↑start₂) i✝ cs₄
h₁✝ : nfa.nodes.size ≤ ↑(↑final).start
h₂✝ : ↑(↑final).start < (↑final).nodes.size
eqs : cs = cs₄ ++ cs₂
eqs₂ : j✝ = ↑start₂
this✝¹ : (↑final).pathToNext (↑next) nfa.nodes.size (↑(↑nfa₂).start) cs
this✝ : (↑nfa₂).pathToNext (↑next) nfa.nodes.size (↑(↑nfa₂).start) cs
i j : ℕ
h₁ : (↑nfa₁).nodes.size ≤ i
h₂ : i < (↑nfa₂).nodes.size
step : (∃ c, j ∈ (↑nfa₂)[i].charStep c) ∨ j ∈ (↑nfa₂)[i].εStep
hj : nfa.nodes.size ≤ j
this : j = ↑⟨↑next, ⋯⟩ ∨ (↑nfa₁).nodes.size ≤ j
⊢ (↑nfa₁).nodes.size ≤ j

State before:
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Expr
result : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq : nfa.pushRegex next (r₁.alternate r₂) = result
ih₁ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₁ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₁
ih₂ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₂ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₂
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)
final : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑final).nodes.size
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
eq₄ : start₂ = (↑nfa₂).start
eq₅ : final = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds
eq' : result = ⟨↑final, property⟩
startNode : (↑final)[↑(↑final).start] = Node.split ↑start₁ ↑start₂
neStart₁ : ↑next ≠ ↑start₁
neStart₂ : ↑next ≠ ↑start₂
get₂ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₂).nodes.size), (↑nfa₂)[i] = (↑final)[i]
get₁ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₁).nodes.size), (↑nfa₁)[i] = (↑final)[i]
i✝ : ℕ
cs₂ : List Char
step✝ : (↑final).stepIn nfa.nodes.size i✝ (↑next) cs₂
j✝ : ℕ
cs₄ : List Char
rest : (↑final).pathIn nfa.nodes.size (↑start₂) i✝ cs₄
h₁✝ : nfa.nodes.size ≤ ↑(↑final).start
h₂✝ : ↑(↑final).start < (↑final).nodes.size
eqs : cs = cs₄ ++ cs₂
eqs₂ : j✝ = ↑start₂
this✝¹ : (↑final).pathToNext (↑next) nfa.nodes.size (↑(↑nfa₂).start) cs
this✝ : (↑nfa₂).pathToNext (↑next) nfa.nodes.size (↑(↑nfa₂).start) cs
i j : ℕ
h₁ : (↑nfa₁).nodes.size ≤ i
h₂ : i < (↑nfa₂).nodes.size
step : (∃ c, j ∈ (↑nfa₂)[i].charStep c) ∨ j ∈ (↑nfa₂)[i].εStep
hj : nfa.nodes.size ≤ j
this : j = ↑⟨↑next, ⋯⟩ ∨ (↑nfa₁).nodes.size ≤ j
⊢ (↑nfa₁).nodes.size ≤ j
Tactic:
simp at this
State after:
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Expr
result : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq : nfa.pushRegex next (r₁.alternate r₂) = result
ih₁ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₁ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₁
ih₂ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₂ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₂
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)
final : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑final).nodes.size
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
eq₄ : start₂ = (↑nfa₂).start
eq₅ : final = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds
eq' : result = ⟨↑final, property⟩
startNode : (↑final)[↑(↑final).start] = Node.split ↑start₁ ↑start₂
neStart₁ : ↑next ≠ ↑start₁
neStart₂ : ↑next ≠ ↑start₂
get₂ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₂).nodes.size), (↑nfa₂)[i] = (↑final)[i]
get₁ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₁).nodes.size), (↑nfa₁)[i] = (↑final)[i]
i✝ : ℕ
cs₂ : List Char
step✝ : (↑final).stepIn nfa.nodes.size i✝ (↑next) cs₂
j✝ : ℕ
cs₄ : List Char
rest : (↑final).pathIn nfa.nodes.size (↑start₂) i✝ cs₄
h₁✝ : nfa.nodes.size ≤ ↑(↑final).start
h₂✝ : ↑(↑final).start < (↑final).nodes.size
eqs : cs = cs₄ ++ cs₂
eqs₂ : j✝ = ↑start₂
this✝¹ : (↑final).pathToNext (↑next) nfa.nodes.size (↑(↑nfa₂).start) cs
this✝ : (↑nfa₂).pathToNext (↑next) nfa.nodes.size (↑(↑nfa₂).start) cs
i j : ℕ
h₁ : (↑nfa₁).nodes.size ≤ i
h₂ : i < (↑nfa₂).nodes.size
step : (∃ c, j ∈ (↑nfa₂)[i].charStep c) ∨ j ∈ (↑nfa₂)[i].εStep
hj : nfa.nodes.size ≤ j
this : j = ↑next ∨ (↑nfa₁).nodes.size ≤ j
⊢ (↑nfa₁).nodes.size ≤ j

State before:
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Expr
result : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq : nfa.pushRegex next (r₁.alternate r₂) = result
ih₁ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₁ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₁
ih₂ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₂ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₂
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)
final : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑final).nodes.size
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
eq₄ : start₂ = (↑nfa₂).start
eq₅ : final = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds
eq' : result = ⟨↑final, property⟩
startNode : (↑final)[↑(↑final).start] = Node.split ↑start₁ ↑start₂
neStart₁ : ↑next ≠ ↑start₁
neStart₂ : ↑next ≠ ↑start₂
get₂ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₂).nodes.size), (↑nfa₂)[i] = (↑final)[i]
get₁ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₁).nodes.size), (↑nfa₁)[i] = (↑final)[i]
i✝ : ℕ
cs₂ : List Char
step✝ : (↑final).stepIn nfa.nodes.size i✝ (↑next) cs₂
j✝ : ℕ
cs₄ : List Char
rest : (↑final).pathIn nfa.nodes.size (↑start₂) i✝ cs₄
h₁✝ : nfa.nodes.size ≤ ↑(↑final).start
h₂✝ : ↑(↑final).start < (↑final).nodes.size
eqs : cs = cs₄ ++ cs₂
eqs₂ : j✝ = ↑start₂
this✝¹ : (↑final).pathToNext (↑next) nfa.nodes.size (↑(↑nfa₂).start) cs
this✝ : (↑nfa₂).pathToNext (↑next) nfa.nodes.size (↑(↑nfa₂).start) cs
i j : ℕ
h₁ : (↑nfa₁).nodes.size ≤ i
h₂ : i < (↑nfa₂).nodes.size
step : (∃ c, j ∈ (↑nfa₂)[i].charStep c) ∨ j ∈ (↑nfa₂)[i].εStep
hj : nfa.nodes.size ≤ j
this : j = ↑next ∨ (↑nfa₁).nodes.size ≤ j
⊢ (↑nfa₁).nodes.size ≤ j
Tactic:
cases this with
| inl eq =>
  exfalso
  rw [eq] at hj
  exact Nat.not_le_of_gt next.isLt hj
| inr ge => exact ge
State after:
no goals

State before:
case inl
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Expr
result : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq✝ : nfa.pushRegex next (r₁.alternate r₂) = result
ih₁ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₁ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₁
ih₂ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₂ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₂
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)
final : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑final).nodes.size
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
eq₄ : start₂ = (↑nfa₂).start
eq₅ : final = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds
eq' : result = ⟨↑final, property⟩
startNode : (↑final)[↑(↑final).start] = Node.split ↑start₁ ↑start₂
neStart₁ : ↑next ≠ ↑start₁
neStart₂ : ↑next ≠ ↑start₂
get₂ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₂).nodes.size), (↑nfa₂)[i] = (↑final)[i]
get₁ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₁).nodes.size), (↑nfa₁)[i] = (↑final)[i]
i✝ : ℕ
cs₂ : List Char
step✝ : (↑final).stepIn nfa.nodes.size i✝ (↑next) cs₂
j✝ : ℕ
cs₄ : List Char
rest : (↑final).pathIn nfa.nodes.size (↑start₂) i✝ cs₄
h₁✝ : nfa.nodes.size ≤ ↑(↑final).start
h₂✝ : ↑(↑final).start < (↑final).nodes.size
eqs : cs = cs₄ ++ cs₂
eqs₂ : j✝ = ↑start₂
this✝ : (↑final).pathToNext (↑next) nfa.nodes.size (↑(↑nfa₂).start) cs
this : (↑nfa₂).pathToNext (↑next) nfa.nodes.size (↑(↑nfa₂).start) cs
i j : ℕ
h₁ : (↑nfa₁).nodes.size ≤ i
h₂ : i < (↑nfa₂).nodes.size
step : (∃ c, j ∈ (↑nfa₂)[i].charStep c) ∨ j ∈ (↑nfa₂)[i].εStep
hj : nfa.nodes.size ≤ j
eq : j = ↑next
⊢ (↑nfa₁).nodes.size ≤ j
Tactic:
exfalso
State after:
case inl
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Expr
result : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq✝ : nfa.pushRegex next (r₁.alternate r₂) = result
ih₁ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₁ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₁
ih₂ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₂ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₂
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)
final : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑final).nodes.size
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
eq₄ : start₂ = (↑nfa₂).start
eq₅ : final = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds
eq' : result = ⟨↑final, property⟩
startNode : (↑final)[↑(↑final).start] = Node.split ↑start₁ ↑start₂
neStart₁ : ↑next ≠ ↑start₁
neStart₂ : ↑next ≠ ↑start₂
get₂ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₂).nodes.size), (↑nfa₂)[i] = (↑final)[i]
get₁ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₁).nodes.size), (↑nfa₁)[i] = (↑final)[i]
i✝ : ℕ
cs₂ : List Char
step✝ : (↑final).stepIn nfa.nodes.size i✝ (↑next) cs₂
j✝ : ℕ
cs₄ : List Char
rest : (↑final).pathIn nfa.nodes.size (↑start₂) i✝ cs₄
h₁✝ : nfa.nodes.size ≤ ↑(↑final).start
h₂✝ : ↑(↑final).start < (↑final).nodes.size
eqs : cs = cs₄ ++ cs₂
eqs₂ : j✝ = ↑start₂
this✝ : (↑final).pathToNext (↑next) nfa.nodes.size (↑(↑nfa₂).start) cs
this : (↑nfa₂).pathToNext (↑next) nfa.nodes.size (↑(↑nfa₂).start) cs
i j : ℕ
h₁ : (↑nfa₁).nodes.size ≤ i
h₂ : i < (↑nfa₂).nodes.size
step : (∃ c, j ∈ (↑nfa₂)[i].charStep c) ∨ j ∈ (↑nfa₂)[i].εStep
hj : nfa.nodes.size ≤ j
eq : j = ↑next
⊢ False

State before:
case inl
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Expr
result : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq✝ : nfa.pushRegex next (r₁.alternate r₂) = result
ih₁ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₁ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₁
ih₂ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₂ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₂
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)
final : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑final).nodes.size
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
eq₄ : start₂ = (↑nfa₂).start
eq₅ : final = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds
eq' : result = ⟨↑final, property⟩
startNode : (↑final)[↑(↑final).start] = Node.split ↑start₁ ↑start₂
neStart₁ : ↑next ≠ ↑start₁
neStart₂ : ↑next ≠ ↑start₂
get₂ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₂).nodes.size), (↑nfa₂)[i] = (↑final)[i]
get₁ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₁).nodes.size), (↑nfa₁)[i] = (↑final)[i]
i✝ : ℕ
cs₂ : List Char
step✝ : (↑final).stepIn nfa.nodes.size i✝ (↑next) cs₂
j✝ : ℕ
cs₄ : List Char
rest : (↑final).pathIn nfa.nodes.size (↑start₂) i✝ cs₄
h₁✝ : nfa.nodes.size ≤ ↑(↑final).start
h₂✝ : ↑(↑final).start < (↑final).nodes.size
eqs : cs = cs₄ ++ cs₂
eqs₂ : j✝ = ↑start₂
this✝ : (↑final).pathToNext (↑next) nfa.nodes.size (↑(↑nfa₂).start) cs
this : (↑nfa₂).pathToNext (↑next) nfa.nodes.size (↑(↑nfa₂).start) cs
i j : ℕ
h₁ : (↑nfa₁).nodes.size ≤ i
h₂ : i < (↑nfa₂).nodes.size
step : (∃ c, j ∈ (↑nfa₂)[i].charStep c) ∨ j ∈ (↑nfa₂)[i].εStep
hj : nfa.nodes.size ≤ j
eq : j = ↑next
⊢ False
Tactic:
rw [eq] at hj
State after:
case inl
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Expr
result : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq✝ : nfa.pushRegex next (r₁.alternate r₂) = result
ih₁ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₁ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₁
ih₂ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₂ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₂
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)
final : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑final).nodes.size
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
eq₄ : start₂ = (↑nfa₂).start
eq₅ : final = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds
eq' : result = ⟨↑final, property⟩
startNode : (↑final)[↑(↑final).start] = Node.split ↑start₁ ↑start₂
neStart₁ : ↑next ≠ ↑start₁
neStart₂ : ↑next ≠ ↑start₂
get₂ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₂).nodes.size), (↑nfa₂)[i] = (↑final)[i]
get₁ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₁).nodes.size), (↑nfa₁)[i] = (↑final)[i]
i✝ : ℕ
cs₂ : List Char
step✝ : (↑final).stepIn nfa.nodes.size i✝ (↑next) cs₂
j✝ : ℕ
cs₄ : List Char
rest : (↑final).pathIn nfa.nodes.size (↑start₂) i✝ cs₄
h₁✝ : nfa.nodes.size ≤ ↑(↑final).start
h₂✝ : ↑(↑final).start < (↑final).nodes.size
eqs : cs = cs₄ ++ cs₂
eqs₂ : j✝ = ↑start₂
this✝ : (↑final).pathToNext (↑next) nfa.nodes.size (↑(↑nfa₂).start) cs
this : (↑nfa₂).pathToNext (↑next) nfa.nodes.size (↑(↑nfa₂).start) cs
i j : ℕ
h₁ : (↑nfa₁).nodes.size ≤ i
h₂ : i < (↑nfa₂).nodes.size
step : (∃ c, j ∈ (↑nfa₂)[i].charStep c) ∨ j ∈ (↑nfa₂)[i].εStep
hj : nfa.nodes.size ≤ ↑next
eq : j = ↑next
⊢ False

State before:
case inl
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Expr
result : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq✝ : nfa.pushRegex next (r₁.alternate r₂) = result
ih₁ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₁ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₁
ih₂ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₂ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₂
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)
final : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑final).nodes.size
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
eq₄ : start₂ = (↑nfa₂).start
eq₅ : final = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds
eq' : result = ⟨↑final, property⟩
startNode : (↑final)[↑(↑final).start] = Node.split ↑start₁ ↑start₂
neStart₁ : ↑next ≠ ↑start₁
neStart₂ : ↑next ≠ ↑start₂
get₂ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₂).nodes.size), (↑nfa₂)[i] = (↑final)[i]
get₁ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₁).nodes.size), (↑nfa₁)[i] = (↑final)[i]
i✝ : ℕ
cs₂ : List Char
step✝ : (↑final).stepIn nfa.nodes.size i✝ (↑next) cs₂
j✝ : ℕ
cs₄ : List Char
rest : (↑final).pathIn nfa.nodes.size (↑start₂) i✝ cs₄
h₁✝ : nfa.nodes.size ≤ ↑(↑final).start
h₂✝ : ↑(↑final).start < (↑final).nodes.size
eqs : cs = cs₄ ++ cs₂
eqs₂ : j✝ = ↑start₂
this✝ : (↑final).pathToNext (↑next) nfa.nodes.size (↑(↑nfa₂).start) cs
this : (↑nfa₂).pathToNext (↑next) nfa.nodes.size (↑(↑nfa₂).start) cs
i j : ℕ
h₁ : (↑nfa₁).nodes.size ≤ i
h₂ : i < (↑nfa₂).nodes.size
step : (∃ c, j ∈ (↑nfa₂)[i].charStep c) ∨ j ∈ (↑nfa₂)[i].εStep
hj : nfa.nodes.size ≤ ↑next
eq : j = ↑next
⊢ False
Tactic:
exact Nat.not_le_of_gt next.isLt hj
State after:
no goals

State before:
case inr
nfa : NFA
next : Fin nfa.nodes.size
r₁ r₂ : Expr
result : { nfa' // nfa.nodes.size < nfa'.nodes.size }
cs : List Char
eq : nfa.pushRegex next (r₁.alternate r₂) = result
ih₁ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₁ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₁
ih₂ :
  ∀ {nfa : NFA} {next : Fin nfa.nodes.size} {result : { nfa' // nfa.nodes.size < nfa'.nodes.size }} {cs : List Char},
    nfa.pushRegex next r₂ = result →
      (↑result).pathToNext (↑next) nfa.nodes.size (↑(↑result).start) cs → Expr.matches cs r₂
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)
final : { nfa' // (↑nfa₂).nodes.size < nfa'.nodes.size }
property : nfa.nodes.size < (↑final).nodes.size
eq₁ : nfa₁ = nfa.pushRegex next r₁
eq₂ : start₁ = (↑nfa₁).start
eq₃ : nfa₂ = (↑nfa₁).pushRegex ⟨↑next, ⋯⟩ r₂
eq₄ : start₂ = (↑nfa₂).start
eq₅ : final = (↑nfa₂).pushNode (Node.split ↑start₁ ↑start₂) inBounds
eq' : result = ⟨↑final, property⟩
startNode : (↑final)[↑(↑final).start] = Node.split ↑start₁ ↑start₂
neStart₁ : ↑next ≠ ↑start₁
neStart₂ : ↑next ≠ ↑start₂
get₂ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₂).nodes.size), (↑nfa₂)[i] = (↑final)[i]
get₁ : ∀ (i : ℕ), nfa.nodes.size ≤ i → ∀ (h₂ : i < (↑nfa₁).nodes.size), (↑nfa₁)[i] = (↑final)[i]
i✝ : ℕ
cs₂ : List Char
step✝ : (↑final).stepIn nfa.nodes.size i✝ (↑next) cs₂
j✝ : ℕ
cs₄ : List Char
rest : (↑final).pathIn nfa.nodes.size (↑start₂) i✝ cs₄
h₁✝ : nfa.nodes.size ≤ ↑(↑final).start
h₂✝ : ↑(↑final).start < (↑final).nodes.size
eqs : cs = cs₄ ++ cs₂
eqs₂ : j✝ = ↑start₂
this✝ : (↑final).pathToNext (↑next) nfa.nodes.size (↑(↑nfa₂).start) cs
this : (↑nfa₂).pathToNext (↑next) nfa.nodes.size (↑(↑nfa₂).start) cs
i j : ℕ
h₁ : (↑nfa₁).nodes.size ≤ i
h₂ : i < (↑nfa₂).nodes.size
step : (∃ c, j ∈ (↑nfa₂)[i].charStep c) ∨ j ∈ (↑nfa₂)[i].εStep
hj : nfa.nodes.size ≤ j
ge : (↑nfa₁).nodes.size ≤ j
⊢ (↑nfa₁).nodes.size ≤ j
Tactic:
exact ge
State after:
no goals