diff options
| author | Chloe Brown <chloe.brown.00@outlook.com> | 2021-03-05 00:22:20 +0000 |
|---|---|---|
| committer | Chloe Brown <chloe.brown.00@outlook.com> | 2021-03-05 00:22:20 +0000 |
| commit | 90c7597b6f80e0bd5bb2a9a7245d097d40486518 (patch) | |
| tree | f106450275fb3375d0346a2f02e72f6537f8c5cc | |
| parent | 9c5540562f53be81bfb03ef2b96d7f59b3ddea44 (diff) | |
Prove lemma 3.3
| -rw-r--r-- | src/Cfe/Expression.agda | 1 | ||||
| -rw-r--r-- | src/Cfe/Language/Base.agda | 4 | ||||
| -rw-r--r-- | src/Cfe/Language/Construct/Union.agda | 8 |
3 files changed, 12 insertions, 1 deletions
diff --git a/src/Cfe/Expression.agda b/src/Cfe/Expression.agda index 8162cc0..8497251 100644 --- a/src/Cfe/Expression.agda +++ b/src/Cfe/Expression.agda @@ -7,3 +7,4 @@ module Cfe.Expression where open import Cfe.Expression.Base setoid public +open import Cfe.Expression.Properties setoid public diff --git a/src/Cfe/Language/Base.agda b/src/Cfe/Language/Base.agda index c34de30..74854df 100644 --- a/src/Cfe/Language/Base.agda +++ b/src/Cfe/Language/Base.agda @@ -21,6 +21,7 @@ open import Relation.Binary.PropositionalEquality as ≡ using (_≡_) open import Relation.Binary.Indexed.Heterogeneous infix 4 _∈_ +infix 4 _∉_ Language : ∀ a aℓ → Set (suc c ⊔ suc a ⊔ suc aℓ) Language a aℓ = IndexedSetoid (List C) a aℓ @@ -58,6 +59,9 @@ Lift b bℓ A = record _∈_ : ∀ {a aℓ} → List C → Language a aℓ → Set a _∈_ = flip 𝕃 +_∉_ : ∀ {a aℓ} → List C → Language a aℓ → Set a +l ∉ A = l ∈ A → ⊥ + ∈-cong : ∀ {a aℓ} → (A : Language a aℓ) → ∀ {l₁ l₂} → l₁ ≡ l₂ → l₁ ∈ A → l₂ ∈ A ∈-cong A ≡.refl l∈A = l∈A diff --git a/src/Cfe/Language/Construct/Union.agda b/src/Cfe/Language/Construct/Union.agda index 4ed0774..5099d04 100644 --- a/src/Cfe/Language/Construct/Union.agda +++ b/src/Cfe/Language/Construct/Union.agda @@ -25,7 +25,7 @@ module _ where infix 4 _≈ᵁ_ - infix 4 _∪_ + infix 6 _∪_ Union : List C → Set (a ⊔ b) Union l = l ∈ A ⊎ l ∈ B @@ -93,3 +93,9 @@ isCommutativeMonoid = record where module X≤Y = _≤_ X≤Y module U≤V = _≤_ U≤V + +∪-unique : ∀ {a aℓ b bℓ} {A : Language a aℓ} {B : Language b bℓ} → (∀ x → first A x → first B x → ⊥) → (𝕃.null A → 𝕃.null B → ⊥) → ∀ {l} → l ∈ A ∪ B → (l ∈ A × l ∉ B) ⊎ (l ∉ A × l ∈ B) +∪-unique fA∩fB≡∅ ¬nA∨¬nB {[]} (inj₁ []∈A) = inj₁ ([]∈A , ¬nA∨¬nB []∈A) +∪-unique fA∩fB≡∅ ¬nA∨¬nB {x ∷ l} (inj₁ xl∈A) = inj₁ (xl∈A , (λ xl∈B → fA∩fB≡∅ x (-, xl∈A) (-, xl∈B))) +∪-unique fA∩fB≡∅ ¬nA∨¬nB {[]} (inj₂ []∈B) = inj₂ (flip ¬nA∨¬nB []∈B , []∈B) +∪-unique fA∩fB≡∅ ¬nA∨¬nB {x ∷ l} (inj₂ xl∈B) = inj₂ ((λ xl∈A → fA∩fB≡∅ x (-, xl∈A) (-, xl∈B)) , xl∈B) |