computability.epsilon_NFA | Mathlib porting status

Changes since the initial port

The following section lists changes to this file in mathlib3 and mathlib4 that occured after the initial port. Most recent changes are shown first. Hovering over a commit will show all commits associated with the same mathlib3 commit.

Changes in mathlib3

28aa996f

(last sync)

Changes in mathlib3port

mathlib3

mathlib3port

23aa88e3

bump to nightly-2023-09-24-06

mathlib commit https://github.com/leanprover-community/mathlib/commit/ce64cd319bb6b3e82f31c2d38e79080d377be451

5655435f

Diff

@@ -3,7 +3,7 @@ Copyright (c) 2021 Fox Thomson. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Fox Thomson, Yaël Dillies
 -/
-import Mathbin.Computability.NFA
+import Computability.NFA
 
 #align_import computability.epsilon_NFA from "leanprover-community/mathlib"@"23aa88e32dcc9d2a24cca7bc23268567ed4cd7d6"

23aa88e3

bump to nightly-2023-07-20-09

mathlib commit https://github.com/leanprover-community/mathlib/commit/8ea5598db6caeddde6cb734aa179cc2408dbd345

9c56d0dd

Diff

@@ -2,14 +2,11 @@
 Copyright (c) 2021 Fox Thomson. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Fox Thomson, Yaël Dillies
-
-! This file was ported from Lean 3 source module computability.epsilon_NFA
-! leanprover-community/mathlib commit 23aa88e32dcc9d2a24cca7bc23268567ed4cd7d6
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathbin.Computability.NFA
 
+#align_import computability.epsilon_NFA from "leanprover-community/mathlib"@"23aa88e32dcc9d2a24cca7bc23268567ed4cd7d6"
+
 /-!
 # Epsilon Nondeterministic Finite Automata

23aa88e3

bump to nightly-2023-06-20-01

mathlib commit https://github.com/leanprover-community/mathlib/commit/2a0ce625dbb0ffbc7d1316597de0b25c1ec75303

9b351f8c

Diff

@@ -255,7 +255,7 @@ theorem toεNFA_evalFrom_match (M : NFA α σ) (start : Set σ) :
   by
   rw [eval_from, εNFA.evalFrom, to_ε_NFA_ε_closure]
   congr
-  ext (S s)
+  ext S s
   simp only [step_set, εNFA.stepSet, exists_prop, Set.mem_iUnion]
   apply exists_congr
   simp only [and_congr_right_iff]

23aa88e3

bump to nightly-2023-06-13-21

mathlib commit https://github.com/leanprover-community/mathlib/commit/9fb8964792b4237dac6200193a0d533f1b3f7423

829520ac

Diff

@@ -88,10 +88,12 @@ def stepSet (S : Set σ) (a : α) : Set σ :=
 
 variable {M}
 
+#print εNFA.mem_stepSet_iff /-
 @[simp]
 theorem mem_stepSet_iff : s ∈ M.stepSet S a ↔ ∃ t ∈ S, s ∈ M.εClosure (M.step t a) :=
   mem_iUnion₂
 #align ε_NFA.mem_step_set_iff εNFA.mem_stepSet_iff
+-/
 
 #print εNFA.stepSet_empty /-
 @[simp]
@@ -207,6 +209,7 @@ theorem toNFA_correct : M.toNFA.accepts = M.accepts :=
 #align ε_NFA.to_NFA_correct εNFA.toNFA_correct
 -/
 
+#print εNFA.pumping_lemma /-
 theorem pumping_lemma [Fintype σ] {x : List α} (hx : x ∈ M.accepts)
     (hlen : Fintype.card (Set σ) ≤ List.length x) :
     ∃ a b c,
@@ -216,6 +219,7 @@ theorem pumping_lemma [Fintype σ] {x : List α} (hx : x ∈ M.accepts)
   rw [← to_NFA_correct] at hx ⊢
   exact M.to_NFA.pumping_lemma hx hlen
 #align ε_NFA.pumping_lemma εNFA.pumping_lemma
+-/
 
 end εNFA

23aa88e3

bump to nightly-2023-06-04-18

mathlib commit https://github.com/leanprover-community/mathlib/commit/5f25c089cb34db4db112556f23c50d12da81b297

3fb4268b

Diff

