|
162
|
1 using Implab;
|
|
|
2 using System;
|
|
|
3 using System.Collections.Generic;
|
|
|
4 using System.Linq;
|
|
|
5
|
|
|
6 namespace Implab.Automaton {
|
|
|
7 public class DFADefinition<TInput, TState, TTag> : IDFADefinitionBuilder<TTag>, IDFADefinition<TInput, TState, TTag> {
|
|
|
8 DFAStateDescriptior<TTag>[] m_dfaTable;
|
|
|
9 readonly IAlphabet<TInput> m_inputAlphabet;
|
|
|
10 readonly IAlphabet<TState> m_stateAlphabet;
|
|
|
11
|
|
|
12 readonly Dictionary<int, TTag[]> m_finalStates = new Dictionary<int, TTag[]>();
|
|
|
13 readonly HashSet<AutomatonTransition> m_transitions = new HashSet<AutomatonTransition>();
|
|
|
14
|
|
|
15 public DFADefinition(IAlphabet<TInput> inputAlphabet, IAlphabet<TState> stateAlphabet) {
|
|
|
16 Safe.ArgumentNotNull(inputAlphabet, "inputAlphabet");
|
|
|
17 Safe.ArgumentNotNull(stateAlphabet, "stateAlphabet");
|
|
|
18
|
|
|
19 m_inputAlphabet = inputAlphabet;
|
|
|
20 m_stateAlphabet = stateAlphabet;
|
|
|
21 }
|
|
|
22
|
|
|
23 public void DefineTransition(int s1, int s2, int symbol) {
|
|
|
24 Safe.ArgumentInRange(s1, 0, m_stateAlphabet.Count-1, "s1");
|
|
|
25 Safe.ArgumentInRange(s2, 0, m_stateAlphabet.Count-1, "s2");
|
|
|
26 Safe.ArgumentInRange(symbol, 0, m_inputAlphabet.Count-1, "symbol");
|
|
|
27
|
|
|
28 m_transitions.Add(new AutomatonTransition(s1, s2, symbol));
|
|
|
29 }
|
|
|
30
|
|
|
31
|
|
|
32 #region IDFADefinition implementation
|
|
|
33
|
|
|
34 public DFAStateDescriptior<TTag>[] GetTransitionTable() {
|
|
|
35 if (m_dfaTable == null) {
|
|
|
36 m_dfaTable = new DFAStateDescriptior<TTag>[m_stateAlphabet.Count];
|
|
|
37
|
|
|
38 foreach (var pair in m_finalStates) {
|
|
|
39 var idx = pair.Key;
|
|
|
40
|
|
|
41 m_dfaTable[idx].final = true;
|
|
|
42 m_dfaTable[idx].tag = m_dfaTable[idx].tag != null ?
|
|
|
43 m_dfaTable[idx].tag.Concat(pair.Value).Distinct().ToArray() :
|
|
|
44 pair.Value;
|
|
|
45 }
|
|
|
46
|
|
|
47 foreach (var t in m_transitions) {
|
|
|
48 if (m_dfaTable[t.s1].transitions == null) {
|
|
|
49 m_dfaTable[t.s1].transitions = new int[m_inputAlphabet.Count];
|
|
|
50 for (int i = 0; i < m_dfaTable[t.s1].transitions.Length; i++)
|
|
|
51 m_dfaTable[t.s1].transitions[i] = DFAConst.UNREACHABLE_STATE;
|
|
|
52 }
|
|
|
53
|
|
|
54 m_dfaTable[t.s1].transitions[t.edge] = t.s2;
|
|
|
55 }
|
|
|
56 }
|
|
|
57 return m_dfaTable;
|
|
|
58 }
|
|
|
59
|
|
|
60 public IAlphabet<TInput> InputAlphabet {
|
|
|
61 get {
|
|
|
62 return m_inputAlphabet;
|
|
|
63 }
|
|
|
64 }
|
|
|
65
|
|
|
66 public IAlphabet<TState> StateAlphabet {
|
|
|
67 get {
|
|
|
68 return m_stateAlphabet;
|
|
|
69 }
|
|
|
70 }
|
|
|
71
|
|
|
72 #endregion
|
|
|
73
|
|
|
74 #region IDFADefinitionBuilder
|
|
|
75
|
|
|
76 public void DefineTransition(int s1, int s2, int symbol) {
|
|
|
77 Safe.ArgumentInRange(s1, 0, m_stateAlphabet.Count - 1, "s1");
|
|
|
78 Safe.ArgumentInRange(s2, 0, m_stateAlphabet.Count - 1, "s2");
|
|
|
79 Safe.ArgumentInRange(symbol, 0, m_inputAlphabet.Count - 1, "symbol");
|
|
|
80
|
|
|
81 m_transitions.Add(new AutomatonTransition(s1, s2, symbol));
|
|
|
82 }
|
|
|
83
|
|
|
84 public void MarkFinalState(int state, params TTag[] tags) {
|
|
|
85 m_finalStates[state] = tags;
|
|
|
86 }
|
|
|
87
|
|
|
88
|
|
|
89 #endregion
|
|
|
90
|
|
|
91 protected void Optimize(IDFADefinitionBuilder<TTag> optimalDFA,IAlphabetBuilder<TInput> optimalInputAlphabet, IAlphabetBuilder<TState> optimalStateAlphabet) {
|
|
|
92 Safe.ArgumentNotNull(optimalDFA, "dfa");
|
|
|
93 Safe.ArgumentNotNull(optimalInputAlphabet, "optimalInputAlphabet");
|
|
|
94 Safe.ArgumentNotNull(optimalStateAlphabet, "optimalStateAlphabet");
|
|
|
95
|
|
|
96 var setComparer = new CustomEqualityComparer<HashSet<int>>(
|
|
|
97 (x, y) => x.SetEquals(y),
|
|
|
98 s => s.Sum(x => x.GetHashCode())
|
|
|
99 );
|
|
|
100
|
|
|
101 var arrayComparer = new CustomEqualityComparer<TTag[]>(
|
|
|
102 (x,y) => (new HashSet<int>(x)).SetEquals(new HashSet<int>(y)),
|
|
|
103 a => a.Sum(x => x.GetHashCode())
|
|
|
104 );
|
|
|
105
|
|
|
106 var optimalStates = new HashSet<HashSet<int>>(setComparer);
|
|
|
107 var queue = new HashSet<HashSet<int>>(setComparer);
|
|
|
108
|
|
|
109 // получаем конечные состояния, сгруппированные по маркерам
|
|
|
110 optimalStates.UnionWith(
|
|
|
111 m_finalStates
|
|
|
112 .GroupBy(pair => pair.Value, arrayComparer)
|
|
|
113 .Select(
|
|
|
114 g => new HashSet<int>(
|
|
|
115 g.Select( pair => pair.Key)
|
|
|
116 )
|
|
|
117 )
|
|
|
118 );
|
|
|
119
|
|
|
120 var state = new HashSet<int>(
|
|
|
121 Enumerable
|
|
|
122 .Range(0, m_stateAlphabet.Count - 1)
|
|
|
123 .Where(i => !m_finalStates.ContainsKey(i))
|
|
|
124 );
|
|
|
125 optimalStates.Add(state);
|
|
|
126 queue.Add(state);
|
|
|
127
|
|
|
128 var rmap = m_transitions
|
|
|
129 .GroupBy(t => t.s2)
|
|
|
130 .ToLookup(
|
|
|
131 g => g.Key, // s2
|
|
|
132 g => g.ToLookup(t => t.edge, t => t.s1)
|
|
|
133 );
|
|
|
134
|
|
|
135 while (queue.Count > 0) {
|
|
|
136 var stateA = queue.First();
|
|
|
137 queue.Remove(stateA);
|
|
|
138
|
|
|
139 for (int c = 0; c < m_inputAlphabet.Count; c++) {
|
|
|
140 var stateX = new HashSet<int>();
|
|
|
141 foreach(var a in stateA)
|
|
|
142 stateX.UnionWith(rmap[a][c]); // all states from wich 'c' leads to 'a'
|
|
|
143
|
|
|
144 foreach (var stateY in optimalStates.ToArray()) {
|
|
|
145 if (stateX.Overlaps(stateY) && !stateY.IsSubsetOf(stateX)) {
|
|
|
146 var stateR1 = new HashSet<int>(stateY);
|
|
|
147 var stateR2 = new HashSet<int>(stateY);
|
|
|
148
|
|
|
149 stateR1.IntersectWith(stateX);
|
|
|
150 stateR2.ExceptWith(stateX);
|
|
|
151
|
|
|
152 optimalStates.Remove(stateY);
|
|
|
153 optimalStates.Add(stateR1);
|
|
|
154 optimalStates.Add(stateR2);
|
|
|
155
|
|
|
156 if (queue.Contains(stateY)) {
|
|
|
157 queue.Remove(stateY);
|
|
|
158 queue.Add(stateR1);
|
|
|
159 queue.Add(stateR2);
|
|
|
160 } else {
|
|
|
161 queue.Add(stateR1.Count <= stateR2.Count ? stateR1 : stateR2);
|
|
|
162 }
|
|
|
163 }
|
|
|
164 }
|
|
|
165 }
|
|
|
166 }
|
|
|
167
|
|
|
168 // карта получения оптимального состояния по соотвествующему ему простому состоянию
|
|
|
169 var statesMap = m_stateAlphabet.Reclassify(optimalStateAlphabet, optimalStates);
|
|
|
170
|
|
|
171 // получаем минимальный алфавит
|
|
|
172 // входные символы не различимы, если Move(s,a1) == Move(s,a2)
|
|
|
173 var optimalAlphabet = m_transitions
|
|
|
174 .GroupBy(t => Tuple.Create(statesMap[t.s1], statesMap[t.s2]), t => t.edge);
|
|
|
175
|
|
|
176 var alphabetMap = m_inputAlphabet.Reclassify(optimalInputAlphabet, optimalAlphabet);
|
|
|
177
|
|
|
178 var optimalTags = m_finalStates
|
|
|
179 .GroupBy(pair => statesMap[pair.Key])
|
|
|
180 .ToDictionary(
|
|
|
181 g => g.Key,
|
|
|
182 g => g.SelectMany(pair => pair.Value).ToArray()
|
|
|
183 );
|
|
|
184
|
|
|
185 // построение автомата
|
|
|
186 foreach (var pair in optimalTags)
|
|
|
187 optimalDFA.MarkFinalState(pair.Key, pair.Value);
|
|
|
188
|
|
|
189 foreach (var t in m_transitions.Select(t => new AutomatonTransition(statesMap[t.s1],statesMap[t.s2],alphabetMap[t.edge])).Distinct())
|
|
|
190 optimalDFA.DefineTransition(t.s1, t.s2, t.edge);
|
|
|
191 }
|
|
|
192
|
|
|
193 public void PrintDFA() {
|
|
|
194
|
|
|
195 var inputMap = InputAlphabet.CreateReverseMap();
|
|
|
196 var stateMap = StateAlphabet.CreateReverseMap();
|
|
|
197
|
|
|
198 for (int i = 0; i < inputMap.Length; i++) {
|
|
|
199 Console.WriteLine("C{0}: {1}", i, String.Join(",", inputMap[i]));
|
|
|
200 }
|
|
|
201
|
|
|
202 foreach(var t in m_transitions)
|
|
|
203 Console.WriteLine(
|
|
|
204 "S{0} -{1}-> S{2}{3}",
|
|
|
205 stateMap[t.s1],
|
|
|
206 String.Join(",", inputMap[t.edge]),
|
|
|
207 stateMap[t.s2],
|
|
|
208 m_finalStates.ContainsKey(t.s2) ? "$" : ""
|
|
|
209 );
|
|
|
210
|
|
|
211 }
|
|
|
212 }
|
|
|
213 }
|
