|
267
|
1 {-# OPTIONS --allow-unsolved-metas #-}
|
|
141
|
2 module automaton-ex where
|
|
|
3
|
|
|
4 open import Data.Nat
|
|
|
5 open import Data.List
|
|
|
6 open import Data.Maybe
|
|
|
7 open import Relation.Binary.PropositionalEquality hiding ( [_] )
|
|
266
|
8 open import Relation.Binary.Definitions
|
|
141
|
9 open import Relation.Nullary using (¬_; Dec; yes; no)
|
|
|
10 open import logic
|
|
|
11
|
|
|
12 open import automaton
|
|
|
13 open Automaton
|
|
|
14
|
|
|
15 data StatesQ : Set where
|
|
|
16 q1 : StatesQ
|
|
|
17 q2 : StatesQ
|
|
|
18 q3 : StatesQ
|
|
|
19
|
|
|
20 data In2 : Set where
|
|
|
21 i0 : In2
|
|
|
22 i1 : In2
|
|
266
|
23
|
|
|
24 transitionQ : StatesQ → In2 → StatesQ
|
|
141
|
25 transitionQ q1 i0 = q1
|
|
|
26 transitionQ q1 i1 = q2
|
|
|
27 transitionQ q2 i0 = q3
|
|
|
28 transitionQ q2 i1 = q2
|
|
|
29 transitionQ q3 i0 = q2
|
|
|
30 transitionQ q3 i1 = q2
|
|
|
31
|
|
|
32 aendQ : StatesQ → Bool
|
|
330
|
33 aendQ q1 = false
|
|
141
|
34 aendQ q2 = true
|
|
330
|
35 aendQ q3 = false
|
|
141
|
36
|
|
|
37 a1 : Automaton StatesQ In2
|
|
|
38 a1 = record {
|
|
|
39 δ = transitionQ
|
|
|
40 ; aend = aendQ
|
|
|
41 }
|
|
|
42
|
|
|
43 test1 : accept a1 q1 ( i0 ∷ i1 ∷ i0 ∷ [] ) ≡ false
|
|
|
44 test1 = refl
|
|
|
45 test2 = accept a1 q1 ( i0 ∷ i1 ∷ i0 ∷ i1 ∷ [] )
|
|
266
|
46 test3 = trace a1 q1 ( i0 ∷ i1 ∷ i0 ∷ i1 ∷ [] )
|
|
141
|
47
|
|
|
48 data States1 : Set where
|
|
|
49 sr : States1
|
|
|
50 ss : States1
|
|
|
51 st : States1
|
|
|
52
|
|
|
53 transition1 : States1 → In2 → States1
|
|
|
54 transition1 sr i0 = sr
|
|
|
55 transition1 sr i1 = ss
|
|
|
56 transition1 ss i0 = sr
|
|
|
57 transition1 ss i1 = st
|
|
|
58 transition1 st i0 = sr
|
|
|
59 transition1 st i1 = st
|
|
|
60
|
|
|
61 fin1 : States1 → Bool
|
|
|
62 fin1 st = true
|
|
|
63 fin1 ss = false
|
|
|
64 fin1 sr = false
|
|
|
65
|
|
|
66 am1 : Automaton States1 In2
|
|
|
67 am1 = record { δ = transition1 ; aend = fin1 }
|
|
|
68
|
|
|
69
|
|
|
70 example1-1 = accept am1 sr ( i0 ∷ i1 ∷ i0 ∷ [] )
|
|
|
71 example1-2 = accept am1 sr ( i1 ∷ i1 ∷ i1 ∷ [] )
|
|
|
72 trace-2 = trace am1 sr ( i1 ∷ i1 ∷ i1 ∷ [] )
|
|
|
73
|
|
|
74 example1-3 = reachable am1 sr st ( i1 ∷ i1 ∷ i1 ∷ [] )
|
|
|
75
|
|
266
|
76 -- data Dec' (A : Set) : Set where
|
|
|
77 -- yes' : A → Dec' A
|
|
|
78 -- no' : ¬ A → Dec' A
|
|
|
79 --
|
|
|
80 -- ieq' : (i i' : In2 ) → Dec' ( i ≡ i' )
|
|
|
81 -- ieq' i0 i0 = yes' refl
|
|
|
82 -- ieq' i1 i1 = yes' refl
|
|
|
83 -- ieq' i0 i1 = no' ( λ () )
|
|
|
84 -- ieq' i1 i0 = no' ( λ () )
|
|
|
85
|
|
141
|
86 ieq : (i i' : In2 ) → Dec ( i ≡ i' )
|
|
|
87 ieq i0 i0 = yes refl
|
|
|
88 ieq i1 i1 = yes refl
|
|
|
89 ieq i0 i1 = no ( λ () )
|
|
|
90 ieq i1 i0 = no ( λ () )
|
|
|
91
|
|
266
|
92 -- p.83 problem 1.4
|
|
|
93 --
|
|
|
94 -- w has at least three i0's and at least two i1's
|
|
|
95
|
|
|
96 count-chars : List In2 → In2 → ℕ
|
|
|
97 count-chars [] _ = 0
|
|
|
98 count-chars (h ∷ t) x with ieq h x
|
|
|
99 ... | yes y = suc ( count-chars t x )
|
|
|
100 ... | no n = count-chars t x
|
|
|
101
|
|
|
102 test11 : count-chars ( i1 ∷ i1 ∷ i0 ∷ [] ) i0 ≡ 1
|
|
|
103 test11 = refl
|
|
|
104
|
|
|
105 ex1_4a : (x : List In2) → Bool
|
|
|
106 ex1_4a x = ( count-chars x i0 ≥b 3 ) /\ ( count-chars x i1 ≥b 2 )
|
|
|
107
|
|
|
108 language' : { Σ : Set } → Set
|
|
|
109 language' {Σ} = List Σ → Bool
|
|
|
110
|
|
|
111 lang14a : language' {In2}
|
|
|
112 lang14a = ex1_4a
|
|
|
113
|
|
|
114 open _∧_
|
|
|
115
|
|
|
116 am14a-tr : ℕ ∧ ℕ → In2 → ℕ ∧ ℕ
|
|
|
117 am14a-tr p i0 = record { proj1 = suc (proj1 p) ; proj2 = proj2 p }
|
|
|
118 am14a-tr p i1 = record { proj1 = proj1 p ; proj2 = suc (proj2 p) }
|
|
|
119
|
|
|
120 am14a : Automaton (ℕ ∧ ℕ) In2
|
|
|
121 am14a = record { δ = am14a-tr ; aend = λ x → ( proj1 x ≥b 3 ) /\ ( proj2 x ≥b 2 )}
|
|
|
122
|
|
|
123 data am14s : Set where
|
|
|
124 a00 : am14s
|
|
|
125 a10 : am14s
|
|
|
126 a20 : am14s
|
|
|
127 a30 : am14s
|
|
|
128 a01 : am14s
|
|
|
129 a11 : am14s
|
|
|
130 a21 : am14s
|
|
|
131 a31 : am14s
|
|
|
132 a02 : am14s
|
|
|
133 a12 : am14s
|
|
|
134 a22 : am14s
|
|
|
135 a32 : am14s
|
|
|
136
|
|
|
137 am14a-tr' : am14s → In2 → am14s
|
|
|
138 am14a-tr' a00 i0 = a10
|
|
|
139 am14a-tr' _ _ = a10
|
|
|
140
|
|
|
141 am14a' : Automaton am14s In2
|
|
|
142 am14a' = record { δ = am14a-tr' ; aend = λ x → {!!} }
|
