Mercurial > pub > ImplabNet

comparison Implab/Automaton/DFATransitionTable.cs @ 164:ec35731ae299 ref20160224

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Almost complete DFA refactoring
author cin
date Thu, 25 Feb 2016 02:11:13 +0300
parents
children e227e78d72e4
comparison
equal deleted inserted replaced
163:419aa51b04fd 164:ec35731ae299
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 }