Mercurial > pub > ImplabNet

comparison Implab/Automaton/DFATable.cs @ 171:0f70905b4652 ref20160224

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Working on regular DFA
author cin
date Thu, 10 Mar 2016 01:19:33 +0300
parents 54270c2f29f2
children 92d5278d1b10
comparison
equal deleted inserted replaced
170:181119ef3b39 171:0f70905b4652
3 using System.Collections.Generic; 3 using System.Collections.Generic;
4 using System.Linq; 4 using System.Linq;
5 5
6 namespace Implab.Automaton { 6 namespace Implab.Automaton {
7 public class DFATable : IDFATableBuilder { 7 public class DFATable : IDFATableBuilder {
8 DFAStateDescriptior[] m_dfaTable;
9
10 int m_stateCount; 8 int m_stateCount;
11 int m_symbolCount; 9 int m_symbolCount;
12 int m_initialState; 10 int m_initialState;
13 11
14 readonly HashSet<int> m_finalStates = new HashSet<int>(); 12 readonly HashSet<int> m_finalStates = new HashSet<int>();
15 readonly HashSet<AutomatonTransition> m_transitions = new HashSet<AutomatonTransition>(); 13 readonly HashSet<AutomatonTransition> m_transitions = new HashSet<AutomatonTransition>();
16 14
17 void AssertNotReadOnly() {
18 if (m_dfaTable != null)
19 throw new InvalidOperationException("The object is readonly");
20 }
21
22 15
23 #region IDFADefinition implementation 16 #region IDFADefinition implementation
24
25 public DFAStateDescriptior[] GetTransitionTable() {
26 if (m_dfaTable == null) {
27 if (m_stateCount <= 0)
28 throw new InvalidOperationException("Invalid automaton definition: states count = {0}", m_stateCount);
29 if (m_symbolCount <= 0)
30 throw new InvalidOperationException("Invalid automaton definition: symbols count = {0}", m_symbolCount);
31
32 m_dfaTable = ConstructTransitionTable();
33 }
34 return m_dfaTable;
35 }
36 17
37 public bool IsFinalState(int s) { 18 public bool IsFinalState(int s) {
38 Safe.ArgumentInRange(s, 0, m_stateCount, "s"); 19 Safe.ArgumentInRange(s, 0, m_stateCount, "s");
39 20
40 return m_dfaTable != null ? m_dfaTable[s].final : m_finalStates.Contains(s); 21 return m_finalStates.Contains(s);
41 } 22 }
42 23
43 public IEnumerable<int> FinalStates { 24 public IEnumerable<int> FinalStates {
44 get { 25 get {
45 return m_finalStates; 26 return m_finalStates;
58 get { return m_initialState; } 39 get { return m_initialState; }
59 } 40 }
60 41
61 #endregion 42 #endregion
62 43
63 protected virtual DFAStateDescriptior[] ConstructTransitionTable() {
64 var dfaTable = new DFAStateDescriptior[m_stateCount];
65
66
67 foreach (var t in m_transitions) {
68 if (dfaTable[t.s1].transitions == null)
69 dfaTable[t.s1] = new DFAStateDescriptior(m_symbolCount, m_finalStates.Contains(t.s1));
70
71 dfaTable[t.s1].transitions[t.edge] = t.s2;
72 }
73
74 foreach (var s in m_finalStates)
75 if (!dfaTable[s].final)
76 m_dfaTable[s] = new DFAStateDescriptior(m_symbolCount, true);
77
78 }
79
80 public void SetInitialState(int s) { 44 public void SetInitialState(int s) {
81 Safe.ArgumentAssert(s >= 0, "s"); 45 Safe.ArgumentAssert(s >= 0, "s");
82 m_initialState = s; 46 m_initialState = s;
83 } 47 }
84 48
85 public void MarkFinalState(int state) { 49 public void MarkFinalState(int state) {
86 AssertNotReadOnly();
87 m_finalStates.Add(state); 50 m_finalStates.Add(state);
88 } 51 }
89 52
90 public void Add(AutomatonTransition item) { 53 public void Add(AutomatonTransition item) {
91 AssertNotReadOnly();
92 Safe.ArgumentAssert(item.s1 >= 0, "item"); 54 Safe.ArgumentAssert(item.s1 >= 0, "item");
93 Safe.ArgumentAssert(item.s2 >= 0, "item"); 55 Safe.ArgumentAssert(item.s2 >= 0, "item");
94 Safe.ArgumentAssert(item.edge >= 0, "item"); 56 Safe.ArgumentAssert(item.edge >= 0, "item");
95 57
96 m_stateCount = Math.Max(m_stateCount, Math.Max(item.s1, item.s2) + 1); 58 m_stateCount = Math.Max(m_stateCount, Math.Max(item.s1, item.s2) + 1);
98 60
99 m_transitions.Add(item); 61 m_transitions.Add(item);
100 } 62 }
101 63
102 public void Clear() { 64 public void Clear() {
103 AssertNotReadOnly();
104
105 m_stateCount = 0; 65 m_stateCount = 0;
106 m_symbolCount = 0; 66 m_symbolCount = 0;
107 m_finalStates.Clear(); 67 m_finalStates.Clear();
108 m_transitions.Clear(); 68 m_transitions.Clear();
109 } 69 }
115 public void CopyTo(AutomatonTransition[] array, int arrayIndex) { 75 public void CopyTo(AutomatonTransition[] array, int arrayIndex) {
116 m_transitions.CopyTo(array, arrayIndex); 76 m_transitions.CopyTo(array, arrayIndex);
117 } 77 }
118 78
119 public bool Remove(AutomatonTransition item) { 79 public bool Remove(AutomatonTransition item) {
120 AssertNotReadOnly();
121 m_transitions.Remove(item); 80 m_transitions.Remove(item);
122 } 81 }
123 82
124 public int Count { 83 public int Count {
125 get { 84 get {
127 } 86 }
128 } 87 }
129 88
130 public bool IsReadOnly { 89 public bool IsReadOnly {
131 get { 90 get {
132 return m_dfaTable != null; 91 return false;
133 } 92 }
134 } 93 }
135 94
136 public IEnumerator<AutomatonTransition> GetEnumerator() { 95 public IEnumerator<AutomatonTransition> GetEnumerator() {
137 return m_transitions.GetEnumerator(); 96 return m_transitions.GetEnumerator();
151 /// <returns>The final states.</returns> 110 /// <returns>The final states.</returns>
152 protected virtual IEnumerable<HashSet<int>> GroupFinalStates() { 111 protected virtual IEnumerable<HashSet<int>> GroupFinalStates() {
153 return new HashSet<int>[] { m_finalStates }; 112 return new HashSet<int>[] { m_finalStates };
154 } 113 }
155 114
156 protected void Optimize<TInput, TState>( 115 protected void Optimize(
157 IDFATableBuilder optimalDFA, 116 IDFATableBuilder optimalDFA,
158 IAlphabet<TInput> inputAlphabet, 117 IDictionary<int,int> alphabetMap,
159 IAlphabetBuilder<TInput> optimalInputAlphabet, 118 IDictionary<int,int> stateMap
160 IAlphabet<TState> stateAlphabet,
161 IAlphabetBuilder<TState> optimalStateAlphabet
162 ) { 119 ) {
163 Safe.ArgumentNotNull(optimalDFA, "dfa"); 120 Safe.ArgumentNotNull(optimalDFA, "dfa");
164 Safe.ArgumentNotNull(optimalInputAlphabet, "optimalInputAlphabet"); 121 Safe.ArgumentNotNull(alphabetMap, "alphabetMap");
165 Safe.ArgumentNotNull(optimalStateAlphabet, "optimalStateAlphabet"); 122 Safe.ArgumentNotNull(stateMap, "stateMap");
166 Safe.ArgumentNotNull(inputAlphabet, "inputAlphabet"); 123
167 Safe.ArgumentNotNull(stateAlphabet, "stateAlphabet");
168
169 if (inputAlphabet.Count != m_symbolCount)
170 throw new InvalidOperationException("The input symbols aphabet mismatch");
171 if (stateAlphabet.Count != m_stateCount)
172 throw new InvalidOperationException("The states alphabet mismatch");
173 124
174 var setComparer = new CustomEqualityComparer<HashSet<int>>( 125 var setComparer = new CustomEqualityComparer<HashSet<int>>(
175 (x, y) => x.SetEquals(y), 126 (x, y) => x.SetEquals(y),
176 s => s.Sum(x => x.GetHashCode()) 127 s => s.Sum(x => x.GetHashCode())
177 ); 128 );
232 } 183 }
233 } 184 }
234 } 185 }
235 186
236 // карта получения оптимального состояния по соотвествующему ему простому состоянию 187 // карта получения оптимального состояния по соотвествующему ему простому состоянию
237 var statesMap = stateAlphabet.Reclassify(optimalStateAlphabet, optimalStates); 188 var nextState = 0;
189 foreach (var item in optimalStates) {
190 var id = nextState++;
191 foreach (var s in item)
192 stateMap[s] = id;
193 }
238 194
239 // получаем минимальный алфавит 195 // получаем минимальный алфавит
240 // входные символы не различимы, если Move(s,a1) == Move(s,a2) 196 // входные символы не различимы, если Move(s,a1) == Move(s,a2), для любого s
241 var optimalAlphabet = m_transitions 197 // для этого используем алгоритм кластеризации, сначала
242 .GroupBy(t => Tuple.Create(statesMap[t.s1], statesMap[t.s2]), t => t.edge); 198 // считаем, что все символы не различимы
243 199
244 var alphabetMap = inputAlphabet.Reclassify(optimalInputAlphabet, optimalAlphabet); 200 var minClasses = new HashSet<HashSet<int>>(setComparer);
201 var alphaQueue = new Queue<HashSet<int>>();
202 alphaQueue.Enqueue(new HashSet<int>(Enumerable.Range(0,AlphabetSize)));
203
204 // для всех состояний, будем проверять каждый класс на различимость,
205 // т.е. символы различимы, если они приводят к разным состояниям
206 for (int s = 0 ; s < optimalStates.Count; s++) {
207 var newQueue = new Queue<HashSet<int>>();
208
209 foreach (var A in alphaQueue) {
210 // классы из одного символа делить бесполезно, переводим их сразу в
211 // результирующий алфавит
212 if (A.Count == 1) {
213 minClasses.Add(A);
214 continue;
215 }
216
217 // различаем классы символов, которые переводят в различные оптимальные состояния
218 // optimalState -> alphaClass
219 var classes = new Dictionary<int, HashSet<int>>();
220
221 foreach (var term in A) {
222 // ищем все переходы класса по символу term
223 var res = m_transitions.Where(t => stateMap[t.s1] == s && t.edge == term).Select(t => stateMap[t.s2]).ToArray();
224
225 var s2 = res.Length > 0 ? res[0] : -1;
226
227 HashSet<int> a2;
228 if (!classes.TryGetValue(s2, out a2)) {
229 a2 = new HashSet<int>();
230 newQueue.Enqueue(a2);
231 classes[s2] = a2;
232 }
233 a2.Add(term);
234 }
235 }
236
237 if (newQueue.Count == 0)
238 break;
239 alphaQueue = newQueue;
240 }
241
242 // после окончания работы алгоритма в очереди останутся минимальные различимые классы
243 // входных символов
244 foreach (var A in alphaQueue)
245 minClasses.Add(A);
246
247 // построение отображения алфавитов входных символов.
248 // поскольку символ DFAConst.UNCLASSIFIED_INPUT может иметь
249 // специальное значение, тогда сохраним минимальный класс,
250 // содержащий этот символ на томже месте.
251
252 var nextCls = 0;
253 foreach (var item in minClasses) {
254 if (nextCls == DFAConst.UNCLASSIFIED_INPUT)
255 nextCls++;
256
257 // сохраняем DFAConst.UNCLASSIFIED_INPUT
258 var cls = item.Contains(DFAConst.UNCLASSIFIED_INPUT) ? DFAConst.UNCLASSIFIED_INPUT : nextCls;
259
260 foreach (var a in item)
261 alphabetMap[a] = cls;
262
263 nextCls++;
264 }
245 265
246 // построение автомата 266 // построение автомата
247 optimalDFA.SetInitialState(statesMap[m_initialState]); 267 optimalDFA.SetInitialState(stateMap[m_initialState]);
248 268
249 foreach (var sf in m_finalStates.GroupBy(s => statesMap[s])) 269 foreach (var sf in m_finalStates.Select(s => stateMap[s]).Distinct())
250 optimalDFA.MarkFinalState(sf.Key); 270 optimalDFA.MarkFinalState(sf);
251 271
252 foreach (var t in m_transitions.Select(t => new AutomatonTransition(statesMap[t.s1],statesMap[t.s2],alphabetMap[t.edge])).Distinct()) 272 foreach (var t in m_transitions.Select(t => new AutomatonTransition(stateMap[t.s1],stateMap[t.s2],alphabetMap[t.edge])).Distinct())
253 optimalDFA.Add(t); 273 optimalDFA.Add(t);
254
255 } 274 }
256 275
257 protected void PrintDFA<TInput, TState>(IAlphabet<TInput> inputAlphabet, IAlphabet<TState> stateAlphabet) { 276 protected void PrintDFA<TInput, TState>(IAlphabet<TInput> inputAlphabet, IAlphabet<TState> stateAlphabet) {
258 Safe.ArgumentNotNull(inputAlphabet, "inputAlphabet"); 277 Safe.ArgumentNotNull(inputAlphabet, "inputAlphabet");
259 Safe.ArgumentNotNull(stateAlphabet, "stateAlphabet"); 278 Safe.ArgumentNotNull(stateAlphabet, "stateAlphabet");
260 279
261 var inputMap = inputAlphabet.CreateReverseMap();
262 var stateMap = stateAlphabet.CreateReverseMap();
263
264 for (int i = 0; i < inputMap.Length; i++)
265 Console.WriteLine("C{0}: {1}", i, String.Join(",", inputMap[i]));
266
267
268 foreach(var t in m_transitions) 280 foreach(var t in m_transitions)
269 Console.WriteLine( 281 Console.WriteLine(
270 "[{0}] -{{{1}}}-> [{2}]{3}", 282 "[{0}] -{{{1}}}-> [{2}]{3}",
271 stateMap[t.s1], 283 String.Join(",", stateAlphabet.GetSymbols(t.s1)),
272 String.Join(",", inputMap[t.edge]), 284 String.Join("", inputAlphabet.GetSymbols(t.edge)),
273 stateMap[t.s2], 285 String.Join(",", stateAlphabet.GetSymbols(t.s2)),
274 m_finalStates.Contains(t.s2) ? "$" : "" 286 m_finalStates.Contains(t.s2) ? "$" : ""
275 ); 287 );
276
277 } 288 }
278 289
279 } 290 }
280 } 291 }