|
164
|
1 using Implab;
|
|
|
2 using System;
|
|
|
3 using System.Collections.Generic;
|
|
|
4 using System.Linq;
|
|
|
5
|
|
|
6 namespace Implab.Automaton {
|
|
|
7 public class DFATransitionTable<TTag> : IDFATransitionTableBuilder<TTag> {
|
|
|
8 DFAStateDescriptior<TTag>[] m_dfaTable;
|
|
|
9
|
|
|
10 int m_stateCount;
|
|
|
11 int m_symbolCount;
|
|
|
12 int m_initialState;
|
|
|
13
|
|
|
14 readonly Dictionary<int, TTag[]> m_finalStates = new Dictionary<int, TTag[]>();
|
|
|
15 readonly HashSet<AutomatonTransition> m_transitions = new HashSet<AutomatonTransition>();
|
|
|
16
|
|
|
17
|
|
|
18 #region IDFADefinition implementation
|
|
|
19
|
|
|
20 public DFAStateDescriptior<TTag>[] GetTransitionTable() {
|
|
|
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
|
|
|
35 return m_finalStates.ContainsKey(s);
|
|
|
36 }
|
|
|
37
|
|
|
38 public IEnumerable<KeyValuePair<int,TTag[]>> FinalStates {
|
|
|
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
|
|
|
56 #endregion
|
|
|
57
|
|
|
58 protected virtual DFAStateDescriptior<TTag>[] ConstructTransitionTable() {
|
|
|
59 var dfaTable = new DFAStateDescriptior<TTag>[m_stateCount];
|
|
|
60
|
|
|
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
|
|
|
68 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
|
|
|
75 dfaTable[t.s1].transitions[t.edge] = t.s2;
|
|
|
76 }
|
|
|
77 }
|
|
|
78
|
|
|
79 #region IDFADefinitionBuilder
|
|
|
80
|
|
|
81 public void DefineTransition(int s1, int s2, int symbol) {
|
|
|
82 if (m_dfaTable != null)
|
|
|
83 throw new InvalidOperationException("The transition table is already built");
|
|
|
84
|
|
|
85 Safe.ArgumentAssert(s1 > 0, "s1");
|
|
|
86 Safe.ArgumentAssert(s2 > 0, "s2");
|
|
|
87 Safe.ArgumentAssert(symbol >= 0, "symbol");
|
|
|
88
|
|
|
89 m_stateCount = Math.Max(Math.Max(m_stateCount, s1 + 1), s2 + 1);
|
|
|
90 m_symbolCount = Math.Max(m_symbolCount, symbol + 1);
|
|
|
91
|
|
|
92 m_transitions.Add(new AutomatonTransition(s1, s2, symbol));
|
|
|
93 }
|
|
|
94
|
|
|
95 public void MarkFinalState(int state, params TTag[] tags) {
|
|
|
96 if (m_dfaTable != null)
|
|
|
97 throw new InvalidOperationException("The transition table is already built");
|
|
|
98
|
|
|
99 m_finalStates[state] = tags;
|
|
|
100 }
|
|
|
101
|
|
|
102 public void SetInitialState(int s) {
|
|
|
103 Safe.ArgumentAssert(s >= 0, "s");
|
|
|
104 m_initialState = s;
|
|
|
105 }
|
|
|
106
|
|
|
107
|
|
|
108 #endregion
|
|
|
109
|
|
|
110 protected void Optimize<TInput, TState>(
|
|
|
111 IDFATransitionTableBuilder<TTag> optimalDFA,
|
|
|
112 IAlphabet<TInput> inputAlphabet,
|
|
|
113 IAlphabetBuilder<TInput> optimalInputAlphabet,
|
|
|
114 IAlphabet<TState> stateAlphabet,
|
|
|
115 IAlphabetBuilder<TState> optimalStateAlphabet
|
|
|
116 ) {
|
|
|
117 Safe.ArgumentNotNull(optimalDFA, "dfa");
|
|
|
118 Safe.ArgumentNotNull(optimalInputAlphabet, "optimalInputAlphabet");
|
|
|
119 Safe.ArgumentNotNull(optimalStateAlphabet, "optimalStateAlphabet");
|
|
|
120 Safe.ArgumentNotNull(inputAlphabet, "inputAlphabet");
|
|
|
121 Safe.ArgumentNotNull(stateAlphabet, "stateAlphabet");
|
|
|
122
|
|
|
123 if (inputAlphabet.Count != m_symbolCount)
|
|
|
124 throw new InvalidOperationException("The input symbols aphabet mismatch");
|
|
|
125 if (stateAlphabet.Count != m_stateCount)
|
|
|
126 throw new InvalidOperationException("The states alphabet mismatch");
|
|
|
127
|
|
|
128 var setComparer = new CustomEqualityComparer<HashSet<int>>(
|
|
|
129 (x, y) => x.SetEquals(y),
|
|
|
130 s => s.Sum(x => x.GetHashCode())
|
|
|
131 );
|
|
|
132
|
|
|
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 var optimalStates = new HashSet<HashSet<int>>(setComparer);
|
|
|
139 var queue = new HashSet<HashSet<int>>(setComparer);
|
|
|
140
|
|
|
141 // получаем конечные состояния, сгруппированные по маркерам
|
|
|
142 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 )
|
|
|
150 );
|
|
|
151
|
|
|
152 var state = new HashSet<int>(
|
|
|
153 Enumerable
|
|
|
154 .Range(0, m_stateCount - 1)
|
|
|
155 .Where(i => !m_finalStates.ContainsKey(i))
|
|
|
156 );
|
|
|
157 optimalStates.Add(state);
|
|
|
158 queue.Add(state);
|
|
|
159
|
|
|
160 var rmap = m_transitions
|
|
|
161 .GroupBy(t => t.s2)
|
|
|
162 .ToLookup(
|
|
|
163 g => g.Key, // s2
|
|
|
164 g => g.ToLookup(t => t.edge, t => t.s1)
|
|
|
165 );
|
|
|
166
|
|
|
167 while (queue.Count > 0) {
|
|
|
168 var stateA = queue.First();
|
|
|
169 queue.Remove(stateA);
|
|
|
170
|
|
|
171 for (int c = 0; c < m_symbolCount; c++) {
|
|
|
172 var stateX = new HashSet<int>();
|
|
|
173 foreach(var a in stateA)
|
|
|
174 stateX.UnionWith(rmap[a][c]); // all states from wich 'c' leads to 'a'
|
|
|
175
|
|
|
176 foreach (var stateY in optimalStates.ToArray()) {
|
|
|
177 if (stateX.Overlaps(stateY) && !stateY.IsSubsetOf(stateX)) {
|
|
|
178 var stateR1 = new HashSet<int>(stateY);
|
|
|
179 var stateR2 = new HashSet<int>(stateY);
|
|
|
180
|
|
|
181 stateR1.IntersectWith(stateX);
|
|
|
182 stateR2.ExceptWith(stateX);
|
|
|
183
|
|
|
184 optimalStates.Remove(stateY);
|
|
|
185 optimalStates.Add(stateR1);
|
|
|
186 optimalStates.Add(stateR2);
|
|
|
187
|
|
|
188 if (queue.Contains(stateY)) {
|
|
|
189 queue.Remove(stateY);
|
|
|
190 queue.Add(stateR1);
|
|
|
191 queue.Add(stateR2);
|
|
|
192 } else {
|
|
|
193 queue.Add(stateR1.Count <= stateR2.Count ? stateR1 : stateR2);
|
|
|
194 }
|
|
|
195 }
|
|
|
196 }
|
|
|
197 }
|
|
|
198 }
|
|
|
199
|
|
|
200 // карта получения оптимального состояния по соотвествующему ему простому состоянию
|
|
|
201 var statesMap = stateAlphabet.Reclassify(optimalStateAlphabet, optimalStates);
|
|
|
202
|
|
|
203 // получаем минимальный алфавит
|
|
|
204 // входные символы не различимы, если Move(s,a1) == Move(s,a2)
|
|
|
205 var optimalAlphabet = m_transitions
|
|
|
206 .GroupBy(t => Tuple.Create(statesMap[t.s1], statesMap[t.s2]), t => t.edge);
|
|
|
207
|
|
|
208 var alphabetMap = inputAlphabet.Reclassify(optimalInputAlphabet, optimalAlphabet);
|
|
|
209
|
|
|
210 var optimalTags = m_finalStates
|
|
|
211 .GroupBy(pair => statesMap[pair.Key])
|
|
|
212 .ToDictionary(
|
|
|
213 g => g.Key,
|
|
|
214 g => g.SelectMany(pair => pair.Value).ToArray()
|
|
|
215 );
|
|
|
216
|
|
|
217 // построение автомата
|
|
|
218 optimalDFA.SetInitialState(statesMap[m_initialState]);
|
|
|
219
|
|
|
220 foreach (var pair in optimalTags)
|
|
|
221 optimalDFA.MarkFinalState(pair.Key, pair.Value);
|
|
|
222
|
|
|
223 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);
|
|
|
225
|
|
|
226 }
|
|
|
227
|
|
|
228 protected void PrintDFA<TInput, TState>(IAlphabet<TInput> inputAlphabet, IAlphabet<TState> stateAlphabet) {
|
|
|
229 Safe.ArgumentNotNull(inputAlphabet, "inputAlphabet");
|
|
|
230 Safe.ArgumentNotNull(stateAlphabet, "stateAlphabet");
|
|
|
231
|
|
|
232 var inputMap = inputAlphabet.CreateReverseMap();
|
|
|
233 var stateMap = stateAlphabet.CreateReverseMap();
|
|
|
234
|
|
|
235 for (int i = 0; i < inputMap.Length; i++)
|
|
|
236 Console.WriteLine("C{0}: {1}", i, String.Join(",", inputMap[i]));
|
|
|
237
|
|
|
238
|
|
|
239 foreach(var t in m_transitions)
|
|
|
240 Console.WriteLine(
|
|
|
241 "[{0}] -{{{1}}}-> [{2}]{3}",
|
|
|
242 stateMap[t.s1],
|
|
|
243 String.Join(",", inputMap[t.edge]),
|
|
|
244 stateMap[t.s2],
|
|
|
245 m_finalStates.ContainsKey(t.s2) ? "$" : ""
|
|
|
246 );
|
|
|
247
|
|
|
248 }
|
|
|
249
|
|
|
250 }
|
|
|
251 }
|
