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