@@ -173,7 +173,7 @@ theorem eval_append_singleton (x : List α) (a : α) : M.eval (x ++ [a]) = M.ste
 #print εNFA.accepts /-
 /-- `M.accepts` is the language of `x` such that there is an accept state in `M.eval x`. -/
 def accepts : Language α :=
-  { x | ∃ S ∈ M.accept, S ∈ M.eval x }
+  {x | ∃ S ∈ M.accept, S ∈ M.eval x}
 #align ε_NFA.accepts εNFA.accepts
 -/

23aa88e3

bump to nightly-2023-06-01-16

mathlib commit https://github.com/leanprover-community/mathlib/commit/cca40788df1b8755d5baf17ab2f27dacc2e17acb

b9c87c70

Diff

@@ -213,7 +213,7 @@ theorem pumping_lemma [Fintype σ] {x : List α} (hx : x ∈ M.accepts)
       x = a ++ b ++ c ∧
         a.length + b.length ≤ Fintype.card (Set σ) ∧ b ≠ [] ∧ {a} * {b}∗ * {c} ≤ M.accepts :=
   by
-  rw [← to_NFA_correct] at hx⊢
+  rw [← to_NFA_correct] at hx ⊢
   exact M.to_NFA.pumping_lemma hx hlen
 #align ε_NFA.pumping_lemma εNFA.pumping_lemma

23aa88e3

bump to nightly-2023-05-28-18

mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb

8d353152

Diff

@@ -27,7 +27,7 @@ supplied for true `ε_NFA`'s.
 
 open Set
 
-open Computability
+open scoped Computability
 
 universe u v

23aa88e3

bump to nightly-2023-05-28-06

mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb

ba5d8b97

Diff

@@ -88,12 +88,6 @@ def stepSet (S : Set σ) (a : α) : Set σ :=
 
 variable {M}
 
-/- warning: ε_NFA.mem_step_set_iff -> εNFA.mem_stepSet_iff is a dubious translation:
-lean 3 declaration is
-  forall {α : Type.{u1}} {σ : Type.{u2}} {M : εNFA.{u1, u2} α σ} {S : Set.{u2} σ} {s : σ} {a : α}, Iff (Membership.Mem.{u2, u2} σ (Set.{u2} σ) (Set.hasMem.{u2} σ) s (εNFA.stepSet.{u1, u2} α σ M S a)) (Exists.{succ u2} σ (fun (t : σ) => Exists.{0} (Membership.Mem.{u2, u2} σ (Set.{u2} σ) (Set.hasMem.{u2} σ) t S) (fun (H : Membership.Mem.{u2, u2} σ (Set.{u2} σ) (Set.hasMem.{u2} σ) t S) => Membership.Mem.{u2, u2} σ (Set.{u2} σ) (Set.hasMem.{u2} σ) s (εNFA.εClosure.{u1, u2} α σ M (εNFA.step.{u1, u2} α σ M t ((fun (a : Type.{u1}) (b : Type.{u1}) [self : HasLiftT.{succ u1, succ u1} a b] => self.0) α (Option.{u1} α) (HasLiftT.mk.{succ u1, succ u1} α (Option.{u1} α) (CoeTCₓ.coe.{succ u1, succ u1} α (Option.{u1} α) (coeOption.{u1} α))) a))))))
-but is expected to have type
-  forall {α : Type.{u1}} {σ : Type.{u2}} {M : εNFA.{u1, u2} α σ} {S : Set.{u2} σ} {s : σ} {a : α}, Iff (Membership.mem.{u2, u2} σ (Set.{u2} σ) (Set.instMembershipSet.{u2} σ) s (εNFA.stepSet.{u1, u2} α σ M S a)) (Exists.{succ u2} σ (fun (t : σ) => And (Membership.mem.{u2, u2} σ (Set.{u2} σ) (Set.instMembershipSet.{u2} σ) t S) (Membership.mem.{u2, u2} σ (Set.{u2} σ) (Set.instMembershipSet.{u2} σ) s (εNFA.εClosure.{u1, u2} α σ M (εNFA.step.{u1, u2} α σ M t (Option.some.{u1} α a))))))
-Case conversion may be inaccurate. Consider using '#align ε_NFA.mem_step_set_iff εNFA.mem_stepSet_iffₓ'. -/
 @[simp]
 theorem mem_stepSet_iff : s ∈ M.stepSet S a ↔ ∃ t ∈ S, s ∈ M.εClosure (M.step t a) :=
   mem_iUnion₂
