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