internlm/Lean-Github huggingface dataset:
Theorem: DFA.fromNFA_run_imp_run
Proof state before:
case right
α qs : Type
inst✝³ : DecidableEq α
inst✝² : DecidableEq qs
inst✝¹ : DecidableEq α
inst✝ : DecidableEq qs
M : NFA α qs
w : Word { x // x ∈ (toNFA (fromNFA M)).Z }
q₀ : { x // x ∈ (fromNFA M).Q }
r : Run (fromNFA M) q₀ w
h✝ : w = ε
h : q₀ ∈ Finset.filter (fun s => ∃ q ∈ ↑s, q ∈ M.F) (Finset.attach Finset.univ)
left✝¹ : q₀ ∈ Finset.attach Finset.univ
qf : { x // x ∈ M.Q }
left✝ : qf ∈ ↑q₀
right✝ : qf ∈ M.F
⊢ ∃ r', NFA.Run.last r' ∈ M.F
Tactic:
apply Exists.intro
Proof state after:
case right.h
α qs : Type
inst✝³ : DecidableEq α
inst✝² : DecidableEq qs
inst✝¹ : DecidableEq α
inst✝ : DecidableEq qs
M : NFA α qs
w : Word { x // x ∈ (toNFA (fromNFA M)).Z }
q₀ : { x // x ∈ (fromNFA M).Q }
r : Run (fromNFA M) q₀ w
h✝ : w = ε
h : q₀ ∈ Finset.filter (fun s => ∃ q ∈ ↑s, q ∈ M.F) (Finset.attach Finset.univ)
left✝¹ : q₀ ∈ Finset.attach Finset.univ
qf : { x // x ∈ M.Q }
left✝ : qf ∈ ↑q₀
right✝ : qf ∈ M.F
⊢ NFA.Run.last ?right.w ∈ M.F

case right.w
α qs : Type
inst✝³ : DecidableEq α
inst✝² : DecidableEq qs
inst✝¹ : DecidableEq α
inst✝ : DecidableEq qs
M : NFA α qs
w : Word { x // x ∈ (toNFA (fromNFA M)).Z }
q₀ : { x // x ∈ (fromNFA M).Q }
r : Run (fromNFA M) q₀ w
h✝ : w = ε
h : q₀ ∈ Finset.filter (fun s => ∃ q ∈ ↑s, q ∈ M.F) (Finset.attach Finset.univ)
left✝¹ : q₀ ∈ Finset.attach Finset.univ
qf : { x // x ∈ M.Q }
left✝ : qf ∈ ↑q₀
right✝ : qf ∈ M.F
⊢ NFA.Run M qf w
Theorem: DFA.fromNFA_run_imp_run
Proof state before:
case right.h
α qs : Type
inst✝³ : DecidableEq α
inst✝² : DecidableEq qs
inst✝¹ : DecidableEq α
inst✝ : DecidableEq qs
M : NFA α qs
w : Word { x // x ∈ (toNFA (fromNFA M)).Z }
q₀ : { x // x ∈ (fromNFA M).Q }
r : Run (fromNFA M) q₀ w
h✝ : w = ε
h : q₀ ∈ Finset.filter (fun s => ∃ q ∈ ↑s, q ∈ M.F) (Finset.attach Finset.univ)
left✝¹ : q₀ ∈ Finset.attach Finset.univ
qf : { x // x ∈ M.Q }
left✝ : qf ∈ ↑q₀
right✝ : qf ∈ M.F
⊢ NFA.Run.last ?right.w ∈ M.F

case right.w
α qs : Type
inst✝³ : DecidableEq α
inst✝² : DecidableEq qs
inst✝¹ : DecidableEq α
inst✝ : DecidableEq qs
M : NFA α qs
w : Word { x // x ∈ (toNFA (fromNFA M)).Z }
q₀ : { x // x ∈ (fromNFA M).Q }
r : Run (fromNFA M) q₀ w
h✝ : w = ε
h : q₀ ∈ Finset.filter (fun s => ∃ q ∈ ↑s, q ∈ M.F) (Finset.attach Finset.univ)
left✝¹ : q₀ ∈ Finset.attach Finset.univ
qf : { x // x ∈ M.Q }
left✝ : qf ∈ ↑q₀
right✝ : qf ∈ M.F
⊢ NFA.Run M qf w
Tactic:
swap
Proof state after:
case right.w
α qs : Type
inst✝³ : DecidableEq α
inst✝² : DecidableEq qs
inst✝¹ : DecidableEq α
inst✝ : DecidableEq qs
M : NFA α qs
w : Word { x // x ∈ (toNFA (fromNFA M)).Z }
q₀ : { x // x ∈ (fromNFA M).Q }
r : Run (fromNFA M) q₀ w
h✝ : w = ε
h : q₀ ∈ Finset.filter (fun s => ∃ q ∈ ↑s, q ∈ M.F) (Finset.attach Finset.univ)
left✝¹ : q₀ ∈ Finset.attach Finset.univ
qf : { x // x ∈ M.Q }
left✝ : qf ∈ ↑q₀
right✝ : qf ∈ M.F
⊢ NFA.Run M qf w

case right.h
α qs : Type
inst✝³ : DecidableEq α
inst✝² : DecidableEq qs
inst✝¹ : DecidableEq α
inst✝ : DecidableEq qs
M : NFA α qs
w : Word { x // x ∈ (toNFA (fromNFA M)).Z }
q₀ : { x // x ∈ (fromNFA M).Q }
r : Run (fromNFA M) q₀ w
h✝ : w = ε
h : q₀ ∈ Finset.filter (fun s => ∃ q ∈ ↑s, q ∈ M.F) (Finset.attach Finset.univ)
left✝¹ : q₀ ∈ Finset.attach Finset.univ
qf : { x // x ∈ M.Q }
left✝ : qf ∈ ↑q₀
right✝ : qf ∈ M.F
⊢ NFA.Run.last ?right.w ∈ M.F
Theorem: DFA.fromNFA_run_imp_run
Proof state before:
case right.w
α qs : Type
inst✝³ : DecidableEq α
inst✝² : DecidableEq qs
inst✝¹ : DecidableEq α
inst✝ : DecidableEq qs
M : NFA α qs
w : Word { x // x ∈ (toNFA (fromNFA M)).Z }
q₀ : { x // x ∈ (fromNFA M).Q }
r : Run (fromNFA M) q₀ w
h✝ : w = ε
h : q₀ ∈ Finset.filter (fun s => ∃ q ∈ ↑s, q ∈ M.F) (Finset.attach Finset.univ)
left✝¹ : q₀ ∈ Finset.attach Finset.univ
qf : { x // x ∈ M.Q }
left✝ : qf ∈ ↑q₀
right✝ : qf ∈ M.F
⊢ NFA.Run M qf w

case right.h
α qs : Type
inst✝³ : DecidableEq α
inst✝² : DecidableEq qs
inst✝¹ : DecidableEq α
inst✝ : DecidableEq qs
M : NFA α qs
w : Word { x // x ∈ (toNFA (fromNFA M)).Z }
q₀ : { x // x ∈ (fromNFA M).Q }
r : Run (fromNFA M) q₀ w
h✝ : w = ε
h : q₀ ∈ Finset.filter (fun s => ∃ q ∈ ↑s, q ∈ M.F) (Finset.attach Finset.univ)
left✝¹ : q₀ ∈ Finset.attach Finset.univ
qf : { x // x ∈ M.Q }
left✝ : qf ∈ ↑q₀
right✝ : qf ∈ M.F
⊢ NFA.Run.last ?right.w ∈ M.F
Tactic:
apply NFA.Run.final _
Proof state after:
case right.w
α qs : Type
inst✝³ : DecidableEq α
inst✝² : DecidableEq qs
inst✝¹ : DecidableEq α
inst✝ : DecidableEq qs
M : NFA α qs
w : Word { x // x ∈ (toNFA (fromNFA M)).Z }
q₀ : { x // x ∈ (fromNFA M).Q }
r : Run (fromNFA M) q₀ w
h✝ : w = ε
h : q₀ ∈ Finset.filter (fun s => ∃ q ∈ ↑s, q ∈ M.F) (Finset.attach Finset.univ)
left✝¹ : q₀ ∈ Finset.attach Finset.univ
qf : { x // x ∈ M.Q }
left✝ : qf ∈ ↑q₀
right✝ : qf ∈ M.F
⊢ w = ε

case right.h
α qs : Type
inst✝³ : DecidableEq α
inst✝² : DecidableEq qs
inst✝¹ : DecidableEq α
inst✝ : DecidableEq qs
M : NFA α qs
w : Word { x // x ∈ (toNFA (fromNFA M)).Z }
q₀ : { x // x ∈ (fromNFA M).Q }
r : Run (fromNFA M) q₀ w
h✝ : w = ε
h : q₀ ∈ Finset.filter (fun s => ∃ q ∈ ↑s, q ∈ M.F) (Finset.attach Finset.univ)
left✝¹ : q₀ ∈ Finset.attach Finset.univ
qf : { x // x ∈ M.Q }
left✝ : qf ∈ ↑q₀
right✝ : qf ∈ M.F
⊢ NFA.Run.last (NFA.Run.final qf ?right.w) ∈ M.F
Theorem: DFA.fromNFA_run_imp_run
Proof state before:
case right.w
α qs : Type
inst✝³ : DecidableEq α
inst✝² : DecidableEq qs
inst✝¹ : DecidableEq α
inst✝ : DecidableEq qs
M : NFA α qs
w : Word { x // x ∈ (toNFA (fromNFA M)).Z }
q₀ : { x // x ∈ (fromNFA M).Q }
r : Run (fromNFA M) q₀ w
h✝ : w = ε
h : q₀ ∈ Finset.filter (fun s => ∃ q ∈ ↑s, q ∈ M.F) (Finset.attach Finset.univ)
left✝¹ : q₀ ∈ Finset.attach Finset.univ
qf : { x // x ∈ M.Q }
left✝ : qf ∈ ↑q₀
right✝ : qf ∈ M.F
⊢ w = ε

case right.h
α qs : Type
inst✝³ : DecidableEq α
inst✝² : DecidableEq qs
inst✝¹ : DecidableEq α
inst✝ : DecidableEq qs
M : NFA α qs
w : Word { x // x ∈ (toNFA (fromNFA M)).Z }
q₀ : { x // x ∈ (fromNFA M).Q }
r : Run (fromNFA M) q₀ w
h✝ : w = ε
h : q₀ ∈ Finset.filter (fun s => ∃ q ∈ ↑s, q ∈ M.F) (Finset.attach Finset.univ)
left✝¹ : q₀ ∈ Finset.attach Finset.univ
qf : { x // x ∈ M.Q }
left✝ : qf ∈ ↑q₀
right✝ : qf ∈ M.F
⊢ NFA.Run.last (NFA.Run.final qf ?right.w) ∈ M.F
Tactic:
assumption
Proof state after:
case right.h
α qs : Type
inst✝³ : DecidableEq α
inst✝² : DecidableEq qs
inst✝¹ : DecidableEq α
inst✝ : DecidableEq qs
M : NFA α qs
w : Word { x // x ∈ (toNFA (fromNFA M)).Z }
q₀ : { x // x ∈ (fromNFA M).Q }
r : Run (fromNFA M) q₀ w
h✝ : w = ε
h : q₀ ∈ Finset.filter (fun s => ∃ q ∈ ↑s, q ∈ M.F) (Finset.attach Finset.univ)
left✝¹ : q₀ ∈ Finset.attach Finset.univ
qf : { x // x ∈ M.Q }
left✝ : qf ∈ ↑q₀
right✝ : qf ∈ M.F
⊢ NFA.Run.last (NFA.Run.final qf h✝) ∈ M.F
Theorem: DFA.fromNFA_run_imp_run
Proof state before:
case right.h
α qs : Type
inst✝³ : DecidableEq α
inst✝² : DecidableEq qs
inst✝¹ : DecidableEq α
inst✝ : DecidableEq qs
M : NFA α qs
w : Word { x // x ∈ (toNFA (fromNFA M)).Z }
q₀ : { x // x ∈ (fromNFA M).Q }
r : Run (fromNFA M) q₀ w
h✝ : w = ε
h : q₀ ∈ Finset.filter (fun s => ∃ q ∈ ↑s, q ∈ M.F) (Finset.attach Finset.univ)
left✝¹ : q₀ ∈ Finset.attach Finset.univ
qf : { x // x ∈ M.Q }
left✝ : qf ∈ ↑q₀
right✝ : qf ∈ M.F
⊢ NFA.Run.last (NFA.Run.final qf h✝) ∈ M.F
Tactic:
dsimp [NFA.Run.last]
Proof state after:
case right.h
α qs : Type
inst✝³ : DecidableEq α
inst✝² : DecidableEq qs
inst✝¹ : DecidableEq α
inst✝ : DecidableEq qs
M : NFA α qs
w : Word { x // x ∈ (toNFA (fromNFA M)).Z }
q₀ : { x // x ∈ (fromNFA M).Q }
r : Run (fromNFA M) q₀ w
h✝ : w = ε
h : q₀ ∈ Finset.filter (fun s => ∃ q ∈ ↑s, q ∈ M.F) (Finset.attach Finset.univ)
left✝¹ : q₀ ∈ Finset.attach Finset.univ
qf : { x // x ∈ M.Q }
left✝ : qf ∈ ↑q₀
right✝ : qf ∈ M.F
⊢ qf ∈ M.F
Theorem: DFA.fromNFA_run_imp_run
Proof state before:
case right.h
α qs : Type
inst✝³ : DecidableEq α
inst✝² : DecidableEq qs
inst✝¹ : DecidableEq α
inst✝ : DecidableEq qs
M : NFA α qs
w : Word { x // x ∈ (toNFA (fromNFA M)).Z }
q₀ : { x // x ∈ (fromNFA M).Q }
r : Run (fromNFA M) q₀ w
h✝ : w = ε
h : q₀ ∈ Finset.filter (fun s => ∃ q ∈ ↑s, q ∈ M.F) (Finset.attach Finset.univ)
left✝¹ : q₀ ∈ Finset.attach Finset.univ
qf : { x // x ∈ M.Q }
left✝ : qf ∈ ↑q₀
right✝ : qf ∈ M.F
⊢ qf ∈ M.F
Tactic:
assumption
Proof state after:
no goals
Theorem: DFA.fromNFA_run_imp_run
Proof state before:
α qs : Type
inst✝³ : DecidableEq α
inst✝² : DecidableEq qs
inst✝¹ : DecidableEq α
inst✝ : DecidableEq qs
M : NFA α qs
w : Word { x // x ∈ (toNFA (fromNFA M)).Z }
q₀ : { x // x ∈ (fromNFA M).Q }
r : Run (fromNFA M) q₀ w
q₂✝ : { x // x ∈ (toNFA (fromNFA M)).Q }
a✝ : { x // x ∈ (toNFA (fromNFA M)).Z }
w✝ : Word { x // x ∈ (toNFA (fromNFA M)).Z }
h_step : q₂✝ ∈ (toNFA (fromNFA M)).δ (q₀, a✝)
r✝ : NFA.Run (toNFA (fromNFA M)) q₂✝ w✝
h✝ : w = a✝ :: w✝
h : NFA.Run.last (NFA.Run.step q₀ h_step r✝ h✝) ∈ (fromNFA M).F
⊢ ∃ q ∈ ↑q₀, ∃ r', NFA.Run.last r' ∈ M.F
Tactic:
dsimp [NFA.Run.last] at h
Proof state after:
α qs : Type
inst✝³ : DecidableEq α
inst✝² : DecidableEq qs
inst✝¹ : DecidableEq α
inst✝ : DecidableEq qs
M : NFA α qs
w : Word { x // x ∈ (toNFA (fromNFA M)).Z }
q₀ : { x // x ∈ (fromNFA M).Q }
r : Run (fromNFA M) q₀ w
q₂✝ : { x // x ∈ (toNFA (fromNFA M)).Q }
a✝ : { x // x ∈ (toNFA (fromNFA M)).Z }
w✝ : Word { x // x ∈ (toNFA (fromNFA M)).Z }
h_step : q₂✝ ∈ (toNFA (fromNFA M)).δ (q₀, a✝)
r✝ : NFA.Run (toNFA (fromNFA M)) q₂✝ w✝
h✝ : w = a✝ :: w✝
h : NFA.Run.last r✝ ∈ (fromNFA M).F
⊢ ∃ q ∈ ↑q₀, ∃ r', NFA.Run.last r' ∈ M.F
Theorem: DFA.fromNFA_run_imp_run
Proof state before:
α qs : Type
inst✝³ : DecidableEq α
inst✝² : DecidableEq qs
inst✝¹ : DecidableEq α
inst✝ : DecidableEq qs
M : NFA α qs
w : Word { x // x ∈ (toNFA (fromNFA M)).Z }
q₀ : { x // x ∈ (fromNFA M).Q }
r : Run (fromNFA M) q₀ w
q₂✝ : { x // x ∈ (toNFA (fromNFA M)).Q }
a✝ : { x // x ∈ (toNFA (fromNFA M)).Z }
w✝ : Word { x // x ∈ (toNFA (fromNFA M)).Z }
h_step : q₂✝ ∈ (toNFA (fromNFA M)).δ (q₀, a✝)
r✝ : NFA.Run (toNFA (fromNFA M)) q₂✝ w✝
h✝ : w = a✝ :: w✝
h : NFA.Run.last r✝ ∈ (fromNFA M).F
⊢ ∃ q ∈ ↑q₀, ∃ r', NFA.Run.last r' ∈ M.F
Tactic:
dsimp [fromNFA, toNFA] at h_step
Proof state after:
α qs : Type
inst✝³ : DecidableEq α
inst✝² : DecidableEq qs
inst✝¹ : DecidableEq α
inst✝ : DecidableEq qs
M : NFA α qs
w : Word { x // x ∈ (toNFA (fromNFA M)).Z }
q₀ : { x // x ∈ (fromNFA M).Q }
r : Run (fromNFA M) q₀ w
q₂✝ : { x // x ∈ (toNFA (fromNFA M)).Q }
a✝ : { x // x ∈ (toNFA (fromNFA M)).Z }
w✝ : Word { x // x ∈ (toNFA (fromNFA M)).Z }
h_step : q₂✝ ∈ {{ val := Finset.fold (fun x x_1 => x ∪ x_1) ∅ (fun q => M.δ (q, a✝)) ↑q₀, property := ⋯ }}
r✝ : NFA.Run (toNFA (fromNFA M)) q₂✝ w✝
h✝ : w = a✝ :: w✝
h : NFA.Run.last r✝ ∈ (fromNFA M).F
⊢ ∃ q ∈ ↑q₀, ∃ r', NFA.Run.last r' ∈ M.F
Theorem: DFA.fromNFA_run_imp_run
Proof state before:
α qs : Type
inst✝³ : DecidableEq α
inst✝² : DecidableEq qs
inst✝¹ : DecidableEq α
inst✝ : DecidableEq qs
M : NFA α qs
w : Word { x // x ∈ (toNFA (fromNFA M)).Z }
q₀ : { x // x ∈ (fromNFA M).Q }
r : Run (fromNFA M) q₀ w
q₂✝ : { x // x ∈ (toNFA (fromNFA M)).Q }
a✝ : { x // x ∈ (toNFA (fromNFA M)).Z }
w✝ : Word { x // x ∈ (toNFA (fromNFA M)).Z }
h_step : q₂✝ ∈ {{ val := Finset.fold (fun x x_1 => x ∪ x_1) ∅ (fun q => M.δ (q, a✝)) ↑q₀, property := ⋯ }}
r✝ : NFA.Run (toNFA (fromNFA M)) q₂✝ w✝
h✝ : w = a✝ :: w✝
h : NFA.Run.last r✝ ∈ (fromNFA M).F
⊢ ∃ q ∈ ↑q₀, ∃ r', NFA.Run.last r' ∈ M.F
Tactic:
simp at h_step
Proof state after:
α qs : Type
inst✝³ : DecidableEq α
inst✝² : DecidableEq qs
inst✝¹ : DecidableEq α
inst✝ : DecidableEq qs
M : NFA α qs
w : Word { x // x ∈ (toNFA (fromNFA M)).Z }
q₀ : { x // x ∈ (fromNFA M).Q }
r : Run (fromNFA M) q₀ w
q₂✝ : { x // x ∈ (toNFA (fromNFA M)).Q }
a✝ : { x // x ∈ (toNFA (fromNFA M)).Z }
w✝ : Word { x // x ∈ (toNFA (fromNFA M)).Z }
r✝ : NFA.Run (toNFA (fromNFA M)) q₂✝ w✝
h✝ : w = a✝ :: w✝
h : NFA.Run.last r✝ ∈ (fromNFA M).F
h_step : q₂✝ = { val := Finset.fold (fun x x_1 => x ∪ x_1) ∅ (fun q => M.δ (q, a✝)) ↑q₀, property := ⋯ }
⊢ ∃ q ∈ ↑q₀, ∃ r', NFA.Run.last r' ∈ M.F
Theorem: DFA.fromNFA_run_imp_run
Proof state before:
α qs : Type
inst✝³ : DecidableEq α
inst✝² : DecidableEq qs
inst✝¹ : DecidableEq α
inst✝ : DecidableEq qs
M : NFA α qs
w : Word { x // x ∈ (toNFA (fromNFA M)).Z }
q₀ : { x // x ∈ (fromNFA M).Q }
r : Run (fromNFA M) q₀ w
q₂✝ : { x // x ∈ (toNFA (fromNFA M)).Q }
a✝ : { x // x ∈ (toNFA (fromNFA M)).Z }
w✝ : Word { x // x ∈ (toNFA (fromNFA M)).Z }
r✝ : NFA.Run (toNFA (fromNFA M)) q₂✝ w✝
h✝ : w = a✝ :: w✝
h : NFA.Run.last r✝ ∈ (fromNFA M).F
h_step : q₂✝ = { val := Finset.fold (fun x x_1 => x ∪ x_1) ∅ (fun q => M.δ (q, a✝)) ↑q₀, property := ⋯ }
⊢ ∃ q ∈ ↑q₀, ∃ r', NFA.Run.last r' ∈ M.F
Tactic:
have ⟨_, h_q₂, r', hr'⟩ := fromNFA_run_imp_run h
Proof state after:
α qs : Type
inst✝³ : DecidableEq α
inst✝² : DecidableEq qs
inst✝¹ : DecidableEq α
inst✝ : DecidableEq qs
M : NFA α qs
w : Word { x // x ∈ (toNFA (fromNFA M)).Z }
q₀ : { x // x ∈ (fromNFA M).Q }
r : Run (fromNFA M) q₀ w
q₂✝ : { x // x ∈ (toNFA (fromNFA M)).Q }
a✝ : { x // x ∈ (toNFA (fromNFA M)).Z }
w✝¹ : Word { x // x ∈ (toNFA (fromNFA M)).Z }
r✝ : NFA.Run (toNFA (fromNFA M)) q₂✝ w✝¹
h✝ : w = a✝ :: w✝¹
h : NFA.Run.last r✝ ∈ (fromNFA M).F
h_step : q₂✝ = { val := Finset.fold (fun x x_1 => x ∪ x_1) ∅ (fun q => M.δ (q, a✝)) ↑q₀, property := ⋯ }
w✝ : { x // x ∈ M.Q }
h_q₂ : w✝ ∈ ↑q₂✝
r' : NFA.Run M w✝ w✝¹
hr' : NFA.Run.last r' ∈ M.F
⊢ ∃ q ∈ ↑q₀, ∃ r', NFA.Run.last r' ∈ M.F
Theorem: DFA.fromNFA_run_imp_run
Proof state before:
α qs : Type
inst✝³ : DecidableEq α
inst✝² : DecidableEq qs
inst✝¹ : DecidableEq α
inst✝ : DecidableEq qs
M : NFA α qs
w : Word { x // x ∈ (toNFA (fromNFA M)).Z }
q₀ : { x // x ∈ (fromNFA M).Q }
r : Run (fromNFA M) q₀ w
q₂✝ : { x // x ∈ (toNFA (fromNFA M)).Q }
a✝ : { x // x ∈ (toNFA (fromNFA M)).Z }
w✝¹ : Word { x // x ∈ (toNFA (fromNFA M)).Z }
r✝ : NFA.Run (toNFA (fromNFA M)) q₂✝ w✝¹
h✝ : w = a✝ :: w✝¹
h : NFA.Run.last r✝ ∈ (fromNFA M).F
h_step : q₂✝ = { val := Finset.fold (fun x x_1 => x ∪ x_1) ∅ (fun q => M.δ (q, a✝)) ↑q₀, property := ⋯ }
w✝ : { x // x ∈ M.Q }
h_q₂ : w✝ ∈ ↑q₂✝
r' : NFA.Run M w✝ w✝¹
hr' : NFA.Run.last r' ∈ M.F
⊢ ∃ q ∈ ↑q₀, ∃ r', NFA.Run.last r' ∈ M.F
Tactic:
rw [h_step, Finset.mem_fold_union_iff] at h_q₂
Proof state after:
α qs : Type
inst✝³ : DecidableEq α
inst✝² : DecidableEq qs
inst✝¹ : DecidableEq α
inst✝ : DecidableEq qs
M : NFA α qs
w : Word { x // x ∈ (toNFA (fromNFA M)).Z }
q₀ : { x // x ∈ (fromNFA M).Q }
r : Run (fromNFA M) q₀ w
q₂✝ : { x // x ∈ (toNFA (fromNFA M)).Q }
a✝ : { x // x ∈ (toNFA (fromNFA M)).Z }
w✝¹ : Word { x // x ∈ (toNFA (fromNFA M)).Z }
r✝ : NFA.Run (toNFA (fromNFA M)) q₂✝ w✝¹
h✝ : w = a✝ :: w✝¹
h : NFA.Run.last r✝ ∈ (fromNFA M).F
h_step : q₂✝ = { val := Finset.fold (fun x x_1 => x ∪ x_1) ∅ (fun q => M.δ (q, a✝)) ↑q₀, property := ⋯ }
w✝ : { x // x ∈ M.Q }
h_q₂ : ∃ x ∈ ↑q₀, w✝ ∈ M.δ (x, a✝)
r' : NFA.Run M w✝ w✝¹
hr' : NFA.Run.last r' ∈ M.F
⊢ ∃ q ∈ ↑q₀, ∃ r', NFA.Run.last r' ∈ M.F
Theorem: DFA.fromNFA_run_imp_run
Proof state before:
α qs : Type
inst✝³ : DecidableEq α
inst✝² : DecidableEq qs
inst✝¹ : DecidableEq α
inst✝ : DecidableEq qs
M : NFA α qs
w : Word { x // x ∈ (toNFA (fromNFA M)).Z }
q₀ : { x // x ∈ (fromNFA M).Q }
r : Run (fromNFA M) q₀ w
q₂✝ : { x // x ∈ (toNFA (fromNFA M)).Q }
a✝ : { x // x ∈ (toNFA (fromNFA M)).Z }
w✝¹ : Word { x // x ∈ (toNFA (fromNFA M)).Z }
r✝ : NFA.Run (toNFA (fromNFA M)) q₂✝ w✝¹
h✝ : w = a✝ :: w✝¹
h : NFA.Run.last r✝ ∈ (fromNFA M).F
h_step : q₂✝ = { val := Finset.fold (fun x x_1 => x ∪ x_1) ∅ (fun q => M.δ (q, a✝)) ↑q₀, property := ⋯ }
w✝ : { x // x ∈ M.Q }
h_q₂ : ∃ x ∈ ↑q₀, w✝ ∈ M.δ (x, a✝)
r' : NFA.Run M w✝ w✝¹
hr' : NFA.Run.last r' ∈ M.F
⊢ ∃ q ∈ ↑q₀, ∃ r', NFA.Run.last r' ∈ M.F
Tactic:
have ⟨x, _, _⟩ := h_q₂
Proof state after:
α qs : Type
inst✝³ : DecidableEq α
inst✝² : DecidableEq qs
inst✝¹ : DecidableEq α
inst✝ : DecidableEq qs
M : NFA α qs
w : Word { x // x ∈ (toNFA (fromNFA M)).Z }
q₀ : { x // x ∈ (fromNFA M).Q }
r : Run (fromNFA M) q₀ w
q₂✝ : { x // x ∈ (toNFA (fromNFA M)).Q }
a✝ : { x // x ∈ (toNFA (fromNFA M)).Z }
w✝¹ : Word { x // x ∈ (toNFA (fromNFA M)).Z }
r✝ : NFA.Run (toNFA (fromNFA M)) q₂✝ w✝¹
h✝ : w = a✝ :: w✝¹
h : NFA.Run.last r✝ ∈ (fromNFA M).F
h_step : q₂✝ = { val := Finset.fold (fun x x_1 => x ∪ x_1) ∅ (fun q => M.δ (q, a✝)) ↑q₀, property := ⋯ }
w✝ : { x // x ∈ M.Q }
h_q₂ : ∃ x ∈ ↑q₀, w✝ ∈ M.δ (x, a✝)
r' : NFA.Run M w✝ w✝¹
hr' : NFA.Run.last r' ∈ M.F
x : { x // x ∈ M.Q }
left✝ : x ∈ ↑q₀
right✝ : w✝ ∈ M.δ (x, a✝)
⊢ ∃ q ∈ ↑q₀, ∃ r', NFA.Run.last r' ∈ M.F
Theorem: DFA.fromNFA_run_imp_run
Proof state before:
α qs : Type
inst✝³ : DecidableEq α
inst✝² : DecidableEq qs
inst✝¹ : DecidableEq α
inst✝ : DecidableEq qs
M : NFA α qs
w : Word { x // x ∈ (toNFA (fromNFA M)).Z }
q₀ : { x // x ∈ (fromNFA M).Q }
r : Run (fromNFA M) q₀ w
q₂✝ : { x // x ∈ (toNFA (fromNFA M)).Q }
a✝ : { x // x ∈ (toNFA (fromNFA M)).Z }
w✝¹ : Word { x // x ∈ (toNFA (fromNFA M)).Z }
r✝ : NFA.Run (toNFA (fromNFA M)) q₂✝ w✝¹
h✝ : w = a✝ :: w✝¹
h : NFA.Run.last r✝ ∈ (fromNFA M).F
h_step : q₂✝ = { val := Finset.fold (fun x x_1 => x ∪ x_1) ∅ (fun q => M.δ (q, a✝)) ↑q₀, property := ⋯ }
w✝ : { x // x ∈ M.Q }
h_q₂ : ∃ x ∈ ↑q₀, w✝ ∈ M.δ (x, a✝)
r' : NFA.Run M w✝ w✝¹
hr' : NFA.Run.last r' ∈ M.F
x : { x // x ∈ M.Q }
left✝ : x ∈ ↑q₀
right✝ : w✝ ∈ M.δ (x, a✝)
⊢ ∃ q ∈ ↑q₀, ∃ r', NFA.Run.last r' ∈ M.F
Tactic:
exists x
Proof state after:
α qs : Type
inst✝³ : DecidableEq α
inst✝² : DecidableEq qs
inst✝¹ : DecidableEq α
inst✝ : DecidableEq qs
M : NFA α qs
w : Word { x // x ∈ (toNFA (fromNFA M)).Z }
q₀ : { x // x ∈ (fromNFA M).Q }
r : Run (fromNFA M) q₀ w
q₂✝ : { x // x ∈ (toNFA (fromNFA M)).Q }
a✝ : { x // x ∈ (toNFA (fromNFA M)).Z }
w✝¹ : Word { x // x ∈ (toNFA (fromNFA M)).Z }
r✝ : NFA.Run (toNFA (fromNFA M)) q₂✝ w✝¹
h✝ : w = a✝ :: w✝¹
h : NFA.Run.last r✝ ∈ (fromNFA M).F
h_step : q₂✝ = { val := Finset.fold (fun x x_1 => x ∪ x_1) ∅ (fun q => M.δ (q, a✝)) ↑q₀, property := ⋯ }
w✝ : { x // x ∈ M.Q }
h_q₂ : ∃ x ∈ ↑q₀, w✝ ∈ M.δ (x, a✝)
r' : NFA.Run M w✝ w✝¹
hr' : NFA.Run.last r' ∈ M.F
x : { x // x ∈ M.Q }
left✝ : x ∈ ↑q₀
right✝ : w✝ ∈ M.δ (x, a✝)
⊢ x ∈ ↑q₀ ∧ ∃ r', NFA.Run.last r' ∈ M.F
Theorem: DFA.fromNFA_run_imp_run
Proof state before:
α qs : Type
inst✝³ : DecidableEq α
inst✝² : DecidableEq qs
inst✝¹ : DecidableEq α
inst✝ : DecidableEq qs
M : NFA α qs
w : Word { x // x ∈ (toNFA (fromNFA M)).Z }
q₀ : { x // x ∈ (fromNFA M).Q }
r : Run (fromNFA M) q₀ w
q₂✝ : { x // x ∈ (toNFA (fromNFA M)).Q }
a✝ : { x // x ∈ (toNFA (fromNFA M)).Z }
w✝¹ : Word { x // x ∈ (toNFA (fromNFA M)).Z }
r✝ : NFA.Run (toNFA (fromNFA M)) q₂✝ w✝¹
h✝ : w = a✝ :: w✝¹
h : NFA.Run.last r✝ ∈ (fromNFA M).F
h_step : q₂✝ = { val := Finset.fold (fun x x_1 => x ∪ x_1) ∅ (fun q => M.δ (q, a✝)) ↑q₀, property := ⋯ }
w✝ : { x // x ∈ M.Q }
h_q₂ : ∃ x ∈ ↑q₀, w✝ ∈ M.δ (x, a✝)
r' : NFA.Run M w✝ w✝¹
hr' : NFA.Run.last r' ∈ M.F
x : { x // x ∈ M.Q }
left✝ : x ∈ ↑q₀
right✝ : w✝ ∈ M.δ (x, a✝)
⊢ x ∈ ↑q₀ ∧ ∃ r', NFA.Run.last r' ∈ M.F
Tactic:
constructor
Proof state after:
case left
α qs : Type
inst✝³ : DecidableEq α
inst✝² : DecidableEq qs
inst✝¹ : DecidableEq α
inst✝ : DecidableEq qs
M : NFA α qs
w : Word { x // x ∈ (toNFA (fromNFA M)).Z }
q₀ : { x // x ∈ (fromNFA M).Q }
r : Run (fromNFA M) q₀ w
q₂✝ : { x // x ∈ (toNFA (fromNFA M)).Q }
a✝ : { x // x ∈ (toNFA (fromNFA M)).Z }
w✝¹ : Word { x // x ∈ (toNFA (fromNFA M)).Z }
r✝ : NFA.Run (toNFA (fromNFA M)) q₂✝ w✝¹
h✝ : w = a✝ :: w✝¹
h : NFA.Run.last r✝ ∈ (fromNFA M).F
h_step : q₂✝ = { val := Finset.fold (fun x x_1 => x ∪ x_1) ∅ (fun q => M.δ (q, a✝)) ↑q₀, property := ⋯ }
w✝ : { x // x ∈ M.Q }
h_q₂ : ∃ x ∈ ↑q₀, w✝ ∈ M.δ (x, a✝)
r' : NFA.Run M w✝ w✝¹
hr' : NFA.Run.last r' ∈ M.F
x : { x // x ∈ M.Q }
left✝ : x ∈ ↑q₀
right✝ : w✝ ∈ M.δ (x, a✝)
⊢ x ∈ ↑q₀

case right
α qs : Type
inst✝³ : DecidableEq α
inst✝² : DecidableEq qs
inst✝¹ : DecidableEq α
inst✝ : DecidableEq qs
M : NFA α qs
w : Word { x // x ∈ (toNFA (fromNFA M)).Z }
q₀ : { x // x ∈ (fromNFA M).Q }
r : Run (fromNFA M) q₀ w
q₂✝ : { x // x ∈ (toNFA (fromNFA M)).Q }
a✝ : { x // x ∈ (toNFA (fromNFA M)).Z }
w✝¹ : Word { x // x ∈ (toNFA (fromNFA M)).Z }
r✝ : NFA.Run (toNFA (fromNFA M)) q₂✝ w✝¹
h✝ : w = a✝ :: w✝¹
h : NFA.Run.last r✝ ∈ (fromNFA M).F
h_step : q₂✝ = { val := Finset.fold (fun x x_1 => x ∪ x_1) ∅ (fun q => M.δ (q, a✝)) ↑q₀, property := ⋯ }
w✝ : { x // x ∈ M.Q }
h_q₂ : ∃ x ∈ ↑q₀, w✝ ∈ M.δ (x, a✝)
r' : NFA.Run M w✝ w✝¹
hr' : NFA.Run.last r' ∈ M.F
x : { x // x ∈ M.Q }
left✝ : x ∈ ↑q₀
right✝ : w✝ ∈ M.δ (x, a✝)
⊢ ∃ r', NFA.Run.last r' ∈ M.F
Theorem: DFA.fromNFA_run_imp_run
Proof state before:
case left
α qs : Type
inst✝³ : DecidableEq α
inst✝² : DecidableEq qs
inst✝¹ : DecidableEq α
inst✝ : DecidableEq qs
M : NFA α qs
w : Word { x // x ∈ (toNFA (fromNFA M)).Z }
q₀ : { x // x ∈ (fromNFA M).Q }
r : Run (fromNFA M) q₀ w
q₂✝ : { x // x ∈ (toNFA (fromNFA M)).Q }
a✝ : { x // x ∈ (toNFA (fromNFA M)).Z }
w✝¹ : Word { x // x ∈ (toNFA (fromNFA M)).Z }
r✝ : NFA.Run (toNFA (fromNFA M)) q₂✝ w✝¹
h✝ : w = a✝ :: w✝¹
h : NFA.Run.last r✝ ∈ (fromNFA M).F
h_step : q₂✝ = { val := Finset.fold (fun x x_1 => x ∪ x_1) ∅ (fun q => M.δ (q, a✝)) ↑q₀, property := ⋯ }
w✝ : { x // x ∈ M.Q }
h_q₂ : ∃ x ∈ ↑q₀, w✝ ∈ M.δ (x, a✝)
r' : NFA.Run M w✝ w✝¹
hr' : NFA.Run.last r' ∈ M.F
x : { x // x ∈ M.Q }
left✝ : x ∈ ↑q₀
right✝ : w✝ ∈ M.δ (x, a✝)
⊢ x ∈ ↑q₀

case right
α qs : Type
inst✝³ : DecidableEq α
inst✝² : DecidableEq qs
inst✝¹ : DecidableEq α
inst✝ : DecidableEq qs
M : NFA α qs
w : Word { x // x ∈ (toNFA (fromNFA M)).Z }
q₀ : { x // x ∈ (fromNFA M).Q }
r : Run (fromNFA M) q₀ w
q₂✝ : { x // x ∈ (toNFA (fromNFA M)).Q }
a✝ : { x // x ∈ (toNFA (fromNFA M)).Z }
w✝¹ : Word { x // x ∈ (toNFA (fromNFA M)).Z }
r✝ : NFA.Run (toNFA (fromNFA M)) q₂✝ w✝¹
h✝ : w = a✝ :: w✝¹
h : NFA.Run.last r✝ ∈ (fromNFA M).F
h_step : q₂✝ = { val := Finset.fold (fun x x_1 => x ∪ x_1) ∅ (fun q => M.δ (q, a✝)) ↑q₀, property := ⋯ }
w✝ : { x // x ∈ M.Q }
h_q₂ : ∃ x ∈ ↑q₀, w✝ ∈ M.δ (x, a✝)
r' : NFA.Run M w✝ w✝¹
hr' : NFA.Run.last r' ∈ M.F
x : { x // x ∈ M.Q }
left✝ : x ∈ ↑q₀
right✝ : w✝ ∈ M.δ (x, a✝)
⊢ ∃ r', NFA.Run.last r' ∈ M.F
Tactic:
assumption
Proof state after:
case right
α qs : Type
inst✝³ : DecidableEq α
inst✝² : DecidableEq qs
inst✝¹ : DecidableEq α
inst✝ : DecidableEq qs
M : NFA α qs
w : Word { x // x ∈ (toNFA (fromNFA M)).Z }
q₀ : { x // x ∈ (fromNFA M).Q }
r : Run (fromNFA M) q₀ w
q₂✝ : { x // x ∈ (toNFA (fromNFA M)).Q }
a✝ : { x // x ∈ (toNFA (fromNFA M)).Z }
w✝¹ : Word { x // x ∈ (toNFA (fromNFA M)).Z }
r✝ : NFA.Run (toNFA (fromNFA M)) q₂✝ w✝¹
h✝ : w = a✝ :: w✝¹
h : NFA.Run.last r✝ ∈ (fromNFA M).F
h_step : q₂✝ = { val := Finset.fold (fun x x_1 => x ∪ x_1) ∅ (fun q => M.δ (q, a✝)) ↑q₀, property := ⋯ }
w✝ : { x // x ∈ M.Q }
h_q₂ : ∃ x ∈ ↑q₀, w✝ ∈ M.δ (x, a✝)
r' : NFA.Run M w✝ w✝¹
hr' : NFA.Run.last r' ∈ M.F
x : { x // x ∈ M.Q }
left✝ : x ∈ ↑q₀
right✝ : w✝ ∈ M.δ (x, a✝)
⊢ ∃ r', NFA.Run.last r' ∈ M.F