@@ -213,12 +207,6 @@ theorem toNFA_correct : M.toNFA.accepts = M.accepts :=
 #align ε_NFA.to_NFA_correct εNFA.toNFA_correct
 -/
 
-/- warning: ε_NFA.pumping_lemma -> εNFA.pumping_lemma is a dubious translation:
-lean 3 declaration is
-  forall {α : Type.{u1}} {σ : Type.{u2}} (M : εNFA.{u1, u2} α σ) [_inst_1 : Fintype.{u2} σ] {x : List.{u1} α}, (Membership.Mem.{u1, u1} (List.{u1} α) (Language.{u1} α) (Language.hasMem.{u1} α) x (εNFA.accepts.{u1, u2} α σ M)) -> (LE.le.{0} Nat Nat.hasLe (Fintype.card.{u2} (Set.{u2} σ) (Set.fintype.{u2} σ _inst_1)) (List.length.{u1} α x)) -> (Exists.{succ u1} (List.{u1} α) (fun (a : List.{u1} α) => Exists.{succ u1} (List.{u1} α) (fun (b : List.{u1} α) => Exists.{succ u1} (List.{u1} α) (fun (c : List.{u1} α) => And (Eq.{succ u1} (List.{u1} α) x (Append.append.{u1} (List.{u1} α) (List.hasAppend.{u1} α) (Append.append.{u1} (List.{u1} α) (List.hasAppend.{u1} α) a b) c)) (And (LE.le.{0} Nat Nat.hasLe (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat Nat.hasAdd) (List.length.{u1} α a) (List.length.{u1} α b)) (Fintype.card.{u2} (Set.{u2} σ) (Set.fintype.{u2} σ _inst_1))) (And (Ne.{succ u1} (List.{u1} α) b (List.nil.{u1} α)) (LE.le.{u1} (Language.{u1} α) (Preorder.toHasLe.{u1} (Language.{u1} α) (PartialOrder.toPreorder.{u1} (Language.{u1} α) (CompleteSemilatticeInf.toPartialOrder.{u1} (Language.{u1} α) (CompleteLattice.toCompleteSemilatticeInf.{u1} (Language.{u1} α) (Order.Coframe.toCompleteLattice.{u1} (Language.{u1} α) (CompleteDistribLattice.toCoframe.{u1} (Language.{u1} α) (CompleteBooleanAlgebra.toCompleteDistribLattice.{u1} (Language.{u1} α) (Language.completeBooleanAlgebra.{u1} α)))))))) (HMul.hMul.{u1, u1, u1} (Language.{u1} α) (Language.{u1} α) (Language.{u1} α) (instHMul.{u1} (Language.{u1} α) (Language.hasMul.{u1} α)) (HMul.hMul.{u1, u1, u1} (Language.{u1} α) (Language.{u1} α) (Language.{u1} α) (instHMul.{u1} (Language.{u1} α) (Language.hasMul.{u1} α)) (Singleton.singleton.{u1, u1} (List.{u1} α) (Language.{u1} α) (Language.hasSingleton.{u1} α) a) (KStar.kstar.{u1} (Language.{u1} α) (Language.hasKstar.{u1} α) (Singleton.singleton.{u1, u1} (List.{u1} α) (Language.{u1} α) (Language.hasSingleton.{u1} α) b))) (Singleton.singleton.{u1, u1} (List.{u1} α) (Language.{u1} α) (Language.hasSingleton.{u1} α) c)) (εNFA.accepts.{u1, u2} α σ M))))))))
-but is expected to have type
-  forall {α : Type.{u1}} {σ : Type.{u2}} (M : εNFA.{u1, u2} α σ) [_inst_1 : Fintype.{u2} σ] {x : List.{u1} α}, (Membership.mem.{u1, u1} (List.{u1} α) (Language.{u1} α) (instMembershipListLanguage.{u1} α) x (εNFA.accepts.{u1, u2} α σ M)) -> (LE.le.{0} Nat instLENat (Fintype.card.{u2} (Set.{u2} σ) (Set.fintype.{u2} σ _inst_1)) (List.length.{u1} α x)) -> (Exists.{succ u1} (List.{u1} α) (fun (a : List.{u1} α) => Exists.{succ u1} (List.{u1} α) (fun (b : List.{u1} α) => Exists.{succ u1} (List.{u1} α) (fun (c : List.{u1} α) => And (Eq.{succ u1} (List.{u1} α) x (HAppend.hAppend.{u1, u1, u1} (List.{u1} α) (List.{u1} α) (List.{u1} α) (instHAppend.{u1} (List.{u1} α) (List.instAppendList.{u1} α)) (HAppend.hAppend.{u1, u1, u1} (List.{u1} α) (List.{u1} α) (List.{u1} α) (instHAppend.{u1} (List.{u1} α) (List.instAppendList.{u1} α)) a b) c)) (And (LE.le.{0} Nat instLENat (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat instAddNat) (List.length.{u1} α a) (List.length.{u1} α b)) (Fintype.card.{u2} (Set.{u2} σ) (Set.fintype.{u2} σ _inst_1))) (And (Ne.{succ u1} (List.{u1} α) b (List.nil.{u1} α)) (LE.le.{u1} (Language.{u1} α) (Preorder.toLE.{u1} (Language.{u1} α) (PartialOrder.toPreorder.{u1} (Language.{u1} α) (CompleteSemilatticeInf.toPartialOrder.{u1} (Language.{u1} α) (CompleteLattice.toCompleteSemilatticeInf.{u1} (Language.{u1} α) (Order.Coframe.toCompleteLattice.{u1} (Language.{u1} α) (CompleteDistribLattice.toCoframe.{u1} (Language.{u1} α) (CompleteBooleanAlgebra.toCompleteDistribLattice.{u1} (Language.{u1} α) (instCompleteBooleanAlgebraLanguage.{u1} α)))))))) (HMul.hMul.{u1, u1, u1} (Language.{u1} α) (Language.{u1} α) (Language.{u1} α) (instHMul.{u1} (Language.{u1} α) (Language.instMulLanguage.{u1} α)) (HMul.hMul.{u1, u1, u1} (Language.{u1} α) (Language.{u1} α) (Language.{u1} α) (instHMul.{u1} (Language.{u1} α) (Language.instMulLanguage.{u1} α)) (Singleton.singleton.{u1, u1} (List.{u1} α) (Language.{u1} α) (instSingletonListLanguage.{u1} α) a) (KStar.kstar.{u1} (Language.{u1} α) (Language.instKStarLanguage.{u1} α) (Singleton.singleton.{u1, u1} (List.{u1} α) (Language.{u1} α) (instSingletonListLanguage.{u1} α) b))) (Singleton.singleton.{u1, u1} (List.{u1} α) (Language.{u1} α) (instSingletonListLanguage.{u1} α) c)) (εNFA.accepts.{u1, u2} α σ M))))))))
-Case conversion may be inaccurate. Consider using '#align ε_NFA.pumping_lemma εNFA.pumping_lemmaₓ'. -/
 theorem pumping_lemma [Fintype σ] {x : List α} (hx : x ∈ M.accepts)
     (hlen : Fintype.card (Set σ) ≤ List.length x) :
     ∃ a b c,

