Mercurial > hg > Members > kono > Proof > automaton

changeset 311:59e2d48950e8

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
...
author Shinji KONO <kono@ie.u-ryukyu.ac.jp>
date Sun, 02 Jan 2022 19:28:01 +0900
parents 271ded718895
children 025c05355024
files automaton-in-agda/src/non-regular.agda
diffstat 1 files changed, 15 insertions(+), 14 deletions(-) [+]
line wrap: on
line diff
--- a/automaton-in-agda/src/non-regular.agda	Sun Jan 02 18:51:36 2022 +0900
+++ b/automaton-in-agda/src/non-regular.agda	Sun Jan 02 19:28:01 2022 +0900
@@ -116,8 +116,8 @@
 
 data QDSEQ { Q : Set } { Σ : Set  } { fa : Automaton  Q  Σ} ( finq : FiniteSet Q) (qd : Q) (z1 :  List Σ) :
        {q : Q} {y2 : List Σ} → Trace fa (y2 ++ z1) q → Set where
-   qd-nil : (i : Σ)  → (q : Q) → (tr : Trace fa z1 q) → equal? finq qd q ≡ true → QDSEQ finq qd z1 tr
-   qd-next : (i : Σ) (y2 : List Σ) → (q : Q) → (tr : Trace fa (y2 ++ z1) (δ fa q i)) → equal? finq qd q ≡ false
+   qd-nil :  (q : Q) → (tr : Trace fa z1 q) → equal? finq qd q ≡ true → QDSEQ finq qd z1 tr
+   qd-next : {i : Σ} (y2 : List Σ) → (q : Q) → (tr : Trace fa (y2 ++ z1) (δ fa q i)) → equal? finq qd q ≡ false
        → QDSEQ finq qd z1 tr 
        → QDSEQ finq qd z1 (tnext q tr)
 
@@ -147,7 +147,7 @@
    tra-phase2 : (q : Q)  → (is : List Σ)  → (tr : Trace fa is  q )
        → phase2 finq qd (tr→qs fa is q tr) ≡ true → TA1 fa finq q qd is
    tra-phase2 q (i ∷ is) (tnext q tr) p with equal? finq qd q | inspect ( equal? finq qd) q
-   ... | true | record { eq = eq } = record { y = [] ; z = i ∷ is ; yz=is = refl ; q=qd = qd-nil i q (tnext q tr) eq
+   ... | true | record { eq = eq } = record { y = [] ; z = i ∷ is ; yz=is = refl ; q=qd = qd-nil q (tnext q tr) eq
         ; trace-z  = subst (λ k → Trace fa (i ∷ is) k ) (sym (equal→refl finq eq)) (tnext q tr) ; trace-yz = tnext q tr }
    ... | false | record { eq = ne } = record { y = i ∷ TA1.y ta ; z = TA1.z ta ; yz=is = cong (i ∷_ ) (TA1.yz=is ta )
        ; q=qd = tra-08
@@ -157,7 +157,7 @@
             tra-07 : Trace fa (TA1.y ta ++ TA1.z ta) (δ fa q i)
             tra-07 = subst (λ k → Trace fa k (δ fa q i)) (sym (TA1.yz=is ta)) tr
             tra-08 : QDSEQ finq qd (TA1.z ta) (tnext q (TA1.trace-yz ta))
-            tra-08 = qd-next i (TA1.y ta) q (TA1.trace-yz (tra-phase2 (δ fa q i) is tr p))  ne (TA1.q=qd ta)
+            tra-08 = qd-next (TA1.y ta) q (TA1.trace-yz (tra-phase2 (δ fa q i) is tr p))  ne (TA1.q=qd ta)
    tra-phase1 : (q : Q)  → (is : List Σ)  → (tr : Trace fa is  q ) → phase1 finq qd (tr→qs fa is q tr) ≡ true  → TA fa q is
    tra-phase1 q (i ∷ is) (tnext q tr) p with equal? finq qd q | inspect (equal? finq qd) q
           | phase1 finq qd (tr→qs fa is (δ fa q i) tr) | inspect ( phase1 finq qd)  (tr→qs fa is (δ fa q i) tr) 
@@ -165,7 +165,7 @@
            ; non-nil-y = λ ()
            ; trace-xyz  = tnext q (TA1.trace-yz ta)
            ; trace-xyyz = tra-04 (i ∷ TA1.y ta) q (tnext q (subst (λ k → Trace fa (y1 ++ z1) (δ fa k i) ) (equal→refl finq eq) tryz0))
-              (λ y2 q tr → tra-051 y2 q tr {!!} ) } where 
+              tra-052 } where 
         ta : TA1 fa finq (δ fa q i ) qd is
         ta = tra-phase2 (δ fa q i ) is tr p 
         y1 = TA1.y ta
