--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/Implab/Automaton/DFADefinition.cs	Wed Feb 24 08:39:53 2016 +0300
@@ -0,0 +1,213 @@
+using Implab;
+using System;
+using System.Collections.Generic;
+using System.Linq;
+
+namespace Implab.Automaton {
+    public class DFADefinition<TInput, TState, TTag> : IDFADefinitionBuilder<TTag>, IDFADefinition<TInput, TState, TTag> {
+        DFAStateDescriptior<TTag>[] m_dfaTable;
+        readonly IAlphabet<TInput> m_inputAlphabet;
+        readonly IAlphabet<TState> m_stateAlphabet;
+
+        readonly Dictionary<int, TTag[]> m_finalStates = new Dictionary<int, TTag[]>();
+        readonly HashSet<AutomatonTransition> m_transitions = new HashSet<AutomatonTransition>();
+
+        public DFADefinition(IAlphabet<TInput> inputAlphabet, IAlphabet<TState> stateAlphabet) {
+            Safe.ArgumentNotNull(inputAlphabet, "inputAlphabet");
+            Safe.ArgumentNotNull(stateAlphabet, "stateAlphabet");
+
+            m_inputAlphabet = inputAlphabet;
+            m_stateAlphabet = stateAlphabet;
+        }
+
+        public void DefineTransition(int s1, int s2, int symbol) {
+            Safe.ArgumentInRange(s1, 0, m_stateAlphabet.Count-1, "s1");
+            Safe.ArgumentInRange(s2, 0, m_stateAlphabet.Count-1, "s2");
+            Safe.ArgumentInRange(symbol, 0, m_inputAlphabet.Count-1, "symbol");
+
+            m_transitions.Add(new AutomatonTransition(s1, s2, symbol));
+        }
+
+
+        #region IDFADefinition implementation
+
+        public DFAStateDescriptior<TTag>[] GetTransitionTable() {
+            if (m_dfaTable == null) {
+                m_dfaTable = new DFAStateDescriptior<TTag>[m_stateAlphabet.Count];
+
+                foreach (var pair in m_finalStates) {
+                    var idx = pair.Key;
+
+                    m_dfaTable[idx].final = true;
+                    m_dfaTable[idx].tag = m_dfaTable[idx].tag != null ?
+                        m_dfaTable[idx].tag.Concat(pair.Value).Distinct().ToArray() :
+                        pair.Value;
+                }
+
+                foreach (var t in m_transitions) {
+                    if (m_dfaTable[t.s1].transitions == null) {
+                        m_dfaTable[t.s1].transitions = new int[m_inputAlphabet.Count];
+                        for (int i = 0; i < m_dfaTable[t.s1].transitions.Length; i++)
+                            m_dfaTable[t.s1].transitions[i] = DFAConst.UNREACHABLE_STATE;
+                    }
+
+                    m_dfaTable[t.s1].transitions[t.edge] = t.s2;
+                }
+            }
+            return m_dfaTable;
+        }
+
+        public IAlphabet<TInput> InputAlphabet {
+            get {
+                return m_inputAlphabet;
+            }
+        }
+
+        public IAlphabet<TState> StateAlphabet {
+            get {
+                return m_stateAlphabet;
+            }
+        }
+
+        #endregion
+
+        #region IDFADefinitionBuilder
+
+        public void DefineTransition(int s1, int s2, int symbol) {
+            Safe.ArgumentInRange(s1, 0, m_stateAlphabet.Count - 1, "s1");
+            Safe.ArgumentInRange(s2, 0, m_stateAlphabet.Count - 1, "s2");
+            Safe.ArgumentInRange(symbol, 0, m_inputAlphabet.Count - 1, "symbol");
+
+            m_transitions.Add(new AutomatonTransition(s1, s2, symbol));
+        }
+
+        public void MarkFinalState(int state, params TTag[] tags) {
+            m_finalStates[state] = tags;
+        }
+
+
+        #endregion
+
+        protected void Optimize(IDFADefinitionBuilder<TTag> optimalDFA,IAlphabetBuilder<TInput> optimalInputAlphabet, IAlphabetBuilder<TState> optimalStateAlphabet) {
+            Safe.ArgumentNotNull(optimalDFA, "dfa");
+            Safe.ArgumentNotNull(optimalInputAlphabet, "optimalInputAlphabet");
+            Safe.ArgumentNotNull(optimalStateAlphabet, "optimalStateAlphabet");
+
+            var setComparer = new CustomEqualityComparer<HashSet<int>>(
+                (x, y) => x.SetEquals(y),
+                s => s.Sum(x => x.GetHashCode())
+            );
+
+            var arrayComparer = new CustomEqualityComparer<TTag[]>(
+                (x,y) => (new HashSet<int>(x)).SetEquals(new HashSet<int>(y)),
+                a => a.Sum(x => x.GetHashCode())
+            );
+
+            var optimalStates = new HashSet<HashSet<int>>(setComparer);
+            var queue = new HashSet<HashSet<int>>(setComparer);
+
+            // получаем конечные состояния, сгруппированные по маркерам
+            optimalStates.UnionWith(
+                m_finalStates
+                .GroupBy(pair => pair.Value, arrayComparer)
+                .Select(
+                    g => new HashSet<int>(
+                        g.Select( pair => pair.Key)
+                    )
+                )
+            );
+
+            var state = new HashSet<int>(
+                Enumerable
+                .Range(0, m_stateAlphabet.Count - 1)
+                .Where(i => !m_finalStates.ContainsKey(i))
+            );
+            optimalStates.Add(state);
+            queue.Add(state);
+
+            var rmap = m_transitions
+                .GroupBy(t => t.s2)
+                .ToLookup(
+                    g => g.Key, // s2
+                    g => g.ToLookup(t => t.edge, t => t.s1)
+                );
+
+            while (queue.Count > 0) {
+                var stateA = queue.First();
+                queue.Remove(stateA);
+
+                for (int c = 0; c < m_inputAlphabet.Count; c++) {
+                    var stateX = new HashSet<int>();
+                        foreach(var a in stateA)
+                            stateX.UnionWith(rmap[a][c]); // all states from wich 'c' leads to 'a'
+
+                    foreach (var stateY in optimalStates.ToArray()) {
+                        if (stateX.Overlaps(stateY) && !stateY.IsSubsetOf(stateX)) {
+                            var stateR1 = new HashSet<int>(stateY);
+                            var stateR2 = new HashSet<int>(stateY);
+
+                            stateR1.IntersectWith(stateX);
+                            stateR2.ExceptWith(stateX);
+
+                            optimalStates.Remove(stateY);
+                            optimalStates.Add(stateR1);
+                            optimalStates.Add(stateR2);
+
+                            if (queue.Contains(stateY)) {
+                                queue.Remove(stateY);
+                                queue.Add(stateR1);
+                                queue.Add(stateR2);
+                            } else {
+                                queue.Add(stateR1.Count <= stateR2.Count ? stateR1 : stateR2);
+                            }
+                        }
+                    }
+                }
+            }
+
+            // карта получения оптимального состояния по соотвествующему ему простому состоянию
+            var statesMap = m_stateAlphabet.Reclassify(optimalStateAlphabet, optimalStates);
+
+            // получаем минимальный алфавит
+            // входные символы не различимы, если Move(s,a1) == Move(s,a2)
+            var optimalAlphabet = m_transitions
+                .GroupBy(t => Tuple.Create(statesMap[t.s1], statesMap[t.s2]), t => t.edge);
+            
+            var alphabetMap = m_inputAlphabet.Reclassify(optimalInputAlphabet, optimalAlphabet);
+
+            var optimalTags = m_finalStates
+                .GroupBy(pair => statesMap[pair.Key])
+                .ToDictionary(
+                    g => g.Key,
+                    g => g.SelectMany(pair => pair.Value).ToArray()
+                );
+
+            // построение автомата
+            foreach (var pair in optimalTags)
+                optimalDFA.MarkFinalState(pair.Key, pair.Value);
+
+            foreach (var t in m_transitions.Select(t => new AutomatonTransition(statesMap[t.s1],statesMap[t.s2],alphabetMap[t.edge])).Distinct())
+                optimalDFA.DefineTransition(t.s1, t.s2, t.edge);
+        }
+
+        public void PrintDFA() {
+            
+            var inputMap = InputAlphabet.CreateReverseMap();
+            var stateMap = StateAlphabet.CreateReverseMap();
+            
+            for (int i = 0; i < inputMap.Length; i++) {
+                Console.WriteLine("C{0}: {1}", i, String.Join(",", inputMap[i]));
+            }
+
+            foreach(var t in m_transitions)
+                Console.WriteLine(
+                    "S{0} -{1}-> S{2}{3}",
+                    stateMap[t.s1],
+                    String.Join(",", inputMap[t.edge]),
+                    stateMap[t.s2],
+                    m_finalStates.ContainsKey(t.s2) ? "$" : ""
+                );
+
+        }
+    }
+}