23aa88e3

bump to nightly-2023-05-16-16

mathlib commit https://github.com/leanprover-community/mathlib/commit/0b9eaaa7686280fad8cce467f5c3c57ee6ce77f8

9cb92e8c

Diff

@@ -215,7 +215,7 @@ theorem toNFA_correct : M.toNFA.accepts = M.accepts :=
 
 /- warning: ε_NFA.pumping_lemma -> εNFA.pumping_lemma is a dubious translation:
 lean 3 declaration is
-  forall {α : Type.{u1}} {σ : Type.{u2}} (M : εNFA.{u1, u2} α σ) [_inst_1 : Fintype.{u2} σ] {x : List.{u1} α}, (Membership.Mem.{u1, u1} (List.{u1} α) (Language.{u1} α) (Language.hasMem.{u1} α) x (εNFA.accepts.{u1, u2} α σ M)) -> (LE.le.{0} Nat Nat.hasLe (Fintype.card.{u2} (Set.{u2} σ) (Set.fintype.{u2} σ _inst_1)) (List.length.{u1} α x)) -> (Exists.{succ u1} (List.{u1} α) (fun (a : List.{u1} α) => Exists.{succ u1} (List.{u1} α) (fun (b : List.{u1} α) => Exists.{succ u1} (List.{u1} α) (fun (c : List.{u1} α) => And (Eq.{succ u1} (List.{u1} α) x (Append.append.{u1} (List.{u1} α) (List.hasAppend.{u1} α) (Append.append.{u1} (List.{u1} α) (List.hasAppend.{u1} α) a b) c)) (And (LE.le.{0} Nat Nat.hasLe (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat Nat.hasAdd) (List.length.{u1} α a) (List.length.{u1} α b)) (Fintype.card.{u2} (Set.{u2} σ) (Set.fintype.{u2} σ _inst_1))) (And (Ne.{succ u1} (List.{u1} α) b (List.nil.{u1} α)) (LE.le.{u1} (Language.{u1} α) (Preorder.toLE.{u1} (Language.{u1} α) (PartialOrder.toPreorder.{u1} (Language.{u1} α) (CompleteSemilatticeInf.toPartialOrder.{u1} (Language.{u1} α) (CompleteLattice.toCompleteSemilatticeInf.{u1} (Language.{u1} α) (Order.Coframe.toCompleteLattice.{u1} (Language.{u1} α) (CompleteDistribLattice.toCoframe.{u1} (Language.{u1} α) (CompleteBooleanAlgebra.toCompleteDistribLattice.{u1} (Language.{u1} α) (Language.completeBooleanAlgebra.{u1} α)))))))) (HMul.hMul.{u1, u1, u1} (Language.{u1} α) (Language.{u1} α) (Language.{u1} α) (instHMul.{u1} (Language.{u1} α) (Language.hasMul.{u1} α)) (HMul.hMul.{u1, u1, u1} (Language.{u1} α) (Language.{u1} α) (Language.{u1} α) (instHMul.{u1} (Language.{u1} α) (Language.hasMul.{u1} α)) (Singleton.singleton.{u1, u1} (List.{u1} α) (Language.{u1} α) (Language.hasSingleton.{u1} α) a) (KStar.kstar.{u1} (Language.{u1} α) (Language.hasKstar.{u1} α) (Singleton.singleton.{u1, u1} (List.{u1} α) (Language.{u1} α) (Language.hasSingleton.{u1} α) b))) (Singleton.singleton.{u1, u1} (List.{u1} α) (Language.{u1} α) (Language.hasSingleton.{u1} α) c)) (εNFA.accepts.{u1, u2} α σ M))))))))
+  forall {α : Type.{u1}} {σ : Type.{u2}} (M : εNFA.{u1, u2} α σ) [_inst_1 : Fintype.{u2} σ] {x : List.{u1} α}, (Membership.Mem.{u1, u1} (List.{u1} α) (Language.{u1} α) (Language.hasMem.{u1} α) x (εNFA.accepts.{u1, u2} α σ M)) -> (LE.le.{0} Nat Nat.hasLe (Fintype.card.{u2} (Set.{u2} σ) (Set.fintype.{u2} σ _inst_1)) (List.length.{u1} α x)) -> (Exists.{succ u1} (List.{u1} α) (fun (a : List.{u1} α) => Exists.{succ u1} (List.{u1} α) (fun (b : List.{u1} α) => Exists.{succ u1} (List.{u1} α) (fun (c : List.{u1} α) => And (Eq.{succ u1} (List.{u1} α) x (Append.append.{u1} (List.{u1} α) (List.hasAppend.{u1} α) (Append.append.{u1} (List.{u1} α) (List.hasAppend.{u1} α) a b) c)) (And (LE.le.{0} Nat Nat.hasLe (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat Nat.hasAdd) (List.length.{u1} α a) (List.length.{u1} α b)) (Fintype.card.{u2} (Set.{u2} σ) (Set.fintype.{u2} σ _inst_1))) (And (Ne.{succ u1} (List.{u1} α) b (List.nil.{u1} α)) (LE.le.{u1} (Language.{u1} α) (Preorder.toHasLe.{u1} (Language.{u1} α) (PartialOrder.toPreorder.{u1} (Language.{u1} α) (CompleteSemilatticeInf.toPartialOrder.{u1} (Language.{u1} α) (CompleteLattice.toCompleteSemilatticeInf.{u1} (Language.{u1} α) (Order.Coframe.toCompleteLattice.{u1} (Language.{u1} α) (CompleteDistribLattice.toCoframe.{u1} (Language.{u1} α) (CompleteBooleanAlgebra.toCompleteDistribLattice.{u1} (Language.{u1} α) (Language.completeBooleanAlgebra.{u1} α)))))))) (HMul.hMul.{u1, u1, u1} (Language.{u1} α) (Language.{u1} α) (Language.{u1} α) (instHMul.{u1} (Language.{u1} α) (Language.hasMul.{u1} α)) (HMul.hMul.{u1, u1, u1} (Language.{u1} α) (Language.{u1} α) (Language.{u1} α) (instHMul.{u1} (Language.{u1} α) (Language.hasMul.{u1} α)) (Singleton.singleton.{u1, u1} (List.{u1} α) (Language.{u1} α) (Language.hasSingleton.{u1} α) a) (KStar.kstar.{u1} (Language.{u1} α) (Language.hasKstar.{u1} α) (Singleton.singleton.{u1, u1} (List.{u1} α) (Language.{u1} α) (Language.hasSingleton.{u1} α) b))) (Singleton.singleton.{u1, u1} (List.{u1} α) (Language.{u1} α) (Language.hasSingleton.{u1} α) c)) (εNFA.accepts.{u1, u2} α σ M))))))))
 but is expected to have type
   forall {α : Type.{u1}} {σ : Type.{u2}} (M : εNFA.{u1, u2} α σ) [_inst_1 : Fintype.{u2} σ] {x : List.{u1} α}, (Membership.mem.{u1, u1} (List.{u1} α) (Language.{u1} α) (instMembershipListLanguage.{u1} α) x (εNFA.accepts.{u1, u2} α σ M)) -> (LE.le.{0} Nat instLENat (Fintype.card.{u2} (Set.{u2} σ) (Set.fintype.{u2} σ _inst_1)) (List.length.{u1} α x)) -> (Exists.{succ u1} (List.{u1} α) (fun (a : List.{u1} α) => Exists.{succ u1} (List.{u1} α) (fun (b : List.{u1} α) => Exists.{succ u1} (List.{u1} α) (fun (c : List.{u1} α) => And (Eq.{succ u1} (List.{u1} α) x (HAppend.hAppend.{u1, u1, u1} (List.{u1} α) (List.{u1} α) (List.{u1} α) (instHAppend.{u1} (List.{u1} α) (List.instAppendList.{u1} α)) (HAppend.hAppend.{u1, u1, u1} (List.{u1} α) (List.{u1} α) (List.{u1} α) (instHAppend.{u1} (List.{u1} α) (List.instAppendList.{u1} α)) a b) c)) (And (LE.le.{0} Nat instLENat (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat instAddNat) (List.length.{u1} α a) (List.length.{u1} α b)) (Fintype.card.{u2} (Set.{u2} σ) (Set.fintype.{u2} σ _inst_1))) (And (Ne.{succ u1} (List.{u1} α) b (List.nil.{u1} α)) (LE.le.{u1} (Language.{u1} α) (Preorder.toLE.{u1} (Language.{u1} α) (PartialOrder.toPreorder.{u1} (Language.{u1} α) (CompleteSemilatticeInf.toPartialOrder.{u1} (Language.{u1} α) (CompleteLattice.toCompleteSemilatticeInf.{u1} (Language.{u1} α) (Order.Coframe.toCompleteLattice.{u1} (Language.{u1} α) (CompleteDistribLattice.toCoframe.{u1} (Language.{u1} α) (CompleteBooleanAlgebra.toCompleteDistribLattice.{u1} (Language.{u1} α) (instCompleteBooleanAlgebraLanguage.{u1} α)))))))) (HMul.hMul.{u1, u1, u1} (Language.{u1} α) (Language.{u1} α) (Language.{u1} α) (instHMul.{u1} (Language.{u1} α) (Language.instMulLanguage.{u1} α)) (HMul.hMul.{u1, u1, u1} (Language.{u1} α) (Language.{u1} α) (Language.{u1} α) (instHMul.{u1} (Language.{u1} α) (Language.instMulLanguage.{u1} α)) (Singleton.singleton.{u1, u1} (List.{u1} α) (Language.{u1} α) (instSingletonListLanguage.{u1} α) a) (KStar.kstar.{u1} (Language.{u1} α) (Language.instKStarLanguage.{u1} α) (Singleton.singleton.{u1, u1} (List.{u1} α) (Language.{u1} α) (instSingletonListLanguage.{u1} α) b))) (Singleton.singleton.{u1, u1} (List.{u1} α) (Language.{u1} α) (instSingletonListLanguage.{u1} α) c)) (εNFA.accepts.{u1, u2} α σ M))))))))
 Case conversion may be inaccurate. Consider using '#align ε_NFA.pumping_lemma εNFA.pumping_lemmaₓ'. -/

