![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to mindfa.icn CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Research Unix] / researchv10dc / cmd / icon / tests|
Return to mindfa.icn CVS log | Up to [Research Unix] / researchv10dc / cmd / icon / tests |
1.1 root 1: ### mindfa -- minimize a DFA
2:
3: record dfa(Q,S,d,q0,F) # a DFA
4:
5: procedure main()
6:
7: x := getdfa()
8: every 1 to 10 do
9: showdfa("Reduced",minimize(showdfa("Original",x)))
10:
11: end
12:
13: ## - getdfa() -- accept a dfa from input, return it
14: ##
15: procedure getdfa()
16: local Q,S,d,q0,F
17: local q,a
18:
19: Q := readset("Enter states (1 character names): ")
20: S := readset("Enter input alphabet: ")
21: F := readset("Enter Final states (subset of states): ")
22: writes("What is the start state? ")
23: q0 := read()
24: d := table()
25: every q := !Q & a := !S do {
26: writes("enter delta(",q,",",a,") = ")
27: d[q||":"||a] := read()
28: }
29: return dfa(Q,S,d,q0,F)
30:
31: end
32:
33:
34: ## readset(s) - get a set
35: #
36: procedure readset(s)
37: local t1
38:
39: writes(s)
40: t1 := []
41: every put(t1,!cset(read())) # the cset removes duplicates
42: return t1
43:
44: end
45:
46: ## showdfa(msg,D) -- show a dfa
47: #
48: procedure showdfa(msg,D)
49: local q,a
50:
51: every 1 to 3 do write()
52: write(msg," Deterministic Finite Automaton is:")
53: write()
54: write("\t(Q,S,delta,q0,F)")
55: write()
56: write("where:")
57: write()
58: writeset("Q",D.Q)
59: writeset("S",D.S)
60: writeset("F",D.F)
61: write("\tStart state is ",D.q0)
62: write("\tDelta: ")
63: every q := !D.Q do {
64: every writes("\td(",q,",",a := !D.S,") = ",D.d[q||":"||a])
65: write()
66: }
67: return D
68:
69: end
70:
71: ## writeset(msg,s) -- display a set
72: #
73: procedure writeset(msg,s)
74: local tmp
75: tmp := ""
76: every tmp ||:= !s || ","
77: write("\t",msg," = {",tmp[1:-1],"}")
78: return
79: end
80:
81: ## minimize(D) -- minimize a dfa
82: #
83: global distab, dlists
84:
85: procedure minimize(D)
86: local F,QF
87: local p,q,a,cs
88:
89: distab := table()
90: dlists := table()
91: F := D.F
92: QF := diff(D.Q,D.F)
93: every p := !F & q := !QF do
94: distab[cset(p||q)] := "X"
95: every ((p := !F & q := !F) |
96: (p := !QF & q := !QF)) & p ~== q do
97: if \distab[cset(D.d[p||":"||(a:=!D.S)]||D.d[q||":"||a])] then {
98: distab[cset(p||q)] := "X"
99: marklists(dlists[cset(p||q)])
100: }
101: else
102: every a := !D.S do
103: if D.d[p||":"||a] ~== D.d[q||":"||a] then {
104: cs := cset(D.d[p||":"||a]||D.d[q||":"||a])
105: if cs == cset(p||q) then next
106: /dlists[cs] := []
107: put(dlists[cs],cset(p||q))
108: }
109:
110: return makemdfa(D,distab)
111:
112: end
113:
114: ## marklists(l) -- recursively mark the pair of nodes
115: # on list l.
116: procedure marklists(l)
117: local e
118:
119: if /l then return
120: every e := !l do {
121: distab[e] := "X"
122: marklists(dlists[e])
123: }
124: return
125:
126: end
127:
128: ## makemdfa(D,DT) -- Use the table from the minimization
129: # to construct the minimal dfa
130: procedure makemdfa(D,DT)
131: local elist, etab, qset, tlist, echeck
132: local p, q, Delta, q0
133:
134: etab := table() # table of new states
135: qset := ''
136: every p := !D.Q do {
137: qset ++:= p
138: plike := equiv(p,etab) | cset(p)
139: every q := !diff(D.Q,qset) & p ~== q do
140: if /distab[cset(p||q)] then {
141: plike ++:= equiv(q,etab) | q
142: }
143: etab[plike] := plike
144: }
145: tlist := []
146: elist := []
147: Delta := table()
148: q0 := equiv(D.q0,etab) # start state of reduced machine
149: put(tlist,q0)
150: put(elist,q0) # only worry about states reachable
151: # from [q0]
152: echeck := table() # keep track of states
153: echeck[q0] := q0
154: while q := get(tlist) do
155: every a := !D.S do {
156: Delta[q||":"||a] := equivdelta(q,a,D,etab)
157: if /echeck[Delta[q||":"||a]] then {
158: echeck[Delta[q||":"||a]] := Delta[q||":"||a]
159: put(tlist,Delta[q||":"||a])
160: put(elist,Delta[q||":"||a])
161: }
162: }
163:
164: return dfa(elist,D.S,Delta,q0,finalstates(D,elist))
165: end
166:
167: ## equiv(q,el) -- return the equivalence class in el containing q
168: #
169: procedure equiv(q,el)
170: every p := !el do
171: if p++q == p then return p
172: end
173:
174: ## equivdelta(p,a,D,el) -- apply delta to equiv. classes
175: #
176: procedure equivdelta(p,a,D,el)
177: local q, r
178: q := !p # any state in equiv. class p
179: r := D.d[q||":"||a] # find state in original dfa
180:
181: return equiv(r,el) # return its equivalence class
182: end
183:
184:
185: ## finalstates(D,el) -- build the set of final states
186: #
187: procedure finalstates(D,el)
188: local flist, p, q
189:
190: ftab := table()
191: every p := !D.F do
192: ftab[q := equiv(p,el)] := q
193: flist := []
194: every put(flist,(!sort(ftab))[1])
195: return flist
196: end
197:
198:
199: ## diff(l1,l2) -- return the difference of two sets
200: #
201: procedure diff(l1,l2)
202: local l,t1,t2
203:
204: t1 := ''
205: every t1 ++:= !l1
206:
207: t2 := ''
208: every t2 ++:= !l2
209:
210: l := []
211: every put(l,!(t1--t2))
212: if *l = 0 then fail
213: return l
214: end
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.