|
176
|
1 using Implab;
|
|
|
2 using System;
|
|
|
3 using System.Collections.Generic;
|
|
|
4 using System.Linq;
|
|
181
|
5 using System.Diagnostics;
|
|
182
|
6 using System.IO;
|
|
|
7 using System.CodeDom.Compiler;
|
|
|
8 using System.CodeDom;
|
|
176
|
9
|
|
|
10 namespace Implab.Automaton {
|
|
|
11 public class DFATable : IDFATableBuilder {
|
|
|
12 int m_stateCount;
|
|
|
13 int m_symbolCount;
|
|
|
14 int m_initialState;
|
|
|
15
|
|
|
16 readonly HashSet<int> m_finalStates = new HashSet<int>();
|
|
|
17 readonly HashSet<AutomatonTransition> m_transitions = new HashSet<AutomatonTransition>();
|
|
|
18
|
|
|
19
|
|
|
20 #region IDFADefinition implementation
|
|
|
21
|
|
|
22 public bool IsFinalState(int s) {
|
|
|
23 Safe.ArgumentInRange(s, 0, m_stateCount, "s");
|
|
|
24
|
|
|
25 return m_finalStates.Contains(s);
|
|
|
26 }
|
|
|
27
|
|
|
28 public IEnumerable<int> FinalStates {
|
|
|
29 get {
|
|
|
30 return m_finalStates;
|
|
|
31 }
|
|
|
32 }
|
|
|
33
|
|
|
34 public int StateCount {
|
|
|
35 get { return m_stateCount; }
|
|
|
36 }
|
|
|
37
|
|
|
38 public int AlphabetSize {
|
|
|
39 get { return m_symbolCount; }
|
|
|
40 }
|
|
|
41
|
|
|
42 public int InitialState {
|
|
|
43 get { return m_initialState; }
|
|
|
44 }
|
|
|
45
|
|
|
46 #endregion
|
|
|
47
|
|
|
48 public void SetInitialState(int s) {
|
|
|
49 Safe.ArgumentAssert(s >= 0, "s");
|
|
181
|
50 m_stateCount = Math.Max(m_stateCount, s + 1);
|
|
176
|
51 m_initialState = s;
|
|
|
52 }
|
|
|
53
|
|
|
54 public void MarkFinalState(int state) {
|
|
181
|
55 m_stateCount = Math.Max(m_stateCount, state + 1);
|
|
176
|
56 m_finalStates.Add(state);
|
|
|
57 }
|
|
|
58
|
|
|
59 public void Add(AutomatonTransition item) {
|
|
|
60 Safe.ArgumentAssert(item.s1 >= 0, "item");
|
|
|
61 Safe.ArgumentAssert(item.s2 >= 0, "item");
|
|
|
62 Safe.ArgumentAssert(item.edge >= 0, "item");
|
|
|
63
|
|
|
64 m_stateCount = Math.Max(m_stateCount, Math.Max(item.s1, item.s2) + 1);
|
|
181
|
65 m_symbolCount = Math.Max(m_symbolCount, item.edge + 1);
|
|
176
|
66
|
|
|
67 m_transitions.Add(item);
|
|
|
68 }
|
|
|
69
|
|
|
70 public void Clear() {
|
|
|
71 m_stateCount = 0;
|
|
|
72 m_symbolCount = 0;
|
|
|
73 m_finalStates.Clear();
|
|
|
74 m_transitions.Clear();
|
|
|
75 }
|
|
|
76
|
|
|
77 public bool Contains(AutomatonTransition item) {
|
|
|
78 return m_transitions.Contains(item);
|
|
|
79 }
|
|
|
80
|
|
|
81 public void CopyTo(AutomatonTransition[] array, int arrayIndex) {
|
|
|
82 m_transitions.CopyTo(array, arrayIndex);
|
|
|
83 }
|
|
|
84
|
|
|
85 public bool Remove(AutomatonTransition item) {
|
|
180
|
86 return m_transitions.Remove(item);
|
|
176
|
87 }
|
|
|
88
|
|
|
89 public int Count {
|
|
|
90 get {
|
|
|
91 return m_transitions.Count;
|
|
|
92 }
|
|
|
93 }
|
|
|
94
|
|
|
95 public bool IsReadOnly {
|
|
|
96 get {
|
|
|
97 return false;
|
|
|
98 }
|
|
|
99 }
|
|
|
100
|
|
|
101 public IEnumerator<AutomatonTransition> GetEnumerator() {
|
|
|
102 return m_transitions.GetEnumerator();
|
|
|
103 }
|
|
|
104
|
|
|
105 System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() {
|
|
|
106 return GetEnumerator();
|
|
|
107 }
|
|
|
108
|
|
182
|
109 public void AddSymbol(int symbol) {
|
|
|
110 Safe.ArgumentAssert(symbol >= 0, "symbol");
|
|
|
111 m_symbolCount = Math.Max(symbol + 1, m_symbolCount);
|
|
|
112 }
|
|
|
113
|
|
176
|
114 public int[,] CreateTransitionTable() {
|
|
|
115 var table = new int[StateCount,AlphabetSize];
|
|
|
116
|
|
|
117 for (int i = 0; i < StateCount; i++)
|
|
181
|
118 for (int j = 0; j < AlphabetSize; j++)
|
|
178
|
119 table[i, j] = AutomatonConst.UNREACHABLE_STATE;
|
|
176
|
120
|
|
|
121 foreach (var t in this)
|
|
|
122 table[t.s1,t.edge] = t.s2;
|
|
|
123
|
|
|
124 return table;
|
|
|
125 }
|
|
|
126
|
|
|
127 public bool[] CreateFinalStateTable() {
|
|
|
128 var table = new bool[StateCount];
|
|
|
129
|
|
|
130 foreach (var s in FinalStates)
|
|
|
131 table[s] = true;
|
|
|
132
|
|
|
133 return table;
|
|
|
134 }
|
|
|
135
|
|
|
136 /// <summary>Формирует множества конечных состояний перед началом работы алгоритма минимизации.</summary>
|
|
|
137 /// <remarks>
|
|
|
138 /// В процессе построения минимального автомата требуется разделить множество состояний,
|
|
|
139 /// на два подмножества - конечные состояния и все остальные, после чего эти подмножества
|
|
|
140 /// будут резделены на более мелкие. Иногда требуется гарантировать различия конечных сосотяний,
|
|
|
141 /// для этого необходимо переопределить даннцю фукнцию, для получения множеств конечных состояний.
|
|
|
142 /// </remarks>
|
|
|
143 /// <returns>The final states.</returns>
|
|
|
144 protected virtual IEnumerable<HashSet<int>> GroupFinalStates() {
|
|
|
145 return new HashSet<int>[] { m_finalStates };
|
|
|
146 }
|
|
|
147
|
|
|
148 protected void Optimize(
|
|
|
149 IDFATableBuilder optimalDFA,
|
|
|
150 IDictionary<int,int> alphabetMap,
|
|
|
151 IDictionary<int,int> stateMap
|
|
|
152 ) {
|
|
|
153 Safe.ArgumentNotNull(optimalDFA, "dfa");
|
|
|
154 Safe.ArgumentNotNull(alphabetMap, "alphabetMap");
|
|
|
155 Safe.ArgumentNotNull(stateMap, "stateMap");
|
|
|
156
|
|
|
157
|
|
|
158 var setComparer = new CustomEqualityComparer<HashSet<int>>(
|
|
|
159 (x, y) => x.SetEquals(y),
|
|
|
160 s => s.Sum(x => x.GetHashCode())
|
|
|
161 );
|
|
|
162
|
|
|
163 var optimalStates = new HashSet<HashSet<int>>(setComparer);
|
|
|
164 var queue = new HashSet<HashSet<int>>(setComparer);
|
|
|
165
|
|
|
166 // получаем конечные состояния, сгруппированные по маркерам
|
|
|
167 optimalStates.UnionWith(
|
|
|
168 GroupFinalStates()
|
|
|
169 );
|
|
|
170
|
|
|
171 var state = new HashSet<int>(
|
|
|
172 Enumerable
|
|
182
|
173 .Range(0, m_stateCount)
|
|
176
|
174 .Where(i => !m_finalStates.Contains(i))
|
|
|
175 );
|
|
|
176
|
|
|
177 optimalStates.Add(state);
|
|
|
178 queue.Add(state);
|
|
|
179
|
|
|
180 var rmap = m_transitions
|
|
|
181 .GroupBy(t => t.s2)
|
|
180
|
182 .ToDictionary(
|
|
176
|
183 g => g.Key, // s2
|
|
181
|
184 g => g.ToLookup(t => t.edge, t => t.s1)//.ToDictionary(p => p.Key)
|
|
176
|
185 );
|
|
|
186
|
|
|
187 while (queue.Count > 0) {
|
|
|
188 var stateA = queue.First();
|
|
|
189 queue.Remove(stateA);
|
|
|
190
|
|
|
191 for (int c = 0; c < m_symbolCount; c++) {
|
|
|
192 var stateX = new HashSet<int>();
|
|
182
|
193 //foreach(var a in stateA.Where(rmap.ContainsKey))
|
|
|
194 // stateX.UnionWith(rmap[a][c]); // all states from wich the symbol 'c' leads to the state 'a'
|
|
176
|
195
|
|
182
|
196 stateX.UnionWith(m_transitions.Where(t => stateA.Contains(t.s2) && t.edge == c).Select(t => t.s1));
|
|
|
197
|
|
|
198 var tmp = optimalStates.ToArray();
|
|
|
199 foreach (var stateY in tmp) {
|
|
176
|
200 if (stateX.Overlaps(stateY) && !stateY.IsSubsetOf(stateX)) {
|
|
|
201 var stateR1 = new HashSet<int>(stateY);
|
|
|
202 var stateR2 = new HashSet<int>(stateY);
|
|
|
203
|
|
|
204 stateR1.IntersectWith(stateX);
|
|
|
205 stateR2.ExceptWith(stateX);
|
|
|
206
|
|
|
207 optimalStates.Remove(stateY);
|
|
|
208 optimalStates.Add(stateR1);
|
|
|
209 optimalStates.Add(stateR2);
|
|
|
210
|
|
|
211 if (queue.Contains(stateY)) {
|
|
|
212 queue.Remove(stateY);
|
|
|
213 queue.Add(stateR1);
|
|
|
214 queue.Add(stateR2);
|
|
|
215 } else {
|
|
|
216 queue.Add(stateR1.Count <= stateR2.Count ? stateR1 : stateR2);
|
|
|
217 }
|
|
|
218 }
|
|
|
219 }
|
|
|
220 }
|
|
|
221 }
|
|
|
222
|
|
|
223 // карта получения оптимального состояния по соотвествующему ему простому состоянию
|
|
|
224 var nextState = 0;
|
|
|
225 foreach (var item in optimalStates) {
|
|
|
226 var id = nextState++;
|
|
|
227 foreach (var s in item)
|
|
|
228 stateMap[s] = id;
|
|
|
229 }
|
|
|
230
|
|
|
231 // получаем минимальный алфавит
|
|
|
232 // входные символы не различимы, если Move(s,a1) == Move(s,a2), для любого s
|
|
|
233 // для этого используем алгоритм кластеризации, сначала
|
|
|
234 // считаем, что все символы не различимы
|
|
|
235
|
|
|
236 var minClasses = new HashSet<HashSet<int>>(setComparer);
|
|
|
237 var alphaQueue = new Queue<HashSet<int>>();
|
|
|
238 alphaQueue.Enqueue(new HashSet<int>(Enumerable.Range(0,AlphabetSize)));
|
|
|
239
|
|
|
240 // для всех состояний, будем проверять каждый класс на различимость,
|
|
|
241 // т.е. символы различимы, если они приводят к разным состояниям
|
|
|
242 for (int s = 0 ; s < optimalStates.Count; s++) {
|
|
|
243 var newQueue = new Queue<HashSet<int>>();
|
|
|
244
|
|
|
245 foreach (var A in alphaQueue) {
|
|
|
246 // классы из одного символа делить бесполезно, переводим их сразу в
|
|
|
247 // результирующий алфавит
|
|
|
248 if (A.Count == 1) {
|
|
|
249 minClasses.Add(A);
|
|
|
250 continue;
|
|
|
251 }
|
|
|
252
|
|
|
253 // различаем классы символов, которые переводят в различные оптимальные состояния
|
|
|
254 // optimalState -> alphaClass
|
|
|
255 var classes = new Dictionary<int, HashSet<int>>();
|
|
|
256
|
|
|
257 foreach (var term in A) {
|
|
|
258 // ищем все переходы класса по символу term
|
|
182
|
259 var s2 = m_transitions.Where(t => stateMap[t.s1] == s && t.edge == term).Select(t => stateMap[t.s2]).DefaultIfEmpty(-1).First();
|
|
176
|
260
|
|
|
261 HashSet<int> a2;
|
|
|
262 if (!classes.TryGetValue(s2, out a2)) {
|
|
|
263 a2 = new HashSet<int>();
|
|
|
264 newQueue.Enqueue(a2);
|
|
|
265 classes[s2] = a2;
|
|
|
266 }
|
|
|
267 a2.Add(term);
|
|
|
268 }
|
|
|
269 }
|
|
|
270
|
|
|
271 if (newQueue.Count == 0)
|
|
|
272 break;
|
|
|
273 alphaQueue = newQueue;
|
|
|
274 }
|
|
|
275
|
|
|
276 // после окончания работы алгоритма в очереди останутся минимальные различимые классы
|
|
|
277 // входных символов
|
|
|
278 foreach (var A in alphaQueue)
|
|
|
279 minClasses.Add(A);
|
|
|
280
|
|
|
281 // построение отображения алфавитов входных символов.
|
|
|
282 // поскольку символ DFAConst.UNCLASSIFIED_INPUT может иметь
|
|
|
283 // специальное значение, тогда сохраним минимальный класс,
|
|
|
284 // содержащий этот символ на томже месте.
|
|
|
285
|
|
|
286 var nextCls = 0;
|
|
|
287 foreach (var item in minClasses) {
|
|
178
|
288 if (nextCls == AutomatonConst.UNCLASSIFIED_INPUT)
|
|
176
|
289 nextCls++;
|
|
|
290
|
|
|
291 // сохраняем DFAConst.UNCLASSIFIED_INPUT
|
|
181
|
292 var cls = item.Contains(AutomatonConst.UNCLASSIFIED_INPUT) ? AutomatonConst.UNCLASSIFIED_INPUT : nextCls++;
|
|
182
|
293 optimalDFA.AddSymbol(cls);
|
|
176
|
294
|
|
|
295 foreach (var a in item)
|
|
|
296 alphabetMap[a] = cls;
|
|
|
297 }
|
|
|
298
|
|
|
299 // построение автомата
|
|
|
300 optimalDFA.SetInitialState(stateMap[m_initialState]);
|
|
|
301
|
|
|
302 foreach (var sf in m_finalStates.Select(s => stateMap[s]).Distinct())
|
|
|
303 optimalDFA.MarkFinalState(sf);
|
|
|
304
|
|
|
305 foreach (var t in m_transitions.Select(t => new AutomatonTransition(stateMap[t.s1],stateMap[t.s2],alphabetMap[t.edge])).Distinct())
|
|
|
306 optimalDFA.Add(t);
|
|
|
307 }
|
|
|
308
|
|
182
|
309 protected string PrintDFA<TInput, TState>(IAlphabet<TInput> inputAlphabet, IAlphabet<TState> stateAlphabet) {
|
|
176
|
310 Safe.ArgumentNotNull(inputAlphabet, "inputAlphabet");
|
|
|
311 Safe.ArgumentNotNull(stateAlphabet, "stateAlphabet");
|
|
|
312
|
|
182
|
313 var data = new List<string>();
|
|
|
314
|
|
|
315 data.Add("digraph dfa {");
|
|
|
316
|
|
|
317 foreach (var final in m_finalStates)
|
|
|
318 data.Add(String.Format("{0} [shape=box];",String.Join("", stateAlphabet.GetSymbols(final))));
|
|
|
319
|
|
|
320 foreach (var t in m_transitions)
|
|
|
321 data.Add(String.Format(
|
|
|
322 "{0} -> {2} [label={1}];",
|
|
|
323 String.Join("", stateAlphabet.GetSymbols(t.s1)),
|
|
|
324 ToLiteral(ToLiteral(String.Join("", t.edge == AutomatonConst.UNCLASSIFIED_INPUT ? new [] { "@" } : inputAlphabet.GetSymbols(t.edge).Select(x => x.ToString())))),
|
|
|
325 String.Join("", stateAlphabet.GetSymbols(t.s2))
|
|
|
326 ));
|
|
|
327 data.Add("}");
|
|
|
328 return String.Join("\n", data);
|
|
176
|
329 }
|
|
|
330
|
|
182
|
331 static string ToLiteral(string input)
|
|
|
332 {
|
|
|
333 using (var writer = new StringWriter())
|
|
|
334 {
|
|
|
335 using (var provider = CodeDomProvider.CreateProvider("CSharp"))
|
|
|
336 {
|
|
|
337 provider.GenerateCodeFromExpression(new CodePrimitiveExpression(input), writer, null);
|
|
|
338 return writer.ToString();
|
|
|
339 }
|
|
|
340 }
|
|
|
341 }
|
|
176
|
342 }
|
|
|
343 }
|
