DFATable.cs
280 lines
| 10.8 KiB
| text/x-csharp
|
CSharpLexer
cin
|
r169 | 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<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); | ||||
| } | ||||
| 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 | ||||
| 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<AutomatonTransition> GetEnumerator() { | ||||
| return m_transitions.GetEnumerator(); | ||||
| } | ||||
| System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() { | ||||
| return GetEnumerator(); | ||||
| } | ||||
| /// <summary>Формирует множества конечных состояний перед началом работы алгоритма минимизации.</summary> | ||||
| /// <remarks> | ||||
| /// В процессе построения минимального автомата требуется разделить множество состояний, | ||||
| /// на два подмножества - конечные состояния и все остальные, после чего эти подмножества | ||||
| /// будут резделены на более мелкие. Иногда требуется гарантировать различия конечных сосотяний, | ||||
| /// для этого необходимо переопределить даннцю фукнцию, для получения множеств конечных состояний. | ||||
| /// </remarks> | ||||
| /// <returns>The final states.</returns> | ||||
| protected virtual IEnumerable<HashSet<int>> GroupFinalStates() { | ||||
| return new HashSet<int>[] { m_finalStates }; | ||||
| } | ||||
| protected void Optimize<TInput, TState>( | ||||
| IDFATableBuilder optimalDFA, | ||||
| IAlphabet<TInput> inputAlphabet, | ||||
| IAlphabetBuilder<TInput> optimalInputAlphabet, | ||||
| IAlphabet<TState> stateAlphabet, | ||||
| IAlphabetBuilder<TState> 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<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.UnionWith( | ||||
| GroupFinalStates() | ||||
| ); | ||||
| var state = new HashSet<int>( | ||||
| 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<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 = 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<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], | ||||
| m_finalStates.Contains(t.s2) ? "$" : "" | ||||
| ); | ||||
| } | ||||
| } | ||||
| } | ||||