23aa88e3

bump to nightly-2023-05-14-08

mathlib commit https://github.com/leanprover-community/mathlib/commit/e3fb84046afd187b710170887195d50bada934ee

d31da313

Diff

@@ -96,7 +96,7 @@ but is expected to have type
 Case conversion may be inaccurate. Consider using '#align ε_NFA.mem_step_set_iff εNFA.mem_stepSet_iffₓ'. -/
 @[simp]
 theorem mem_stepSet_iff : s ∈ M.stepSet S a ↔ ∃ t ∈ S, s ∈ M.εClosure (M.step t a) :=
-  mem_unionᵢ₂
+  mem_iUnion₂
 #align ε_NFA.mem_step_set_iff εNFA.mem_stepSet_iff
 
 #print εNFA.stepSet_empty /-
@@ -264,7 +264,7 @@ theorem toεNFA_evalFrom_match (M : NFA α σ) (start : Set σ) :
   rw [eval_from, εNFA.evalFrom, to_ε_NFA_ε_closure]
   congr
   ext (S s)
-  simp only [step_set, εNFA.stepSet, exists_prop, Set.mem_unionᵢ]
+  simp only [step_set, εNFA.stepSet, exists_prop, Set.mem_iUnion]
   apply exists_congr
   simp only [and_congr_right_iff]
   intro t ht

