##// END OF EJS Templates
implab » ImplabNet
RSS
sync
cin -
r168:8fb9c9507a26 ref20160224
parent child
Show More
Show file before | Show file after | Hide comments
@@ -53,27 +53,31 namespace Implab.Automaton {
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
@@ -107,8 +111,12 namespace Implab.Automaton {
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,
@@ -130,30 +138,20 namespace Implab.Automaton {
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
@@ -208,10 +206,10 namespace Implab.Automaton {
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 // построение автомата
@@ -221,8 +219,52 namespace Implab.Automaton {
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) {
Show file before | Show file after | Hide comments
@@ -10,7 +10,6 namespace Implab.Automaton {
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