diff Implab/Automaton/DFATable.cs @ 183:4f82e0f161c3 ref20160224

fixed DFA optimization, JSON is fully functional
author cin
date Fri, 25 Mar 2016 02:49:02 +0300
parents 76e8f2ba12b8
children 5f7a3e1d32b9
line wrap: on
line diff
--- a/Implab/Automaton/DFATable.cs	Thu Mar 24 18:52:10 2016 +0300
+++ b/Implab/Automaton/DFATable.cs	Fri Mar 25 02:49:02 2016 +0300
@@ -141,8 +141,8 @@
         /// для этого необходимо переопределить даннцю фукнцию, для получения множеств конечных состояний.
         /// </remarks>
         /// <returns>The final states.</returns>
-        protected virtual IEnumerable<HashSet<int>> GroupFinalStates() {
-            return new HashSet<int>[] { m_finalStates };
+        protected virtual IEnumerable<HashSet<int>> SplitFinalStates(IEnumerable<int> states) {
+            return new [] { new HashSet<int>(states) };
         }
 
         protected void Optimize(
@@ -163,10 +163,7 @@
             var optimalStates = new HashSet<HashSet<int>>(setComparer);
             var queue = new HashSet<HashSet<int>>(setComparer);
 
-            // получаем конечные состояния, сгруппированные по маркерам
-            optimalStates.UnionWith(
-                GroupFinalStates()
-            );
+            optimalStates.Add(new HashSet<int>(FinalStates));
 
             var state = new HashSet<int>(
                 Enumerable
@@ -190,19 +187,19 @@
 
                 for (int c = 0; c < m_symbolCount; c++) {
                     var stateX = new HashSet<int>();
-                    //foreach(var a in stateA.Where(rmap.ContainsKey))
-                    //    stateX.UnionWith(rmap[a][c]); // all states from wich the symbol 'c' leads to the state 'a'
-
-                    stateX.UnionWith(m_transitions.Where(t => stateA.Contains(t.s2) && t.edge == c).Select(t => t.s1));
+                    foreach(var a in stateA.Where(rmap.ContainsKey))
+                        stateX.UnionWith(rmap[a][c]); // all states from wich the symbol 'c' leads to the state 'a'
 
                     var tmp = optimalStates.ToArray();
                     foreach (var stateY in tmp) {
-                        if (stateX.Overlaps(stateY) && !stateY.IsSubsetOf(stateX)) {
-                            var stateR1 = new HashSet<int>(stateY);
-                            var stateR2 = new HashSet<int>(stateY);
+                        var stateR1 = new HashSet<int>(stateY);
+                        var stateR2 = new HashSet<int>(stateY);
 
-                            stateR1.IntersectWith(stateX);
-                            stateR2.ExceptWith(stateX);
+                        stateR1.IntersectWith(stateX);
+                        stateR2.ExceptWith(stateX);
+
+                        if (stateR1.Count > 0 && stateR2.Count > 0) {
+                            
 
                             optimalStates.Remove(stateY);
                             optimalStates.Add(stateR1);
@@ -220,6 +217,14 @@
                 }
             }
 
+            // дополнительно разбиваем конечные состояния
+            foreach (var final in optimalStates.Where(s => s.Overlaps(m_finalStates)).ToArray()) {
+                optimalStates.Remove(final);
+                foreach (var split in SplitFinalStates(final))
+                    optimalStates.Add(split);
+            }
+                
+
             // карта получения оптимального состояния по соотвествующему ему простому состоянию
             var nextState = 0;
             foreach (var item in optimalStates) {