Mercurial > pub > ImplabNet

comparison Implab/Automaton/DFATable.cs @ 169:54270c2f29f2 ref20160224

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
DFA refactoring
author cin
date Thu, 03 Mar 2016 08:41:02 +0300
parents
children 0f70905b4652
comparison
equal deleted inserted replaced
168:8fb9c9507a26 169:54270c2f29f2
1 using Implab;
2 using System;
3 using System.Collections.Generic;
4 using System.Linq;
5
6 namespace Implab.Automaton {
7 public class DFATable : IDFATableBuilder {
8 DFAStateDescriptior[] m_dfaTable;
9
10 int m_stateCount;
11 int m_symbolCount;
12 int m_initialState;
13
14 readonly HashSet<int> m_finalStates = new HashSet<int>();
15 readonly HashSet<AutomatonTransition> m_transitions = new HashSet<AutomatonTransition>();
16
17 void AssertNotReadOnly() {
18 if (m_dfaTable != null)
19 throw new InvalidOperationException("The object is readonly");
20 }
21
22
23 #region IDFADefinition implementation
24
25 public DFAStateDescriptior[] GetTransitionTable() {
26 if (m_dfaTable == null) {
27 if (m_stateCount <= 0)
28 throw new InvalidOperationException("Invalid automaton definition: states count = {0}", m_stateCount);
29 if (m_symbolCount <= 0)
30 throw new InvalidOperationException("Invalid automaton definition: symbols count = {0}", m_symbolCount);
31
32 m_dfaTable = ConstructTransitionTable();
33 }
34 return m_dfaTable;
35 }
36
37 public bool IsFinalState(int s) {
38 Safe.ArgumentInRange(s, 0, m_stateCount, "s");
39
40 return m_dfaTable != null ? m_dfaTable[s].final : m_finalStates.Contains(s);
41 }
42
43 public IEnumerable<int> FinalStates {
44 get {
45 return m_finalStates;
46 }
47 }
48
49 public int StateCount {
50 get { return m_stateCount; }
51 }
52
53 public int AlphabetSize {
54 get { return m_symbolCount; }
55 }
56
57 public int InitialState {
58 get { return m_initialState; }
59 }
60
61 #endregion
62
63 protected virtual DFAStateDescriptior[] ConstructTransitionTable() {
64 var dfaTable = new DFAStateDescriptior[m_stateCount];
65
66
67 foreach (var t in m_transitions) {
68 if (dfaTable[t.s1].transitions == null)
69 dfaTable[t.s1] = new DFAStateDescriptior(m_symbolCount, m_finalStates.Contains(t.s1));
70
71 dfaTable[t.s1].transitions[t.edge] = t.s2;
72 }
73
74 foreach (var s in m_finalStates)
75 if (!dfaTable[s].final)
76 m_dfaTable[s] = new DFAStateDescriptior(m_symbolCount, true);
77
78 }
79
80 public void SetInitialState(int s) {
81 Safe.ArgumentAssert(s >= 0, "s");
82 m_initialState = s;
83 }
84
85 public void MarkFinalState(int state) {
86 AssertNotReadOnly();
87 m_finalStates.Add(state);
88 }
89
90 public void Add(AutomatonTransition item) {
91 AssertNotReadOnly();
92 Safe.ArgumentAssert(item.s1 >= 0, "item");
93 Safe.ArgumentAssert(item.s2 >= 0, "item");
94 Safe.ArgumentAssert(item.edge >= 0, "item");
95
96 m_stateCount = Math.Max(m_stateCount, Math.Max(item.s1, item.s2) + 1);
97 m_symbolCount = Math.Max(m_symbolCount, item.edge);
98
99 m_transitions.Add(item);
100 }
101
102 public void Clear() {
103 AssertNotReadOnly();
104
105 m_stateCount = 0;
106 m_symbolCount = 0;
107 m_finalStates.Clear();
108 m_transitions.Clear();
109 }
110
111 public bool Contains(AutomatonTransition item) {
112 return m_transitions.Contains(item);
113 }
114
115 public void CopyTo(AutomatonTransition[] array, int arrayIndex) {
116 m_transitions.CopyTo(array, arrayIndex);
117 }
118
119 public bool Remove(AutomatonTransition item) {
120 AssertNotReadOnly();
121 m_transitions.Remove(item);
122 }
123
124 public int Count {
125 get {
126 return m_transitions.Count;
127 }
128 }
129
130 public bool IsReadOnly {
131 get {
132 return m_dfaTable != null;
133 }
134 }
135
136 public IEnumerator<AutomatonTransition> GetEnumerator() {
137 return m_transitions.GetEnumerator();
138 }
139
140 System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() {
141 return GetEnumerator();
142 }
143
144 /// <summary>Формирует множества конечных состояний перед началом работы алгоритма минимизации.</summary>
145 /// <remarks>
146 /// В процессе построения минимального автомата требуется разделить множество состояний,
147 /// на два подмножества - конечные состояния и все остальные, после чего эти подмножества
148 /// будут резделены на более мелкие. Иногда требуется гарантировать различия конечных сосотяний,
149 /// для этого необходимо переопределить даннцю фукнцию, для получения множеств конечных состояний.
150 /// </remarks>
151 /// <returns>The final states.</returns>
152 protected virtual IEnumerable<HashSet<int>> GroupFinalStates() {
153 return new HashSet<int>[] { m_finalStates };
154 }
155
156 protected void Optimize<TInput, TState>(
157 IDFATableBuilder optimalDFA,
158 IAlphabet<TInput> inputAlphabet,
159 IAlphabetBuilder<TInput> optimalInputAlphabet,
160 IAlphabet<TState> stateAlphabet,
161 IAlphabetBuilder<TState> optimalStateAlphabet
162 ) {
163 Safe.ArgumentNotNull(optimalDFA, "dfa");
164 Safe.ArgumentNotNull(optimalInputAlphabet, "optimalInputAlphabet");
165 Safe.ArgumentNotNull(optimalStateAlphabet, "optimalStateAlphabet");
166 Safe.ArgumentNotNull(inputAlphabet, "inputAlphabet");
167 Safe.ArgumentNotNull(stateAlphabet, "stateAlphabet");
168
169 if (inputAlphabet.Count != m_symbolCount)
170 throw new InvalidOperationException("The input symbols aphabet mismatch");
171 if (stateAlphabet.Count != m_stateCount)
172 throw new InvalidOperationException("The states alphabet mismatch");
173
174 var setComparer = new CustomEqualityComparer<HashSet<int>>(
175 (x, y) => x.SetEquals(y),
176 s => s.Sum(x => x.GetHashCode())
177 );
178
179 var optimalStates = new HashSet<HashSet<int>>(setComparer);
180 var queue = new HashSet<HashSet<int>>(setComparer);
181
182 // получаем конечные состояния, сгруппированные по маркерам
183 optimalStates.UnionWith(
184 GroupFinalStates()
185 );
186
187 var state = new HashSet<int>(
188 Enumerable
189 .Range(0, m_stateCount - 1)
190 .Where(i => !m_finalStates.Contains(i))
191 );
192
193 optimalStates.Add(state);
194 queue.Add(state);
195
196 var rmap = m_transitions
197 .GroupBy(t => t.s2)
198 .ToLookup(
199 g => g.Key, // s2
200 g => g.ToLookup(t => t.edge, t => t.s1)
201 );
202
203 while (queue.Count > 0) {
204 var stateA = queue.First();
205 queue.Remove(stateA);
206
207 for (int c = 0; c < m_symbolCount; c++) {
208 var stateX = new HashSet<int>();
209 foreach(var a in stateA)
210 stateX.UnionWith(rmap[a][c]); // all states from wich 'c' leads to 'a'
211
212 foreach (var stateY in optimalStates.ToArray()) {
213 if (stateX.Overlaps(stateY) && !stateY.IsSubsetOf(stateX)) {
214 var stateR1 = new HashSet<int>(stateY);
215 var stateR2 = new HashSet<int>(stateY);
216
217 stateR1.IntersectWith(stateX);
218 stateR2.ExceptWith(stateX);
219
220 optimalStates.Remove(stateY);
221 optimalStates.Add(stateR1);
222 optimalStates.Add(stateR2);
223
224 if (queue.Contains(stateY)) {
225 queue.Remove(stateY);
226 queue.Add(stateR1);
227 queue.Add(stateR2);
228 } else {
229 queue.Add(stateR1.Count <= stateR2.Count ? stateR1 : stateR2);
230 }
231 }
232 }
233 }
234 }
235
236 // карта получения оптимального состояния по соотвествующему ему простому состоянию
237 var statesMap = stateAlphabet.Reclassify(optimalStateAlphabet, optimalStates);
238
239 // получаем минимальный алфавит
240 // входные символы не различимы, если Move(s,a1) == Move(s,a2)
241 var optimalAlphabet = m_transitions
242 .GroupBy(t => Tuple.Create(statesMap[t.s1], statesMap[t.s2]), t => t.edge);
243
244 var alphabetMap = inputAlphabet.Reclassify(optimalInputAlphabet, optimalAlphabet);
245
246 // построение автомата
247 optimalDFA.SetInitialState(statesMap[m_initialState]);
248
249 foreach (var sf in m_finalStates.GroupBy(s => statesMap[s]))
250 optimalDFA.MarkFinalState(sf.Key);
251
252 foreach (var t in m_transitions.Select(t => new AutomatonTransition(statesMap[t.s1],statesMap[t.s2],alphabetMap[t.edge])).Distinct())
253 optimalDFA.Add(t);
254
255 }
256
257 protected void PrintDFA<TInput, TState>(IAlphabet<TInput> inputAlphabet, IAlphabet<TState> stateAlphabet) {
258 Safe.ArgumentNotNull(inputAlphabet, "inputAlphabet");
259 Safe.ArgumentNotNull(stateAlphabet, "stateAlphabet");
260
261 var inputMap = inputAlphabet.CreateReverseMap();
262 var stateMap = stateAlphabet.CreateReverseMap();
263
264 for (int i = 0; i < inputMap.Length; i++)
265 Console.WriteLine("C{0}: {1}", i, String.Join(",", inputMap[i]));
266
267
268 foreach(var t in m_transitions)
269 Console.WriteLine(
270 "[{0}] -{{{1}}}-> [{2}]{3}",
271 stateMap[t.s1],
272 String.Join(",", inputMap[t.edge]),
273 stateMap[t.s2],
274 m_finalStates.Contains(t.s2) ? "$" : ""
275 );
276
277 }
278
279 }
280 }