23aa88e3

bump to nightly-2023-02-23-03

mathlib commit https://github.com/leanprover-community/mathlib/commit/3ade05ac9447ae31a22d2ea5423435e054131240

5c91f1b0

Diff

@@ -4,7 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Fox Thomson, Yaël Dillies
 
 ! This file was ported from Lean 3 source module computability.epsilon_NFA
-! leanprover-community/mathlib commit a239cd3e7ac2c7cde36c913808f9d40c411344f6
+! leanprover-community/mathlib commit 23aa88e32dcc9d2a24cca7bc23268567ed4cd7d6
 ! Please do not edit these lines, except to modify the commit id
 ! if you have ported upstream changes.
 -/
@@ -13,6 +13,9 @@ import Mathbin.Computability.NFA
 /-!
 # Epsilon Nondeterministic Finite Automata
 
+> THIS FILE IS SYNCHRONIZED WITH MATHLIB4.
+> Any changes to this file require a corresponding PR to mathlib4.
+
 This file contains the definition of an epsilon Nondeterministic Finite Automaton (`ε_NFA`), a state
 machine which determines whether a string (implemented as a list over an arbitrary alphabet) is in a
 regular set by evaluating the string over every possible path, also having access to ε-transitons,

a239cd3e

bump to nightly-2023-02-21-16

