##// END OF EJS Templates
implab » ImplabNet
RSS
sync
cin -
r168:8fb9c9507a26 ref20160224
parent child
Show More
Show file before | Show file after | Hide comments
@@ -1,251 +1,293
1 1 using Implab;
2 2 using System;
3 3 using System.Collections.Generic;
4 4 using System.Linq;
5 5
6 6 namespace Implab.Automaton {
7 7 public class DFATransitionTable : IDFATableBuilder {
8 8 DFAStateDescriptior[] m_dfaTable;
9 9
10 10 int m_stateCount;
11 11 int m_symbolCount;
12 12 int m_initialState;
13 13
14 14 readonly HashSet<int> m_finalStates = new HashSet<int>();
15 15 readonly HashSet<AutomatonTransition> m_transitions = new HashSet<AutomatonTransition>();
16 16
17 17
18 18 #region IDFADefinition implementation
19 19
20 20 public DFAStateDescriptior[] GetTransitionTable() {
21 21 if (m_dfaTable == null) {
22 22 if (m_stateCount <= 0)
23 23 throw new InvalidOperationException("Invalid automaton definition: states count = {0}", m_stateCount);
24 24 if (m_symbolCount <= 0)
25 25 throw new InvalidOperationException("Invalid automaton definition: symbols count = {0}", m_symbolCount);
26 26
27 27 m_dfaTable = ConstructTransitionTable();
28 28 }
29 29 return m_dfaTable;
30 30 }
31 31
32 32 public bool IsFinalState(int s) {
33 33 Safe.ArgumentInRange(s, 0, m_stateCount, "s");
34 34
35 35 return m_dfaTable != null ? m_dfaTable[s].final : m_finalStates.Contains(s);
36 36 }
37 37
38 38 public IEnumerable<int> FinalStates {
39 39 get {
40 40 return m_finalStates;
41 41 }
42 42 }
43 43
44 44 public int StateCount {
45 45 get { return m_stateCount; }
46 46 }
47 47
48 48 public int AlphabetSize {
49 49 get { return m_symbolCount; }
50 50 }
51 51
52 52 public int InitialState {
53 53 get { return m_initialState; }
54 54 }
55 55
56 int[] NewTransitionArray() {
57 var t = new int[m_symbolCount];
58
59 for (var i = 0; i < m_symbolCount; i++)
60 t[i] = DFAConst.UNREACHABLE_STATE;
61 return t;
62 }
63
56 64 #endregion
57 65
58 66 protected virtual DFAStateDescriptior[] ConstructTransitionTable() {
59 67 var dfaTable = new DFAStateDescriptior[m_stateCount];
60 68
61 foreach (var pair in m_finalStates) {
62 var idx = pair.Key;
63
64 dfaTable[idx].final = true;
65 dfaTable[idx].tag = pair.Value;
66 }
67 69
68 70 foreach (var t in m_transitions) {
69 if (dfaTable[t.s1].transitions == null) {
70 dfaTable[t.s1].transitions = new int[m_symbolCount];
71 for (int i = 0; i < dfaTable[t.s1].transitions.Length; i++)
72 dfaTable[t.s1].transitions[i] = DFAConst.UNREACHABLE_STATE;
73 }
74
71 if (dfaTable[t.s1].transitions == null)
72 dfaTable[t.s1] = new DFAStateDescriptior(NewTransitionArray(), m_finalStates.Contains(t.s1));
73
75 74 dfaTable[t.s1].transitions[t.edge] = t.s2;
76 75 }
76
77 foreach (var s in m_finalStates)
78 if (!dfaTable[s].final)
79 m_dfaTable[s] = new DFAStateDescriptior(NewTransitionArray, true);
80
77 81 }
78 82
79 83 #region IDFADefinitionBuilder
80 84
81 85 public void DefineTransition(int s1, int s2, int symbol) {
82 86 if (m_dfaTable != null)
83 87 throw new InvalidOperationException("The transition table is already built");
84 88
85 89 Safe.ArgumentAssert(s1 > 0, "s1");
86 90 Safe.ArgumentAssert(s2 > 0, "s2");
87 91 Safe.ArgumentAssert(symbol >= 0, "symbol");
88 92
89 93 m_stateCount = Math.Max(Math.Max(m_stateCount, s1 + 1), s2 + 1);
90 94 m_symbolCount = Math.Max(m_symbolCount, symbol + 1);
91 95
92 96 m_transitions.Add(new AutomatonTransition(s1, s2, symbol));
93 97 }
94 98
95 99 public void MarkFinalState(int state, params TTag[] tags) {
96 100 if (m_dfaTable != null)
97 101 throw new InvalidOperationException("The transition table is already built");
98 102
99 103 m_finalStates[state] = tags;
100 104 }
101 105
102 106 public void SetInitialState(int s) {
103 107 Safe.ArgumentAssert(s >= 0, "s");
104 108 m_initialState = s;
105 109 }
106 110
107 111
108 112 #endregion
109 113
114 protected virtual IEnumerable<HashSet<int>> GroupFinalStates() {
115 return new HashSet<int>[] { m_finalStates };
116 }
117
110 118 protected void Optimize<TInput, TState>(
111 IDFATableBuilder<TTag> optimalDFA,
119 IDFATableBuilder optimalDFA,
112 120 IAlphabet<TInput> inputAlphabet,
113 121 IAlphabetBuilder<TInput> optimalInputAlphabet,
114 122 IAlphabet<TState> stateAlphabet,
115 123 IAlphabetBuilder<TState> optimalStateAlphabet
116 124 ) {
117 125 Safe.ArgumentNotNull(optimalDFA, "dfa");
118 126 Safe.ArgumentNotNull(optimalInputAlphabet, "optimalInputAlphabet");
119 127 Safe.ArgumentNotNull(optimalStateAlphabet, "optimalStateAlphabet");
120 128 Safe.ArgumentNotNull(inputAlphabet, "inputAlphabet");
121 129 Safe.ArgumentNotNull(stateAlphabet, "stateAlphabet");
122 130
123 131 if (inputAlphabet.Count != m_symbolCount)
124 132 throw new InvalidOperationException("The input symbols aphabet mismatch");
125 133 if (stateAlphabet.Count != m_stateCount)
126 134 throw new InvalidOperationException("The states alphabet mismatch");
127 135
128 136 var setComparer = new CustomEqualityComparer<HashSet<int>>(
129 137 (x, y) => x.SetEquals(y),
130 138 s => s.Sum(x => x.GetHashCode())
131 139 );
132 140
133 var arrayComparer = new CustomEqualityComparer<TTag[]>(
134 (x,y) => (new HashSet<int>(x)).SetEquals(new HashSet<int>(y)),
135 a => a.Sum(x => x.GetHashCode())
136 );
137
138 141 var optimalStates = new HashSet<HashSet<int>>(setComparer);
139 142 var queue = new HashSet<HashSet<int>>(setComparer);
140 143
141 144 // получаем конечные состояния, сгруппированные по маркерам
142 145 optimalStates.UnionWith(
143 m_finalStates
144 .GroupBy(pair => pair.Value, arrayComparer)
145 .Select(
146 g => new HashSet<int>(
147 g.Select( pair => pair.Key)
148 )
149 )
146 GroupFinalStates()
150 147 );
151 148
152 149 var state = new HashSet<int>(
153 150 Enumerable
154 151 .Range(0, m_stateCount - 1)
155 .Where(i => !m_finalStates.ContainsKey(i))
152 .Where(i => !m_finalStates.Contains(i))
156 153 );
154
157 155 optimalStates.Add(state);
158 156 queue.Add(state);
159 157
160 158 var rmap = m_transitions
161 159 .GroupBy(t => t.s2)
162 160 .ToLookup(
163 161 g => g.Key, // s2
164 162 g => g.ToLookup(t => t.edge, t => t.s1)
165 163 );
166 164
167 165 while (queue.Count > 0) {
168 166 var stateA = queue.First();
169 167 queue.Remove(stateA);
170 168
171 169 for (int c = 0; c < m_symbolCount; c++) {
172 170 var stateX = new HashSet<int>();
173 171 foreach(var a in stateA)
174 172 stateX.UnionWith(rmap[a][c]); // all states from wich 'c' leads to 'a'
175 173
176 174 foreach (var stateY in optimalStates.ToArray()) {
177 175 if (stateX.Overlaps(stateY) && !stateY.IsSubsetOf(stateX)) {
178 176 var stateR1 = new HashSet<int>(stateY);
179 177 var stateR2 = new HashSet<int>(stateY);
180 178
181 179 stateR1.IntersectWith(stateX);
182 180 stateR2.ExceptWith(stateX);
183 181
184 182 optimalStates.Remove(stateY);
185 183 optimalStates.Add(stateR1);
186 184 optimalStates.Add(stateR2);
187 185
188 186 if (queue.Contains(stateY)) {
189 187 queue.Remove(stateY);
190 188 queue.Add(stateR1);
191 189 queue.Add(stateR2);
192 190 } else {
193 191 queue.Add(stateR1.Count <= stateR2.Count ? stateR1 : stateR2);
194 192 }
195 193 }
196 194 }
197 195 }
198 196 }
199 197
200 198 // карта получения оптимального состояния по соотвествующему ему простому состоянию
201 199 var statesMap = stateAlphabet.Reclassify(optimalStateAlphabet, optimalStates);
202 200
203 201 // получаем минимальный алфавит
204 202 // входные символы не различимы, если Move(s,a1) == Move(s,a2)
205 203 var optimalAlphabet = m_transitions
206 204 .GroupBy(t => Tuple.Create(statesMap[t.s1], statesMap[t.s2]), t => t.edge);
207 205
208 206 var alphabetMap = inputAlphabet.Reclassify(optimalInputAlphabet, optimalAlphabet);
209 207
210 208 var optimalTags = m_finalStates
211 .GroupBy(pair => statesMap[pair.Key])
209 .GroupBy(s => statesMap[s])
212 210 .ToDictionary(
213 211 g => g.Key,
214 g => g.SelectMany(pair => pair.Value).ToArray()
212 g => g.ToArray()
215 213 );
216 214
217 215 // построение автомата
218 216 optimalDFA.SetInitialState(statesMap[m_initialState]);
219 217
220 218 foreach (var pair in optimalTags)
221 219 optimalDFA.MarkFinalState(pair.Key, pair.Value);
222 220
223 221 foreach (var t in m_transitions.Select(t => new AutomatonTransition(statesMap[t.s1],statesMap[t.s2],alphabetMap[t.edge])).Distinct())
224 optimalDFA.DefineTransition(t.s1, t.s2, t.edge);
222 optimalDFA.Add(new AutomatonTransition(t.s1, t.s2, t.edge));
225 223
226 224 }
227 225
226 public void MarkFinalState(int state) {
227 throw new NotImplementedException();
228 }
229
230 public void Add(AutomatonTransition item) {
231 throw new NotImplementedException();
232 }
233
234 public void Clear() {
235 throw new NotImplementedException();
236 }
237
238 public bool Contains(AutomatonTransition item) {
239 throw new NotImplementedException();
240 }
241
242 public void CopyTo(AutomatonTransition[] array, int arrayIndex) {
243 throw new NotImplementedException();
244 }
245
246 public bool Remove(AutomatonTransition item) {
247 throw new NotImplementedException();
248 }
249
250 public int Count {
251 get {
252 throw new NotImplementedException();
253 }
254 }
255
256 public bool IsReadOnly {
257 get {
258 throw new NotImplementedException();
259 }
260 }
261
262 public IEnumerator<AutomatonTransition> GetEnumerator() {
263 throw new NotImplementedException();
264 }
265
266 System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() {
267 throw new NotImplementedException();
268 }
269
228 270 protected void PrintDFA<TInput, TState>(IAlphabet<TInput> inputAlphabet, IAlphabet<TState> stateAlphabet) {
229 271 Safe.ArgumentNotNull(inputAlphabet, "inputAlphabet");
230 272 Safe.ArgumentNotNull(stateAlphabet, "stateAlphabet");
231 273
232 274 var inputMap = inputAlphabet.CreateReverseMap();
233 275 var stateMap = stateAlphabet.CreateReverseMap();
234 276
235 277 for (int i = 0; i < inputMap.Length; i++)
236 278 Console.WriteLine("C{0}: {1}", i, String.Join(",", inputMap[i]));
237 279
238 280
239 281 foreach(var t in m_transitions)
240 282 Console.WriteLine(
241 283 "[{0}] -{{{1}}}-> [{2}]{3}",
242 284 stateMap[t.s1],
243 285 String.Join(",", inputMap[t.edge]),
244 286 stateMap[t.s2],
245 287 m_finalStates.ContainsKey(t.s2) ? "$" : ""
246 288 );
247 289
248 290 }
249 291
250 292 }
251 293 }
Show file before | Show file after | Hide comments
@@ -1,16 +1,15
1 1 using System;
2 2 using System.Collections.Generic;
3 3
4 4 namespace Implab.Automaton {
5 5 public interface IDFATableBuilder : IDFATable, ICollection<AutomatonTransition> {
6 6 /// <summary>
7 7 /// Marks the state as final.
8 8 /// </summary>
9 9 /// <param name="state">State.</param>
10 10 void MarkFinalState(int state);
11 11
12 12 void SetInitialState(int s);
13
14 13 }
15 14 }
16 15
General Comments 0
You need to be logged in to leave comments. Login now