--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/Implab/Automaton/DFATable.cs	Fri Apr 22 13:08:08 2016 +0300
@@ -0,0 +1,348 @@
+using Implab;
+using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Diagnostics;
+using System.IO;
+using System.CodeDom.Compiler;
+using System.CodeDom;
+
+namespace Implab.Automaton {
+    public class DFATable : IDFATableBuilder {
+        int m_stateCount;
+        int m_symbolCount;
+        int m_initialState;
+
+        readonly HashSet<int> m_finalStates = new HashSet<int>();
+        readonly HashSet<AutomatonTransition> m_transitions = new HashSet<AutomatonTransition>();
+
+
+        #region IDFADefinition implementation
+
+        public bool IsFinalState(int s) {
+            Safe.ArgumentInRange(s, 0, m_stateCount, "s");
+
+            return m_finalStates.Contains(s);
+        }
+
+        public IEnumerable<int> FinalStates {
+            get {
+                return m_finalStates;
+            }
+        }
+
+        public int StateCount {
+            get { return m_stateCount; }
+        }
+
+        public int AlphabetSize {
+            get { return m_symbolCount; }
+        }
+
+        public int InitialState {
+            get { return m_initialState; }
+        }
+
+        #endregion
+
+        public void SetInitialState(int s) {
+            Safe.ArgumentAssert(s >= 0, "s");
+            m_stateCount = Math.Max(m_stateCount, s + 1);
+            m_initialState = s;
+        }
+
+        public void MarkFinalState(int state) {
+            m_stateCount = Math.Max(m_stateCount, state + 1);
+            m_finalStates.Add(state);
+        }
+
+        public void Add(AutomatonTransition item) {
+            Safe.ArgumentAssert(item.s1 >= 0, "item");
+            Safe.ArgumentAssert(item.s2 >= 0, "item");
+            Safe.ArgumentAssert(item.edge >= 0, "item");
+
+            m_stateCount = Math.Max(m_stateCount, Math.Max(item.s1, item.s2) + 1);
+            m_symbolCount = Math.Max(m_symbolCount, item.edge + 1);
+
+            m_transitions.Add(item);
+        }
+
+        public void Clear() {
+            m_stateCount = 0;
+            m_symbolCount = 0;
+            m_finalStates.Clear();
+            m_transitions.Clear();
+        }
+
+        public bool Contains(AutomatonTransition item) {
+            return m_transitions.Contains(item);
+        }
+
+        public void CopyTo(AutomatonTransition[] array, int arrayIndex) {
+            m_transitions.CopyTo(array, arrayIndex);
+        }
+
+        public bool Remove(AutomatonTransition item) {
+            return m_transitions.Remove(item);
+        }
+
+        public int Count {
+            get {
+                return m_transitions.Count;
+            }
+        }
+
+        public bool IsReadOnly {
+            get {
+                return false;
+            }
+        }
+
+        public IEnumerator<AutomatonTransition> GetEnumerator() {
+            return m_transitions.GetEnumerator();
+        }
+
+        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() {
+            return GetEnumerator();
+        }
+
+        public void AddSymbol(int symbol) {
+            Safe.ArgumentAssert(symbol >= 0, "symbol");
+            m_symbolCount = Math.Max(symbol + 1, m_symbolCount);
+        }
+
+        public int[,] CreateTransitionTable() {
+            var table = new int[StateCount,AlphabetSize];
+
+            for (int i = 0; i < StateCount; i++)
+                for (int j = 0; j < AlphabetSize; j++)
+                    table[i, j] = AutomatonConst.UNREACHABLE_STATE;
+
+            foreach (var t in this)
+                table[t.s1,t.edge] = t.s2;
+
+            return table;
+        }
+
+        public bool[] CreateFinalStateTable() {
+            var table = new bool[StateCount];
+
+            foreach (var s in FinalStates)
+                table[s] = true;
+
+            return table;
+        }
+
+        /// <summary>Формирует множества конечных состояний перед началом работы алгоритма минимизации.</summary>
+        /// <remarks>
+        /// В процессе построения минимального автомата требуется разделить множество состояний,
+        /// на два подмножества - конечные состояния и все остальные, после чего эти подмножества
+        /// будут резделены на более мелкие. Иногда требуется гарантировать различия конечных сосотяний,
+        /// для этого необходимо переопределить даннцю фукнцию, для получения множеств конечных состояний.
+        /// </remarks>
+        /// <returns>The final states.</returns>
+        protected virtual IEnumerable<HashSet<int>> SplitFinalStates(IEnumerable<int> states) {
+            return new [] { new HashSet<int>(states) };
+        }
+
+        protected void Optimize(
+            IDFATableBuilder optimalDFA,
+            IDictionary<int,int> alphabetMap,
+            IDictionary<int,int> stateMap
+        ) {
+            Safe.ArgumentNotNull(optimalDFA, "dfa");
+            Safe.ArgumentNotNull(alphabetMap, "alphabetMap");
+            Safe.ArgumentNotNull(stateMap, "stateMap");
+
+
+            var setComparer = new CustomEqualityComparer<HashSet<int>>(
+                (x, y) => x.SetEquals(y),
+                s => s.Sum(x => x.GetHashCode())
+            );
+
+            var optimalStates = new HashSet<HashSet<int>>(setComparer);
+            var queue = new HashSet<HashSet<int>>(setComparer);
+
+            optimalStates.Add(new HashSet<int>(FinalStates));
+
+            var state = new HashSet<int>(
+                Enumerable
+                .Range(0, m_stateCount)
+                .Where(i => !m_finalStates.Contains(i))
+            );
+
+            optimalStates.Add(state);
+            queue.Add(state);
+
+            var rmap = m_transitions
+                .GroupBy(t => t.s2)
+                .ToDictionary(
+                    g => g.Key, // s2
+                    g => g.ToLookup(t => t.edge, t => t.s1)//.ToDictionary(p => p.Key)
+                );
+
+            while (queue.Count > 0) {
+                var stateA = queue.First();
+                queue.Remove(stateA);
+
+                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'
+
+                    var tmp = optimalStates.ToArray();
+                    foreach (var stateY in tmp) {
+                        var stateR1 = new HashSet<int>(stateY);
+                        var stateR2 = new HashSet<int>(stateY);
+
+                        stateR1.IntersectWith(stateX);
+                        stateR2.ExceptWith(stateX);
+
+                        if (stateR1.Count > 0 && stateR2.Count > 0) {
+                            
+
+                            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);
+                            }
+                        }
+                    }
+                }
+            }
+
+            // дополнительно разбиваем конечные состояния
+            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) {
+                var id = nextState++;
+                foreach (var s in item)
+                    stateMap[s] = id;
+            }
+
+            // получаем минимальный алфавит
+            // входные символы не различимы, если Move(s,a1) == Move(s,a2), для любого s
+            // для этого используем алгоритм кластеризации, сначала 
+            // считаем, что все символы не различимы
+
+            var minClasses = new HashSet<HashSet<int>>(setComparer);
+            var alphaQueue = new Queue<HashSet<int>>();
+            alphaQueue.Enqueue(new HashSet<int>(Enumerable.Range(0,AlphabetSize)));
+
+            // для всех состояний, будем проверять каждый класс на различимость,
+            // т.е. символы различимы, если они приводят к разным состояниям
+            for (int s = 0 ; s < optimalStates.Count; s++) {
+                var newQueue = new Queue<HashSet<int>>();
+
+                foreach (var A in alphaQueue) {
+                    // классы из одного символа делить бесполезно, переводим их сразу в
+                    // результирующий алфавит
+                    if (A.Count == 1) {
+                        minClasses.Add(A);
+                        continue;
+                    }
+
+                    // различаем классы символов, которые переводят в различные оптимальные состояния
+                    // optimalState -> alphaClass
+                    var classes = new Dictionary<int, HashSet<int>>();
+
+                    foreach (var term in A) {
+                        // ищем все переходы класса по символу term
+                        var s2 = m_transitions.Where(t => stateMap[t.s1] == s && t.edge == term).Select(t => stateMap[t.s2]).DefaultIfEmpty(-1).First();
+
+                        HashSet<int> a2;
+                        if (!classes.TryGetValue(s2, out a2)) {
+                            a2 = new HashSet<int>();
+                            newQueue.Enqueue(a2);
+                            classes[s2] = a2;
+                        }
+                        a2.Add(term);
+                    }
+                }
+
+                if (newQueue.Count == 0)
+                    break;
+                alphaQueue = newQueue;
+            }
+
+            // после окончания работы алгоритма в очереди останутся минимальные различимые классы
+            // входных символов
+            foreach (var A in alphaQueue)
+                minClasses.Add(A);
+
+            // построение отображения алфавитов входных символов.
+            // поскольку символ DFAConst.UNCLASSIFIED_INPUT может иметь
+            // специальное значение, тогда сохраним минимальный класс,
+            // содержащий этот символ на томже месте.
+
+            var nextCls = 0;
+            foreach (var item in minClasses) {
+                if (nextCls == AutomatonConst.UNCLASSIFIED_INPUT)
+                    nextCls++;
+
+                // сохраняем DFAConst.UNCLASSIFIED_INPUT
+                var cls = item.Contains(AutomatonConst.UNCLASSIFIED_INPUT) ? AutomatonConst.UNCLASSIFIED_INPUT : nextCls++;
+                optimalDFA.AddSymbol(cls);
+
+                foreach (var a in item)
+                    alphabetMap[a] = cls;
+            }
+
+            // построение автомата
+            optimalDFA.SetInitialState(stateMap[m_initialState]);
+
+            foreach (var sf in m_finalStates.Select(s => stateMap[s]).Distinct())
+                optimalDFA.MarkFinalState(sf);
+
+            foreach (var t in m_transitions.Select(t => new AutomatonTransition(stateMap[t.s1],stateMap[t.s2],alphabetMap[t.edge])).Distinct())
+                optimalDFA.Add(t);
+        }
+
+        protected string PrintDFA<TInput, TState>(IAlphabet<TInput> inputAlphabet, IAlphabet<TState> stateAlphabet) {
+            Safe.ArgumentNotNull(inputAlphabet, "inputAlphabet");
+            Safe.ArgumentNotNull(stateAlphabet, "stateAlphabet");
+
+            var data = new List<string>();
+
+            data.Add("digraph dfa {");
+
+            foreach (var final in m_finalStates)
+                data.Add(String.Format("{0} [shape=box];",String.Join("", stateAlphabet.GetSymbols(final))));
+
+            foreach (var t in m_transitions)
+                data.Add(String.Format(
+                    "{0} -> {2} [label={1}];",
+                    String.Join("", stateAlphabet.GetSymbols(t.s1)),
+                    ToLiteral(ToLiteral(String.Join("", t.edge == AutomatonConst.UNCLASSIFIED_INPUT ? new [] { "@" } : inputAlphabet.GetSymbols(t.edge).Select(x => x.ToString())))),
+                    String.Join("", stateAlphabet.GetSymbols(t.s2))
+                ));
+            data.Add("}");
+            return String.Join("\n", data);
+        }
+
+        static string ToLiteral(string input)
+        {
+            using (var writer = new StringWriter())
+            {
+                using (var provider = CodeDomProvider.CreateProvider("CSharp"))
+                {
+                    provider.GenerateCodeFromExpression(new CodePrimitiveExpression(input), writer, null);
+                    return writer.ToString();
+                }
+            }
+        }
+    }
+}