mathlib commit https://github.com/leanprover-community/mathlib/commit/bd9851ca476957ea4549eb19b40e7b5ade9428cc

1107b979

Changes in mathlib4

mathlib3

mathlib4

28aa996f

doc: @[inherit_doc] on notations (#9942)

Make all the notations that unambiguously should inherit the docstring of their definition actually inherit it.

Also write a few docstrings by hand. I only wrote the ones I was competent to write and which I was sure of. Some docstrings come from mathlib3 as they were lost during the early port.

This PR is only intended as a first pass There are many more docstrings to add.

08f7e99d

Diff

@@ -35,8 +35,13 @@ universe u v
   Since this definition allows for Automata with infinite states, a `Fintype` instance must be
   supplied for true `εNFA`'s. -/
 structure εNFA (α : Type u) (σ : Type v) where
+  /-- Transition function. The automaton is rendered non-deterministic by this transition function
+  returning `Set σ` (rather than `σ`), and ε-transitions are made possible by taking `Option α`
+  (rather than `α`). -/
   step : σ → Option α → Set σ
+  /-- Starting states. -/
   start : Set σ
+  /-- Set of acceptance states. -/
   accept : Set σ
 #align ε_NFA εNFA

28aa996f

chore: script to replace headers with #align_import statements (#5979)

depends on: #5966

Co-authored-by: Eric Wieser <wieser.eric@gmail.com> Co-authored-by: Scott Morrison <scott.morrison@gmail.com>

89aa3a3b

Diff

@@ -2,14 +2,11 @@
 Copyright (c) 2021 Fox Thomson. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Fox Thomson, Yaël Dillies
-
-! This file was ported from Lean 3 source module computability.epsilon_NFA
-! leanprover-community/mathlib commit 28aa996fc6fb4317f0083c4e6daf79878d81be33
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathlib.Computability.NFA
 
+#align_import computability.epsilon_NFA from "leanprover-community/mathlib"@"28aa996fc6fb4317f0083c4e6daf79878d81be33"
+
 /-!
 # Epsilon Nondeterministic Finite Automata

28aa996f

fix: precedences of ⨆⋃⋂⨅ (#5614)

e3c8f983

Diff

@@ -71,7 +71,7 @@ theorem εClosure_univ : M.εClosure univ = univ :=
 
 /-- `M.stepSet S a` is the union of the ε-closure of `M.step s a` for all `s ∈ S`. -/
 def stepSet (S : Set σ) (a : α) : Set σ :=
-  ⋃ s ∈ S, M.εClosure <| M.step s a
+  ⋃ s ∈ S, M.εClosure (M.step s a)
 #align ε_NFA.step_set εNFA.stepSet
 
 variable {M}

28aa996f

chore: fix many typos (#4983)

These are all doc fixes

54b72114

Diff

@@ -15,7 +15,7 @@ import Mathlib.Computability.NFA
 
 This file contains the definition of an epsilon Nondeterministic Finite Automaton (`εNFA`), a state
 machine which determines whether a string (implemented as a list over an arbitrary alphabet) is in a
-regular set by evaluating the string over every possible path, also having access to ε-transitons,
+regular set by evaluating the string over every possible path, also having access to ε-transitions,
 which can be followed without reading a character.
 Since this definition allows for automata with infinite states, a `Fintype` instance must be
 supplied for true `εNFA`'s.

28aa996f

chore: Rename to sSup/iSup (#3938)

As discussed on Zulip

Renames

supₛ → sSup
infₛ → sInf
supᵢ → iSup
infᵢ → iInf
bsupₛ → bsSup
binfₛ → bsInf
bsupᵢ → biSup
binfᵢ → biInf
csupₛ → csSup
cinfₛ → csInf
csupᵢ → ciSup
cinfᵢ → ciInf
unionₛ → sUnion
interₛ → sInter
unionᵢ → iUnion
interᵢ → iInter
bunionₛ → bsUnion
binterₛ → bsInter
bunionᵢ → biUnion
binterᵢ → biInter

Co-authored-by: Parcly Taxel <reddeloostw@gmail.com>

d1eb6264

Diff

@@ -78,12 +78,12 @@ variable {M}
 
 @[simp]
 theorem mem_stepSet_iff : s ∈ M.stepSet S a ↔ ∃ t ∈ S, s ∈ M.εClosure (M.step t a) := by
-  simp_rw [stepSet, mem_unionᵢ₂, exists_prop]
+  simp_rw [stepSet, mem_iUnion₂, exists_prop]
 #align ε_NFA.mem_step_set_iff εNFA.mem_stepSet_iff
 
 @[simp]
 theorem stepSet_empty (a : α) : M.stepSet ∅ a = ∅ := by
-  simp_rw [stepSet, mem_empty_iff_false, unionᵢ_false, unionᵢ_empty]
+  simp_rw [stepSet, mem_empty_iff_false, iUnion_false, iUnion_empty]
 #align ε_NFA.step_set_empty εNFA.stepSet_empty
 
 variable (M)
@@ -198,7 +198,7 @@ theorem toεNFA_evalFrom_match (M : NFA α σ) (start : Set σ) :
   rw [evalFrom, εNFA.evalFrom, toεNFA_εClosure]
   suffices εNFA.stepSet (toεNFA M) = stepSet M by rw [this]
   ext S s
-  simp only [stepSet, εNFA.stepSet, exists_prop, Set.mem_unionᵢ]
+  simp only [stepSet, εNFA.stepSet, exists_prop, Set.mem_iUnion]
   apply exists_congr
   simp only [and_congr_right_iff]
   intro _ _

28aa996f

feat: port Computability.EpsilonNFA (#2386)

a4a916a2

`computability.epsilon_NFA` ⟷ `Mathlib.Computability.EpsilonNFA`

Changes since the initial port

Changes in mathlib3

Changes in mathlib3port

Changes in mathlib4

Renames

Dependencies 2 + 208

computability.epsilon_NFA ⟷ Mathlib.Computability.EpsilonNFA

Changes since the initial port

Changes in mathlib3

Changes in mathlib3port

Changes in mathlib4

Renames

Dependencies 2 + 208

`computability.epsilon_NFA` ⟷ `Mathlib.Computability.EpsilonNFA`