Theorem: Regex.VM.lower_bound_exploreεClosure (RegexCorrectness/VM/Auxiliary.lean)

State before:
nfa : NFA
pos : String.Pos
next : SparseSet nfa.nodes.size
currentSave : Array (Option String.Pos)
matched : Option (Array (Option String.Pos))
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin nfa.nodes.size
stack : Array (StackEntry nfa.nodes.size)
matched' : Option (Array (Option String.Pos))
next' : SparseSet nfa.nodes.size
saveSlots' : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
h : exploreεClosure nfa pos next currentSave matched saveSlots target stack = (matched', next', saveSlots')
inv : LowerInvExploreεClosure nfa next target stack
⊢ LowerBoundεClosure nfa target next next'
Tactic:
intro j hj
State after:
nfa : NFA
pos : String.Pos
next : SparseSet nfa.nodes.size
currentSave : Array (Option String.Pos)
matched : Option (Array (Option String.Pos))
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin nfa.nodes.size
stack : Array (StackEntry nfa.nodes.size)
matched' : Option (Array (Option String.Pos))
next' : SparseSet nfa.nodes.size
saveSlots' : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
h : exploreεClosure nfa pos next currentSave matched saveSlots target stack = (matched', next', saveSlots')
inv : LowerInvExploreεClosure nfa next target stack
j : Fin nfa.nodes.size
hj : j ∈ next ∨ ↑j ∈ nfa.εClosure ↑target
⊢ j ∈ next'

State before:
nfa : NFA
pos : String.Pos
next : SparseSet nfa.nodes.size
currentSave : Array (Option String.Pos)
matched : Option (Array (Option String.Pos))
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin nfa.nodes.size
stack : Array (StackEntry nfa.nodes.size)
matched' : Option (Array (Option String.Pos))
next' : SparseSet nfa.nodes.size
saveSlots' : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
h : exploreεClosure nfa pos next currentSave matched saveSlots target stack = (matched', next', saveSlots')
inv : LowerInvExploreεClosure nfa next target stack
j : Fin nfa.nodes.size
hj : j ∈ next ∨ ↑j ∈ nfa.εClosure ↑target
⊢ j ∈ next'
Tactic:
cases hj with
| inl hnext => exact exploreεClosure_subset h j hnext
| inr hcls =>
  have inv' := lower_inv_exploreεClosure h inv
  have ⟨_, hmem⟩ := εClosure_subset_lower_inv inv' target (target_mem_exploreεClosure h) j hcls
  exact hmem
State after:
no goals

State before:
case inl
nfa : NFA
pos : String.Pos
next : SparseSet nfa.nodes.size
currentSave : Array (Option String.Pos)
matched : Option (Array (Option String.Pos))
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin nfa.nodes.size
stack : Array (StackEntry nfa.nodes.size)
matched' : Option (Array (Option String.Pos))
next' : SparseSet nfa.nodes.size
saveSlots' : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
h : exploreεClosure nfa pos next currentSave matched saveSlots target stack = (matched', next', saveSlots')
inv : LowerInvExploreεClosure nfa next target stack
j : Fin nfa.nodes.size
hnext : j ∈ next
⊢ j ∈ next'
Tactic:
exact exploreεClosure_subset h j hnext
State after:
no goals

State before:
case inr
nfa : NFA
pos : String.Pos
next : SparseSet nfa.nodes.size
currentSave : Array (Option String.Pos)
matched : Option (Array (Option String.Pos))
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin nfa.nodes.size
stack : Array (StackEntry nfa.nodes.size)
matched' : Option (Array (Option String.Pos))
next' : SparseSet nfa.nodes.size
saveSlots' : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
h : exploreεClosure nfa pos next currentSave matched saveSlots target stack = (matched', next', saveSlots')
inv : LowerInvExploreεClosure nfa next target stack
j : Fin nfa.nodes.size
hcls : ↑j ∈ nfa.εClosure ↑target
⊢ j ∈ next'
Tactic:
have inv' := lower_inv_exploreεClosure h inv
State after:
case inr
nfa : NFA
pos : String.Pos
next : SparseSet nfa.nodes.size
currentSave : Array (Option String.Pos)
matched : Option (Array (Option String.Pos))
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin nfa.nodes.size
stack : Array (StackEntry nfa.nodes.size)
matched' : Option (Array (Option String.Pos))
next' : SparseSet nfa.nodes.size
saveSlots' : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
h : exploreεClosure nfa pos next currentSave matched saveSlots target stack = (matched', next', saveSlots')
inv : LowerInvExploreεClosure nfa next target stack
j : Fin nfa.nodes.size
hcls : ↑j ∈ nfa.εClosure ↑target
inv' : LowerInvεClosure nfa next' #[]
⊢ j ∈ next'

State before:
case inr
nfa : NFA
pos : String.Pos
next : SparseSet nfa.nodes.size
currentSave : Array (Option String.Pos)
matched : Option (Array (Option String.Pos))
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin nfa.nodes.size
stack : Array (StackEntry nfa.nodes.size)
matched' : Option (Array (Option String.Pos))
next' : SparseSet nfa.nodes.size
saveSlots' : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
h : exploreεClosure nfa pos next currentSave matched saveSlots target stack = (matched', next', saveSlots')
inv : LowerInvExploreεClosure nfa next target stack
j : Fin nfa.nodes.size
hcls : ↑j ∈ nfa.εClosure ↑target
inv' : LowerInvεClosure nfa next' #[]
⊢ j ∈ next'
Tactic:
have ⟨_, hmem⟩ := εClosure_subset_lower_inv inv' target (target_mem_exploreεClosure h) j hcls
State after:
case inr
nfa : NFA
pos : String.Pos
next : SparseSet nfa.nodes.size
currentSave : Array (Option String.Pos)
matched : Option (Array (Option String.Pos))
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin nfa.nodes.size
stack : Array (StackEntry nfa.nodes.size)
matched' : Option (Array (Option String.Pos))
next' : SparseSet nfa.nodes.size
saveSlots' : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
h : exploreεClosure nfa pos next currentSave matched saveSlots target stack = (matched', next', saveSlots')
inv : LowerInvExploreεClosure nfa next target stack
j : Fin nfa.nodes.size
hcls : ↑j ∈ nfa.εClosure ↑target
inv' : LowerInvεClosure nfa next' #[]
w✝ : ↑j < nfa.nodes.size
hmem : ⟨↑j, w✝⟩ ∈ next'
⊢ j ∈ next'

State before:
case inr
nfa : NFA
pos : String.Pos
next : SparseSet nfa.nodes.size
currentSave : Array (Option String.Pos)
matched : Option (Array (Option String.Pos))
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin nfa.nodes.size
stack : Array (StackEntry nfa.nodes.size)
matched' : Option (Array (Option String.Pos))
next' : SparseSet nfa.nodes.size
saveSlots' : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
h : exploreεClosure nfa pos next currentSave matched saveSlots target stack = (matched', next', saveSlots')
inv : LowerInvExploreεClosure nfa next target stack
j : Fin nfa.nodes.size
hcls : ↑j ∈ nfa.εClosure ↑target
inv' : LowerInvεClosure nfa next' #[]
w✝ : ↑j < nfa.nodes.size
hmem : ⟨↑j, w✝⟩ ∈ next'
⊢ j ∈ next'
Tactic:
exact hmem
State after:
no goals