using Implab; using System; using System.Collections.Generic; using System.Linq; namespace Implab.Automaton { public class DFATable : IDFATableBuilder { DFAStateDescriptior[] m_dfaTable; int m_stateCount; int m_symbolCount; int m_initialState; readonly HashSet m_finalStates = new HashSet(); readonly HashSet m_transitions = new HashSet(); 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); } public IEnumerable 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 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"); m_stateCount = Math.Max(m_stateCount, Math.Max(item.s1, item.s2) + 1); m_symbolCount = Math.Max(m_symbolCount, item.edge); m_transitions.Add(item); } public void Clear() { AssertNotReadOnly(); 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) { AssertNotReadOnly(); m_transitions.Remove(item); } public int Count { get { return m_transitions.Count; } } public bool IsReadOnly { get { return m_dfaTable != null; } } public IEnumerator GetEnumerator() { return m_transitions.GetEnumerator(); } System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() { return GetEnumerator(); } /// Формирует множества конечных состояний перед началом работы алгоритма минимизации. /// /// В процессе построения минимального автомата требуется разделить множество состояний, /// на два подмножества - конечные состояния и все остальные, после чего эти подмножества /// будут резделены на более мелкие. Иногда требуется гарантировать различия конечных сосотяний, /// для этого необходимо переопределить даннцю фукнцию, для получения множеств конечных состояний. /// /// The final states. protected virtual IEnumerable> GroupFinalStates() { return new HashSet[] { m_finalStates }; } protected void Optimize( IDFATableBuilder optimalDFA, IAlphabet inputAlphabet, IAlphabetBuilder optimalInputAlphabet, IAlphabet stateAlphabet, IAlphabetBuilder optimalStateAlphabet ) { Safe.ArgumentNotNull(optimalDFA, "dfa"); Safe.ArgumentNotNull(optimalInputAlphabet, "optimalInputAlphabet"); Safe.ArgumentNotNull(optimalStateAlphabet, "optimalStateAlphabet"); Safe.ArgumentNotNull(inputAlphabet, "inputAlphabet"); Safe.ArgumentNotNull(stateAlphabet, "stateAlphabet"); 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>( (x, y) => x.SetEquals(y), s => s.Sum(x => x.GetHashCode()) ); var optimalStates = new HashSet>(setComparer); var queue = new HashSet>(setComparer); // получаем конечные состояния, сгруппированные по маркерам optimalStates.UnionWith( GroupFinalStates() ); var state = new HashSet( Enumerable .Range(0, m_stateCount - 1) .Where(i => !m_finalStates.Contains(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_symbolCount; c++) { var stateX = new HashSet(); 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(stateY); var stateR2 = new HashSet(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 = 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 = inputAlphabet.Reclassify(optimalInputAlphabet, optimalAlphabet); // построение автомата optimalDFA.SetInitialState(statesMap[m_initialState]); foreach (var sf in m_finalStates.GroupBy(s => statesMap[s])) optimalDFA.MarkFinalState(sf.Key); foreach (var t in m_transitions.Select(t => new AutomatonTransition(statesMap[t.s1],statesMap[t.s2],alphabetMap[t.edge])).Distinct()) optimalDFA.Add(t); } protected void PrintDFA(IAlphabet inputAlphabet, IAlphabet 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], m_finalStates.Contains(t.s2) ? "$" : "" ); } } }