@@ -176,18 +176,19 @@
         tryz = tnext qd tryz0
         tra-06 : QDSEQ finq qd (TA1.z ta) (TA1.trace-yz ta)
         tra-06 = TA1.q=qd ta 
-        tra-051 : (y2 : List Σ) → (q : Q) → (tr : Trace fa (y2 ++ z1) q) → QDSEQ finq qd z1 tr → equal? finq qd q ≡ is0-bool (length y2)
-        tra-051 .[] q tr (qd-nil i .q .tr x₁) = x₁
-        tra-051 .(i ∷ y2) q .(tnext q tr) (qd-next i y2 .q tr x₁ qdseq) = x₁
+        tra-052 : QDSEQ finq qd z1 (tnext q (subst (λ k → Trace fa (y1 ++ z1) (δ fa k i)) (equal→refl finq eq) tryz0))
+        tra-052 = ?
+        tra-051 : QDSEQ finq qd z1 {!!}
+        tra-051 = TA1.q=qd ta
         tra-04 : (y2 : List Σ) → (q : Q) → (tr : Trace fa (y2 ++ z1) q)
-               → (tra-05 : (y2 : List Σ) → (q : Q) → (tr : Trace fa (y2 ++ z1) q) → equal? finq qd q ≡ is0-bool (length y2))
+               →  QDSEQ finq qd z1 {q} {y2} tr
                → Trace fa (y2 ++ (i ∷ y1) ++ z1) q
-        tra-04 [] q tr tra-05 with equal? finq qd q | inspect (equal? finq qd) q
+        tra-04 [] q tr (qd-nil .q .tr x₁) with equal? finq qd q | inspect (equal? finq qd) q
         ... | true | record { eq = eq } = subst (λ k → Trace fa (i ∷ y1 ++ z1) k) (equal→refl finq eq) tryz
-        ... | false | record { eq = ne } = ⊥-elim ( ¬-bool  ne (tra-05 [] q tr) ) 
-        tra-04 (y0 ∷ y2) q (tnext q tr) tra-05 with equal? finq qd q | inspect (equal? finq qd) q
-        ... | true | record { eq = eq } = ⊥-elim ( ¬-bool (tra-05 (y0 ∷ y2) q (tnext q tr)) eq ) where -- y2 + z1 contains two qd
-        ... | false | record { eq = ne } = tnext q (tra-04 y2 (δ fa q y0) tr tra-05 ) 
+        ... | false | record { eq = ne } = ⊥-elim ( ¬-bool  ne {!!} ) 
+        tra-04 (y0 ∷ y2) q (tnext q tr) (qd-next y2 .q tr x₁ qdseq) with equal? finq qd q | inspect (equal? finq qd) q
+        ... | true | record { eq = eq } = ⊥-elim ( ¬-bool {!!} eq ) where -- y2 + z1 contains two qd
+        ... | false | record { eq = ne } = tnext q (tra-04 y2 (δ fa q y0) tr qdseq ) 
    ... | true | record { eq = eq } | true | record { eq = np} = record { x = i ∷ x ta ; y = y ta ; z = z ta ; xyz=is = cong (i ∷_ ) (xyz=is ta)
            ; non-nil-y = non-nil-y ta
             ; trace-xyz = tnext q (trace-xyz ta ) ; trace-xyyz = tnext q (trace-xyyz ta )} where