annotate Implab/Automaton/DFATable.cs @ 175:96a89dcb4060 ref20160224

sync
author cin
date Mon, 21 Mar 2016 18:41:45 +0300
parents 92d5278d1b10
children 0c3c69fe225b
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
169
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
1 using Implab;
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
2 using System;
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
3 using System.Collections.Generic;
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
4 using System.Linq;
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
5
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
6 namespace Implab.Automaton {
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
7 public class DFATable : IDFATableBuilder {
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
8 int m_stateCount;
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
9 int m_symbolCount;
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
10 int m_initialState;
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
11
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
12 readonly HashSet<int> m_finalStates = new HashSet<int>();
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
13 readonly HashSet<AutomatonTransition> m_transitions = new HashSet<AutomatonTransition>();
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
14
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
15
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
16 #region IDFADefinition implementation
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
17
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
18 public bool IsFinalState(int s) {
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
19 Safe.ArgumentInRange(s, 0, m_stateCount, "s");
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
20
171
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
21 return m_finalStates.Contains(s);
169
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
22 }
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
23
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
24 public IEnumerable<int> FinalStates {
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
25 get {
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
26 return m_finalStates;
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
27 }
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
28 }
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
29
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
30 public int StateCount {
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
31 get { return m_stateCount; }
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
32 }
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
33
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
34 public int AlphabetSize {
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
35 get { return m_symbolCount; }
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
36 }
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
37
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
38 public int InitialState {
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
39 get { return m_initialState; }
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
40 }
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
41
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
42 #endregion
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
43
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
44 public void SetInitialState(int s) {
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
45 Safe.ArgumentAssert(s >= 0, "s");
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
46 m_initialState = s;
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
47 }
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
48
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
49 public void MarkFinalState(int state) {
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
50 m_finalStates.Add(state);
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
51 }
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
52
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
53 public void Add(AutomatonTransition item) {
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
54 Safe.ArgumentAssert(item.s1 >= 0, "item");
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
55 Safe.ArgumentAssert(item.s2 >= 0, "item");
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
56 Safe.ArgumentAssert(item.edge >= 0, "item");
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
57
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
58 m_stateCount = Math.Max(m_stateCount, Math.Max(item.s1, item.s2) + 1);
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
59 m_symbolCount = Math.Max(m_symbolCount, item.edge);
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
60
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
61 m_transitions.Add(item);
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
62 }
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
63
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
64 public void Clear() {
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
65 m_stateCount = 0;
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
66 m_symbolCount = 0;
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
67 m_finalStates.Clear();
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
68 m_transitions.Clear();
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
69 }
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
70
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
71 public bool Contains(AutomatonTransition item) {
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
72 return m_transitions.Contains(item);
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
73 }
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
74
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
75 public void CopyTo(AutomatonTransition[] array, int arrayIndex) {
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
76 m_transitions.CopyTo(array, arrayIndex);
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
77 }
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
78
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
79 public bool Remove(AutomatonTransition item) {
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
80 m_transitions.Remove(item);
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
81 }
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
82
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
83 public int Count {
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
84 get {
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
85 return m_transitions.Count;
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
86 }
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
87 }
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
88
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
89 public bool IsReadOnly {
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
90 get {
171
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
91 return false;
169
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
92 }
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
93 }
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
94
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
95 public IEnumerator<AutomatonTransition> GetEnumerator() {
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
96 return m_transitions.GetEnumerator();
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
97 }
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
98
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
99 System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() {
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
100 return GetEnumerator();
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
101 }
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
102
172
92d5278d1b10 Working on text scanner
cin
parents: 171
diff changeset
103 public DFAStateDescriptor[] CreateTransitionTable() {
92d5278d1b10 Working on text scanner
cin
parents: 171
diff changeset
104 var table = new DFAStateDescriptor[StateCount];
92d5278d1b10 Working on text scanner
cin
parents: 171
diff changeset
105
92d5278d1b10 Working on text scanner
cin
parents: 171
diff changeset
106 foreach (var t in this) {
92d5278d1b10 Working on text scanner
cin
parents: 171
diff changeset
107 if (table[t.s1].transitions == null)
92d5278d1b10 Working on text scanner
cin
parents: 171
diff changeset
108 table[t.s1] = new DFAStateDescriptor(AlphabetSize, IsFinalState(t.s1));
92d5278d1b10 Working on text scanner
cin
parents: 171
diff changeset
109 if (table[t.s2].transitions == null)
92d5278d1b10 Working on text scanner
cin
parents: 171
diff changeset
110 table[t.s2] = new DFAStateDescriptor(AlphabetSize, IsFinalState(t.s2));
92d5278d1b10 Working on text scanner
cin
parents: 171
diff changeset
111 table[t.s1].transitions[t.edge] = t.s2;
92d5278d1b10 Working on text scanner
cin
parents: 171
diff changeset
112 }
92d5278d1b10 Working on text scanner
cin
parents: 171
diff changeset
113
92d5278d1b10 Working on text scanner
cin
parents: 171
diff changeset
114 return table;
92d5278d1b10 Working on text scanner
cin
parents: 171
diff changeset
115 }
92d5278d1b10 Working on text scanner
cin
parents: 171
diff changeset
116
169
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
117 /// <summary>Формирует множества конечных состояний перед началом работы алгоритма минимизации.</summary>
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
118 /// <remarks>
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
119 /// В процессе построения минимального автомата требуется разделить множество состояний,
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
120 /// на два подмножества - конечные состояния и все остальные, после чего эти подмножества
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
121 /// будут резделены на более мелкие. Иногда требуется гарантировать различия конечных сосотяний,
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
122 /// для этого необходимо переопределить даннцю фукнцию, для получения множеств конечных состояний.
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
123 /// </remarks>
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
124 /// <returns>The final states.</returns>
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
125 protected virtual IEnumerable<HashSet<int>> GroupFinalStates() {
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
126 return new HashSet<int>[] { m_finalStates };
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
127 }
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
128
171
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
129 protected void Optimize(
169
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
130 IDFATableBuilder optimalDFA,
171
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
131 IDictionary<int,int> alphabetMap,
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
132 IDictionary<int,int> stateMap
169
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
133 ) {
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
134 Safe.ArgumentNotNull(optimalDFA, "dfa");
171
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
135 Safe.ArgumentNotNull(alphabetMap, "alphabetMap");
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
136 Safe.ArgumentNotNull(stateMap, "stateMap");
169
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
137
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
138
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
139 var setComparer = new CustomEqualityComparer<HashSet<int>>(
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
140 (x, y) => x.SetEquals(y),
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
141 s => s.Sum(x => x.GetHashCode())
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
142 );
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
143
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
144 var optimalStates = new HashSet<HashSet<int>>(setComparer);
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
145 var queue = new HashSet<HashSet<int>>(setComparer);
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
146
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
147 // получаем конечные состояния, сгруппированные по маркерам
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
148 optimalStates.UnionWith(
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
149 GroupFinalStates()
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
150 );
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
151
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
152 var state = new HashSet<int>(
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
153 Enumerable
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
154 .Range(0, m_stateCount - 1)
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
155 .Where(i => !m_finalStates.Contains(i))
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
156 );
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
157
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
158 optimalStates.Add(state);
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
159 queue.Add(state);
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
160
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
161 var rmap = m_transitions
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
162 .GroupBy(t => t.s2)
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
163 .ToLookup(
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
164 g => g.Key, // s2
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
165 g => g.ToLookup(t => t.edge, t => t.s1)
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
166 );
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
167
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
168 while (queue.Count > 0) {
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
169 var stateA = queue.First();
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
170 queue.Remove(stateA);
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
171
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
172 for (int c = 0; c < m_symbolCount; c++) {
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
173 var stateX = new HashSet<int>();
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
174 foreach(var a in stateA)
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
175 stateX.UnionWith(rmap[a][c]); // all states from wich 'c' leads to 'a'
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
176
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
177 foreach (var stateY in optimalStates.ToArray()) {
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
178 if (stateX.Overlaps(stateY) && !stateY.IsSubsetOf(stateX)) {
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
179 var stateR1 = new HashSet<int>(stateY);
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
180 var stateR2 = new HashSet<int>(stateY);
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
181
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
182 stateR1.IntersectWith(stateX);
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
183 stateR2.ExceptWith(stateX);
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
184
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
185 optimalStates.Remove(stateY);
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
186 optimalStates.Add(stateR1);
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
187 optimalStates.Add(stateR2);
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
188
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
189 if (queue.Contains(stateY)) {
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
190 queue.Remove(stateY);
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
191 queue.Add(stateR1);
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
192 queue.Add(stateR2);
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
193 } else {
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
194 queue.Add(stateR1.Count <= stateR2.Count ? stateR1 : stateR2);
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
195 }
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
196 }
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
197 }
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
198 }
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
199 }
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
200
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
201 // карта получения оптимального состояния по соотвествующему ему простому состоянию
171
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
202 var nextState = 0;
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
203 foreach (var item in optimalStates) {
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
204 var id = nextState++;
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
205 foreach (var s in item)
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
206 stateMap[s] = id;
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
207 }
169
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
208
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
209 // получаем минимальный алфавит
171
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
210 // входные символы не различимы, если Move(s,a1) == Move(s,a2), для любого s
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
211 // для этого используем алгоритм кластеризации, сначала
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
212 // считаем, что все символы не различимы
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
213
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
214 var minClasses = new HashSet<HashSet<int>>(setComparer);
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
215 var alphaQueue = new Queue<HashSet<int>>();
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
216 alphaQueue.Enqueue(new HashSet<int>(Enumerable.Range(0,AlphabetSize)));
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
217
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
218 // для всех состояний, будем проверять каждый класс на различимость,
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
219 // т.е. символы различимы, если они приводят к разным состояниям
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
220 for (int s = 0 ; s < optimalStates.Count; s++) {
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
221 var newQueue = new Queue<HashSet<int>>();
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
222
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
223 foreach (var A in alphaQueue) {
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
224 // классы из одного символа делить бесполезно, переводим их сразу в
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
225 // результирующий алфавит
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
226 if (A.Count == 1) {
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
227 minClasses.Add(A);
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
228 continue;
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
229 }
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
230
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
231 // различаем классы символов, которые переводят в различные оптимальные состояния
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
232 // optimalState -> alphaClass
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
233 var classes = new Dictionary<int, HashSet<int>>();
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
234
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
235 foreach (var term in A) {
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
236 // ищем все переходы класса по символу term
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
237 var res = m_transitions.Where(t => stateMap[t.s1] == s && t.edge == term).Select(t => stateMap[t.s2]).ToArray();
169
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
238
171
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
239 var s2 = res.Length > 0 ? res[0] : -1;
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
240
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
241 HashSet<int> a2;
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
242 if (!classes.TryGetValue(s2, out a2)) {
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
243 a2 = new HashSet<int>();
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
244 newQueue.Enqueue(a2);
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
245 classes[s2] = a2;
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
246 }
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
247 a2.Add(term);
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
248 }
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
249 }
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
250
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
251 if (newQueue.Count == 0)
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
252 break;
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
253 alphaQueue = newQueue;
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
254 }
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
255
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
256 // после окончания работы алгоритма в очереди останутся минимальные различимые классы
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
257 // входных символов
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
258 foreach (var A in alphaQueue)
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
259 minClasses.Add(A);
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
260
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
261 // построение отображения алфавитов входных символов.
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
262 // поскольку символ DFAConst.UNCLASSIFIED_INPUT может иметь
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
263 // специальное значение, тогда сохраним минимальный класс,
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
264 // содержащий этот символ на томже месте.
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
265
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
266 var nextCls = 0;
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
267 foreach (var item in minClasses) {
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
268 if (nextCls == DFAConst.UNCLASSIFIED_INPUT)
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
269 nextCls++;
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
270
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
271 // сохраняем DFAConst.UNCLASSIFIED_INPUT
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
272 var cls = item.Contains(DFAConst.UNCLASSIFIED_INPUT) ? DFAConst.UNCLASSIFIED_INPUT : nextCls;
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
273
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
274 foreach (var a in item)
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
275 alphabetMap[a] = cls;
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
276
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
277 nextCls++;
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
278 }
169
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
279
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
280 // построение автомата
171
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
281 optimalDFA.SetInitialState(stateMap[m_initialState]);
169
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
282
171
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
283 foreach (var sf in m_finalStates.Select(s => stateMap[s]).Distinct())
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
284 optimalDFA.MarkFinalState(sf);
169
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
285
171
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
286 foreach (var t in m_transitions.Select(t => new AutomatonTransition(stateMap[t.s1],stateMap[t.s2],alphabetMap[t.edge])).Distinct())
169
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
287 optimalDFA.Add(t);
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
288 }
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
289
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
290 protected void PrintDFA<TInput, TState>(IAlphabet<TInput> inputAlphabet, IAlphabet<TState> stateAlphabet) {
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
291 Safe.ArgumentNotNull(inputAlphabet, "inputAlphabet");
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
292 Safe.ArgumentNotNull(stateAlphabet, "stateAlphabet");
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
293
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
294 foreach(var t in m_transitions)
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
295 Console.WriteLine(
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
296 "[{0}] -{{{1}}}-> [{2}]{3}",
171
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
297 String.Join(",", stateAlphabet.GetSymbols(t.s1)),
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
298 String.Join("", inputAlphabet.GetSymbols(t.edge)),
0f70905b4652 Working on regular DFA
cin
parents: 169
diff changeset
299 String.Join(",", stateAlphabet.GetSymbols(t.s2)),
169
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
300 m_finalStates.Contains(t.s2) ? "$" : ""
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
301 );
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
302 }
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
303
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
304 }
54270c2f29f2 DFA refactoring
cin
parents:
diff changeset
305 }