--- a/Implab/Automaton/DFATable.cs	Fri Mar 04 01:56:31 2016 +0300
+++ b/Implab/Automaton/DFATable.cs	Thu Mar 10 01:19:33 2016 +0300
@@ -5,8 +5,6 @@
 
 namespace Implab.Automaton {
     public class DFATable : IDFATableBuilder {
-        DFAStateDescriptior[] m_dfaTable;
-
         int m_stateCount;
         int m_symbolCount;
         int m_initialState;
@@ -14,30 +12,13 @@
         readonly HashSet<int> m_finalStates = new HashSet<int>();
         readonly HashSet<AutomatonTransition> m_transitions = new HashSet<AutomatonTransition>();
 
-        void AssertNotReadOnly() {
-            if (m_dfaTable != null)
-                throw new InvalidOperationException("The object is readonly");
-        }
-
 
         #region IDFADefinition implementation
 
-        public DFAStateDescriptior[] GetTransitionTable() {
-            if (m_dfaTable == null) {
-                if (m_stateCount <= 0)
-                    throw new InvalidOperationException("Invalid automaton definition: states count = {0}", m_stateCount);
-                if (m_symbolCount <= 0)
-                    throw new InvalidOperationException("Invalid automaton definition: symbols count = {0}", m_symbolCount);
-
-                m_dfaTable = ConstructTransitionTable();
-            }
-            return m_dfaTable;
-        }
-
         public bool IsFinalState(int s) {
             Safe.ArgumentInRange(s, 0, m_stateCount, "s");
 
-            return m_dfaTable != null ? m_dfaTable[s].final :  m_finalStates.Contains(s);
+            return m_finalStates.Contains(s);
         }
 
         public IEnumerable<int> FinalStates {
@@ -60,35 +41,16 @@
 
         #endregion
 
-        protected virtual DFAStateDescriptior[] ConstructTransitionTable() {
-            var dfaTable = new DFAStateDescriptior[m_stateCount];
-
-
-            foreach (var t in m_transitions) {
-                if (dfaTable[t.s1].transitions == null)
-                    dfaTable[t.s1] = new DFAStateDescriptior(m_symbolCount, m_finalStates.Contains(t.s1));
-                
-                dfaTable[t.s1].transitions[t.edge] = t.s2;
-            }
-
-            foreach (var s in m_finalStates)
-                if (!dfaTable[s].final) 
-                    m_dfaTable[s] = new DFAStateDescriptior(m_symbolCount, true);
-                
-        }
-
         public void SetInitialState(int s) {
             Safe.ArgumentAssert(s >= 0, "s");
             m_initialState = s;
         }
 
         public void MarkFinalState(int state) {
-            AssertNotReadOnly();
             m_finalStates.Add(state);
         }
 
         public void Add(AutomatonTransition item) {
-            AssertNotReadOnly();
             Safe.ArgumentAssert(item.s1 >= 0, "item");
             Safe.ArgumentAssert(item.s2 >= 0, "item");
             Safe.ArgumentAssert(item.edge >= 0, "item");
@@ -100,8 +62,6 @@
         }
 
         public void Clear() {
-            AssertNotReadOnly();
-
             m_stateCount = 0;
             m_symbolCount = 0;
             m_finalStates.Clear();
@@ -117,7 +77,6 @@
         }
 
         public bool Remove(AutomatonTransition item) {
-            AssertNotReadOnly();
             m_transitions.Remove(item);
         }
 
@@ -129,7 +88,7 @@
 
         public bool IsReadOnly {
             get {
-                return m_dfaTable != null;
+                return false;
             }
         }
 
@@ -153,23 +112,15 @@
             return new HashSet<int>[] { m_finalStates };
         }
 
-        protected void Optimize<TInput, TState>(
+        protected void Optimize(
             IDFATableBuilder optimalDFA,
-            IAlphabet<TInput> inputAlphabet,
-            IAlphabetBuilder<TInput> optimalInputAlphabet,
-            IAlphabet<TState> stateAlphabet,
-            IAlphabetBuilder<TState> optimalStateAlphabet
+            IDictionary<int,int> alphabetMap,
+            IDictionary<int,int> stateMap
         ) {
             Safe.ArgumentNotNull(optimalDFA, "dfa");
-            Safe.ArgumentNotNull(optimalInputAlphabet, "optimalInputAlphabet");
-            Safe.ArgumentNotNull(optimalStateAlphabet, "optimalStateAlphabet");
-            Safe.ArgumentNotNull(inputAlphabet, "inputAlphabet");
-            Safe.ArgumentNotNull(stateAlphabet, "stateAlphabet");
+            Safe.ArgumentNotNull(alphabetMap, "alphabetMap");
+            Safe.ArgumentNotNull(stateMap, "stateMap");
 
-            if (inputAlphabet.Count != m_symbolCount)
-                throw new InvalidOperationException("The input symbols aphabet mismatch");
-            if (stateAlphabet.Count != m_stateCount)
-                throw new InvalidOperationException("The states alphabet mismatch");
 
             var setComparer = new CustomEqualityComparer<HashSet<int>>(
                 (x, y) => x.SetEquals(y),
@@ -234,46 +185,106 @@
             }
 
             // карта получения оптимального состояния по соотвествующему ему простому состоянию
-            var statesMap = stateAlphabet.Reclassify(optimalStateAlphabet, optimalStates);
+            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)
-            var optimalAlphabet = m_transitions
-                .GroupBy(t => Tuple.Create(statesMap[t.s1], statesMap[t.s2]), t => t.edge);
+            // входные символы не различимы, если 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 res = m_transitions.Where(t => stateMap[t.s1] == s && t.edge == term).Select(t => stateMap[t.s2]).ToArray();
 
-            var alphabetMap = inputAlphabet.Reclassify(optimalInputAlphabet, optimalAlphabet);
+                        var s2 = res.Length > 0 ? res[0] : -1;
+                            
+                        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 == DFAConst.UNCLASSIFIED_INPUT)
+                    nextCls++;
+
+                // сохраняем DFAConst.UNCLASSIFIED_INPUT
+                var cls = item.Contains(DFAConst.UNCLASSIFIED_INPUT) ? DFAConst.UNCLASSIFIED_INPUT : nextCls;
+
+                foreach (var a in item)
+                    alphabetMap[a] = cls;
+
+                nextCls++;
+            }
 
             // построение автомата
-            optimalDFA.SetInitialState(statesMap[m_initialState]);
+            optimalDFA.SetInitialState(stateMap[m_initialState]);
 
-            foreach (var sf in m_finalStates.GroupBy(s => statesMap[s]))
-                optimalDFA.MarkFinalState(sf.Key);
+            foreach (var sf in m_finalStates.Select(s => stateMap[s]).Distinct())
+                optimalDFA.MarkFinalState(sf);
 
-            foreach (var t in m_transitions.Select(t => new AutomatonTransition(statesMap[t.s1],statesMap[t.s2],alphabetMap[t.edge])).Distinct())
+            foreach (var t in m_transitions.Select(t => new AutomatonTransition(stateMap[t.s1],stateMap[t.s2],alphabetMap[t.edge])).Distinct())
                 optimalDFA.Add(t);
-
         }
 
         protected void PrintDFA<TInput, TState>(IAlphabet<TInput> inputAlphabet, IAlphabet<TState> stateAlphabet) {
             Safe.ArgumentNotNull(inputAlphabet, "inputAlphabet");
             Safe.ArgumentNotNull(stateAlphabet, "stateAlphabet");
 
-            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(
                     "[{0}] -{{{1}}}-> [{2}]{3}",
-                    stateMap[t.s1],
-                    String.Join(",", inputMap[t.edge]),
-                    stateMap[t.s2],
+                    String.Join(",", stateAlphabet.GetSymbols(t.s1)),
+                    String.Join("", inputAlphabet.GetSymbols(t.edge)),
+                    String.Join(",", stateAlphabet.GetSymbols(t.s2)),
                     m_finalStates.Contains(t.s2) ? "$" : ""
                 );
-
         }
 
     }