Mercurial > pub > ImplabNet
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) {