![[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.