annotate Implab/Automaton/DFATransitionTable.cs @ 165:e227e78d72e4 ref20160224

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