# HG changeset patch
# User cin
# Date 2016-03-09 22:19:33
# Node ID 0f70905b46522ae15bf2de1c4b30123912eeab9e
# Parent  181119ef3b3997445cb634f520a456a50d04cdba

Working on regular DFA

diff --git a/Implab/Automaton/DFATable.cs b/Implab/Automaton/DFATable.cs
--- a/Implab/Automaton/DFATable.cs
+++ b/Implab/Automaton/DFATable.cs
@@ -5,8 +5,6 @@ using System.Linq;
 
 namespace Implab.Automaton {
     public class DFATable : IDFATableBuilder {
-        DFAStateDescriptior[] m_dfaTable;
-
         int m_stateCount;
         int m_symbolCount;
         int m_initialState;
@@ -14,30 +12,13 @@ namespace Implab.Automaton {
         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 @@ namespace Implab.Automaton {
 
         #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 @@ namespace Implab.Automaton {
         }
 
         public void Clear() {
-            AssertNotReadOnly();
-
             m_stateCount = 0;
             m_symbolCount = 0;
             m_finalStates.Clear();
@@ -117,7 +77,6 @@ namespace Implab.Automaton {
         }
 
         public bool Remove(AutomatonTransition item) {
-            AssertNotReadOnly();
             m_transitions.Remove(item);
         }
 
@@ -129,7 +88,7 @@ namespace Implab.Automaton {
 
         public bool IsReadOnly {
             get {
-                return m_dfaTable != null;
+                return false;
             }
         }
 
@@ -153,23 +112,15 @@ namespace Implab.Automaton {
             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 @@ namespace Implab.Automaton {
             }
 
             // карта получения оптимального состояния по соотвествующему ему простому состоянию
-            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) ? "$" : ""
                 );
-
         }
 
     }
diff --git a/Implab/Automaton/DummyAlphabet.cs b/Implab/Automaton/DummyAlphabet.cs
--- a/Implab/Automaton/DummyAlphabet.cs
+++ b/Implab/Automaton/DummyAlphabet.cs
@@ -24,24 +24,14 @@ namespace Implab.Automaton {
             Enumerable.Range(0, m_size).ToArray();
         }
 
-        public int[] Reclassify(IAlphabetBuilder<int> newAlphabet, IEnumerable<IEnumerable<int>> classes) {
-            Safe.ArgumentNotNull(newAlphabet, "newAlphabet");
-            Safe.ArgumentNotNull(classes, "classes");
-            var map = new int[m_size];
-            foreach (var cls in classes) {
-                if (cls.Contains(DFAConst.UNCLASSIFIED_INPUT))
-                    continue;
-                var newid = newAlphabet.DefineClass(cls);
-                foreach (var id in cls)
-                    map[id] = newid;
-            }
-
-            return map;
+        public int Translate(int symbol) {
+            Safe.ArgumentInRange(symbol, 0, m_size, "symbol");
+            return symbol;
         }
 
-        public int Translate(int symobl) {
-            Safe.ArgumentInRange(symobl, 0, m_size, "symbol");
-            return symobl;
+        public bool Contains(int symbol) {
+            Safe.ArgumentInRange(symbol, 0, m_size, "symbol");
+            return true;
         }
 
         public int Count {
diff --git a/Implab/Automaton/IAlphabet.cs b/Implab/Automaton/IAlphabet.cs
--- a/Implab/Automaton/IAlphabet.cs
+++ b/Implab/Automaton/IAlphabet.cs
@@ -21,28 +21,14 @@ namespace Implab.Automaton {
         int Count { get; }
 
         /// <summary>
-        /// Создает карту обратного сопоставления класса символов алфавита и сопоставленным
-        /// ему исходным символам.
-        /// </summary>
-        /// <returns></returns>
-        List<TSymbol>[] CreateReverseMap();
-
-        /// <summary>
-        /// Создает новый алфавит на основе текущего, горппируя его сиволы в более
-        /// крупные непересекающиеся классы символов.
-        /// </summary>
-        /// <param name="newAlphabet">Новый, пустой алфавит, в котором быдут определены классы.</param>
-        /// <param name="classes">Множество классов символов текущего алфавита.</param>
-        /// <returns>Карта для перехода классов текущего
-        /// алфавита к классам нового.</returns>
-        /// <remarks>Ползволяет укрупнить алфавит, объединив классы в текущем алфавите. Используется при оптимизации автомата.</remarks>
-        int[] Reclassify(IAlphabetBuilder<TSymbol> newAlphabet, IEnumerable<IEnumerable<int>> classes);
-
-        /// <summary>
         /// Преобразует входной символ в индекс символа из алфавита.
         /// </summary>
         /// <param name="symobl">Исходный символ</param>
         /// <returns>Индекс в алфавите</returns>
         int Translate(TSymbol symobl);
+
+        bool Contains(TSymbol symbol);
+
+        IEnumerable<TSymbol> GetSymbols(int cls);
     }
 }
diff --git a/Implab/Automaton/IAlphabetBuilder.cs b/Implab/Automaton/IAlphabetBuilder.cs
--- a/Implab/Automaton/IAlphabetBuilder.cs
+++ b/Implab/Automaton/IAlphabetBuilder.cs
@@ -10,6 +10,8 @@ namespace Implab.Automaton {
         /// <param name="symbol">Символ для добавления.</param>
         /// <returns>Индекс класса, который попоставлен с символом.</returns>
         int DefineSymbol(TSymbol symbol);
+
+        int DefineSymbol(TSymbol symbol, int cls);
         /// <summary>
         /// Доабвляем класс символов. Множеству указанных исходных символов 
         /// будет сопоставлен символ в алфавите.
@@ -17,6 +19,8 @@ namespace Implab.Automaton {
         /// <param name="symbols">Множестов исходных символов</param>
         /// <returns>Идентификатор символа алфавита.</returns>
         int DefineClass(IEnumerable<TSymbol> symbols);
+
+        int DefineClass(IEnumerable<TSymbol> symbols, int cls);
     }
 }
 
diff --git a/Implab/Automaton/IDFATable.cs b/Implab/Automaton/IDFATable.cs
--- a/Implab/Automaton/IDFATable.cs
+++ b/Implab/Automaton/IDFATable.cs
@@ -32,12 +32,6 @@ namespace Implab.Automaton {
     /// }
     /// </example>
     public interface IDFATable : IEnumerable<AutomatonTransition> {
-        /// <summary>
-        /// Таблица переходов состояний автомата
-        /// </summary>
-        /// <returns>The transition table.</returns>
-        DFAStateDescriptior[] GetTransitionTable();
-
         int StateCount {
             get;
         }
diff --git a/Implab/Automaton/IndexedAlphabetBase.cs b/Implab/Automaton/IndexedAlphabetBase.cs
--- a/Implab/Automaton/IndexedAlphabetBase.cs
+++ b/Implab/Automaton/IndexedAlphabetBase.cs
@@ -17,16 +17,13 @@ namespace Implab.Automaton {
         int m_nextId = 1;
         readonly int[] m_map;
 
-        public int Count {
-            get { return m_nextId; }
-        }
-
         protected IndexedAlphabetBase(int mapSize) {
             m_map = new int[mapSize];
         }
 
         protected IndexedAlphabetBase(int[] map) {
-            Debug.Assert(map != null);
+            Debug.Assert(map != null && map.Length > 0);
+            Debug.Assert(map.All(x => x >= 0));
 
             m_map = map;
             m_nextId = map.Max() + 1;
@@ -39,60 +36,41 @@ namespace Implab.Automaton {
             return m_map[index];
         }
 
+        public int DefineSymbol(T symbol, int cls) {
+            var index = GetSymbolIndex(symbol);
+            m_map[index] = cls;
+            m_nextId = Math.Max(cls + 1, m_nextId);
+            return cls;
+        }
+
         public int DefineClass(IEnumerable<T> symbols) {
+            return DefineClass(symbols, m_nextId);
+        }
+
+        public int DefineClass(IEnumerable<T> symbols, int cls) {
             Safe.ArgumentNotNull(symbols, "symbols");
             symbols = symbols.Distinct();
 
-            foreach (var symbol in symbols) {
-                var index = GetSymbolIndex(symbol);
-                if (m_map[index] == DFAConst.UNCLASSIFIED_INPUT)
-                    m_map[GetSymbolIndex(symbol)] = m_nextId;
-                else
-                    throw new InvalidOperationException(String.Format("Symbol '{0}' already in use", symbol));
-            }
-            return m_nextId++;
-        }
-
-        public List<T>[] CreateReverseMap() {
-            return
-                Enumerable.Range(0, Count)
-                    .Select(
-                        i => InputSymbols
-                        .Where(x => i != DFAConst.UNCLASSIFIED_INPUT && m_map[GetSymbolIndex(x)] == i)
-                            .ToList()
-                    )
-                    .ToArray();
-        }
+            foreach (var symbol in symbols)
+                m_map[GetSymbolIndex(symbol)] = cls;
+            
+            m_nextId = Math.Max(cls + 1, m_nextId);
 
-        public int[] Reclassify(IAlphabetBuilder<T> newAlphabet, IEnumerable<IEnumerable<int>> classes) {
-            Safe.ArgumentNotNull(newAlphabet, "newAlphabet");
-            Safe.ArgumentNotNull(classes, "classes");
-            var reverseMap = CreateReverseMap();
-
-            var translationMap = new int[Count];
-
-            foreach (var scl in classes) {
-                // skip if the supper class contains the unclassified element
-                if (scl.Contains(DFAConst.UNCLASSIFIED_INPUT))
-                    continue;
-                var range = new List<T>();
-                foreach (var cl in scl) {
-                    if (cl < 0 || cl >= reverseMap.Length)
-                        throw new ArgumentOutOfRangeException(String.Format("Class {0} is not valid for the current alphabet", cl));
-                    range.AddRange(reverseMap[cl]);
-                }
-                var newClass = newAlphabet.DefineClass(range);
-                foreach (var cl in scl)
-                    translationMap[cl] = newClass;
-            }
-
-            return translationMap;
+            return cls;
         }
 
         public virtual int Translate(T symbol) {
             return m_map[GetSymbolIndex(symbol)];
         }
 
+        public int Count {
+            get { return m_nextId; }
+        }
+
+        public bool Contains(T symbol) {
+            return true;
+        }
+
         public abstract int GetSymbolIndex(T symbol);
 
         public abstract IEnumerable<T> InputSymbols { get; }
diff --git a/Implab/Automaton/MapAlphabet.cs b/Implab/Automaton/MapAlphabet.cs
--- a/Implab/Automaton/MapAlphabet.cs
+++ b/Implab/Automaton/MapAlphabet.cs
@@ -5,96 +5,57 @@ using System.Linq;
 namespace Implab.Automaton {
     public class MapAlphabet<T> : IAlphabetBuilder<T> {
         readonly Dictionary<T,int> m_map;
-        int m_nextCls = 1;
+        int m_nextCls;
+        readonly bool m_supportUnclassified;
 
-        public MapAlphabet() {
-            m_map = new Dictionary<T, int>();
-        }
-
-        public MapAlphabet(IEqualityComparer<T> comparer) {
-            m_map = new Dictionary<T, int>(comparer);
+        public MapAlphabet(bool supportUnclassified, IEqualityComparer<T> comparer) {
+            m_map = comparer != null ? new Dictionary<T, int>(comparer) : new Dictionary<T,int>();
+            m_supportUnclassified = supportUnclassified;
+            m_nextCls = supportUnclassified ? 1 : 0;
         }
 
         #region IAlphabetBuilder implementation
 
         public int DefineSymbol(T symbol) {
             int cls;
-            if (m_map.TryGetValue(symbol, out cls))
-                return cls;
+            return m_map.TryGetValue(symbol, out cls) ? cls : DefineSymbol(symbol, m_nextCls);
+        }
 
-            cls = m_nextCls++;
+        public int DefineSymbol(T symbol, int cls) {
+            Safe.ArgumentAssert(cls >= 0, "cls");
 
+            m_nextCls = Math.Max(cls + 1, m_nextCls);
             m_map.Add(symbol, cls);
-
             return cls;
         }
 
         public int DefineClass(IEnumerable<T> symbols) {
+            return DefineClass(symbols, m_nextCls);
+        }
+
+        public int DefineClass(IEnumerable<T> symbols, int cls) {
+            Safe.ArgumentAssert(cls >= 0, "cls");
             Safe.ArgumentNotNull(symbols, "symbols");
+
+            m_nextCls = Math.Max(cls + 1, m_nextCls);
             symbols = symbols.Distinct();
 
-            foreach (var symbol in symbols) {
-                if (!m_map.Contains(symbol))
-                    m_map.Add(symbol, m_nextCls);
-                else
-                    throw new InvalidOperationException(String.Format("Symbol '{0}' already in use", symbol));
-            }
-            return m_nextCls++;
+            foreach (var symbol in symbols)
+                m_map[symbol] = cls;
+            return cls;
         }
 
         #endregion
 
         #region IAlphabet implementation
 
-        public List<T>[] CreateReverseMap() {
-            var empty = new List<T>();
-            var rmap = new List<T>[m_nextCls];
-
-            for (int i = 0; i < rmap.Length; i++)
-                rmap[i] = empty;
-
-            foreach (var pair in m_map) {
-                var symbols = rmap[pair.Value];
-                if (symbols == null) {
-                    symbols = new List<T>();
-                    rmap[pair.Value] = symbols;
-                }
-
-                symbols.Add(pair.Key);
-            }
-
-            return rmap;
-        }
-
-        public int[] Reclassify(IAlphabetBuilder<T> newAlphabet, IEnumerable<IEnumerable<int>> classes) {
-            Safe.ArgumentNotNull(newAlphabet, "newAlphabet");
-            Safe.ArgumentNotNull(classes, "classes");
-
-            var rmap = CreateReverseMap();
-            var map = new int[rmap.Length];
-
-            foreach (var cls in classes) {
-                if (cls.Contains(DFAConst.UNCLASSIFIED_INPUT))
-                    continue;
-                
-                var symbols = new List<T>();
-                foreach (var id in cls) {
-                    if (id < 0 || id >= rmap.Length)
-                        throw new ArgumentOutOfRangeException(String.Format("Class {0} is not valid for the current alphabet", id));
-                    if (rmap[id] != null)
-                        symbols.AddRange(rmap[id]);
-                }
-
-                var newId = newAlphabet.DefineClass(symbols);
-
-                foreach (var id in cls)
-                    map[id] = newId;
-            }
-        }
-
-        public int Translate(T symobl) {
+        public int Translate(T symbol) {
             int cls;
-            return m_map.TryGetValue(symobl, out cls) ? cls : DFAConst.UNCLASSIFIED_INPUT;
+            if (m_map.TryGetValue(symbol, out cls))
+                return cls;
+            if (!m_supportUnclassified)
+                throw new ArgumentOutOfRangeException("symbol", "The specified symbol isn't in the alphabet");
+            return DFAConst.UNCLASSIFIED_INPUT;
         }
 
         public int Count {
@@ -103,6 +64,10 @@ namespace Implab.Automaton {
             }
         }
 
+        public bool Contains(T symbol) {
+            return m_supportUnclassified || m_map.ContainsKey(symbol);
+        }
+
         #endregion
     }
 }
diff --git a/Implab/Automaton/RegularExpressions/DFAStateDescriptorT.cs b/Implab/Automaton/RegularExpressions/DFAStateDescriptorT.cs
new file mode 100644
--- /dev/null
+++ b/Implab/Automaton/RegularExpressions/DFAStateDescriptorT.cs
@@ -0,0 +1,23 @@
+using System;
+
+namespace Implab.Automaton.RegularExpressions {
+    public struct DFAStateDescriptorT<T> {
+        public readonly bool final;
+
+        public readonly int[] transitions;
+
+        public readonly T[] tags;
+
+        public DFAStateDescriptorT(int size, bool final, T[] tags) {
+            Safe.ArgumentAssert(size >= 0, "size");
+            this.final = final;
+            this.tags = tags;
+
+            transitions = new int[size];
+
+            for (int i = 0; i < size; i++)
+                transitions[i] = DFAConst.UNREACHABLE_STATE;
+        }
+    }
+}
+
diff --git a/Implab/Automaton/RegularExpressions/RegularDFADefinition.cs b/Implab/Automaton/RegularExpressions/RegularDFADefinition.cs
--- a/Implab/Automaton/RegularExpressions/RegularDFADefinition.cs
+++ b/Implab/Automaton/RegularExpressions/RegularDFADefinition.cs
@@ -21,13 +21,6 @@ namespace Implab.Automaton.RegularExpres
             }
         }
 
-        protected override DFAStateDescriptior[] ConstructTransitionTable() {
-            if (InputAlphabet.Count != m_alphabet.Count)
-                throw new InvalidOperationException("The alphabet doesn't match the transition table");
-            
-            return base.ConstructTransitionTable();
-        }
-
         public void MarkFinalState(int s, TTag[] tags) {
             MarkFinalState(s);
             SetStateTag(s, tags);
@@ -53,16 +46,23 @@ namespace Implab.Automaton.RegularExpres
             var dfaTable = new RegularDFADefinition<TInput, TTag>(alphabet);
 
             var states = new DummyAlphabet(StateCount);
-            var map = new MapAlphabet<int>();
+            var alphaMap = new Dictionary<int,int>();
+            var stateMap = new Dictionary<int,int>();
+            Optimize(dfaTable, alphaMap, stateMap); 
 
-            Optimize(dfaTable, InputAlphabet, alphabet, states, map); 
-
-            foreach (var g in m_tags.Where(x => x.Key < StateCount).GroupBy(x => map.Translate(x.Key), x => x.Value ))
+            foreach (var g in m_tags.Where(x => x.Key < StateCount).GroupBy(x => stateMap[x.Key], x => x.Value ))
                 dfaTable.SetStateTag(g.Key, g.SelectMany(x => x).ToArray());
 
             return dfaTable;
         }
 
+        protected override IEnumerable<HashSet<int>> GroupFinalStates() {
+            var arrayComparer = new CustomEqualityComparer<TTag[]>(
+                (x,y) => x.Length == y.Length && x.All(it => y.Contains(it)),
+                x => x.Sum(it => x.GetHashCode())
+            );
+            return FinalStates.GroupBy(x => m_tags[x], arrayComparer).Select(g => new HashSet<int>(g));
+        }
 
     }
 }
diff --git a/Implab/Implab.csproj b/Implab/Implab.csproj
--- a/Implab/Implab.csproj
+++ b/Implab/Implab.csproj
@@ -190,6 +190,7 @@
     <Compile Include="Automaton\IDFATable.cs" />
     <Compile Include="Automaton\IDFATableBuilder.cs" />
     <Compile Include="Automaton\DFATable.cs" />
+    <Compile Include="Automaton\RegularExpressions\DFAStateDescriptorT.cs" />
   </ItemGroup>
   <Import Project="$(MSBuildBinPath)\Microsoft.CSharp.targets" />
   <ItemGroup />