DFATransitionTable.cs
251 lines
| 9.6 KiB
| text/x-csharp
|
CSharpLexer
cin
|
r164 | using Implab; | ||
| using System; | ||||
| using System.Collections.Generic; | ||||
| using System.Linq; | ||||
| namespace Implab.Automaton { | ||||
| public class DFATransitionTable<TTag> : IDFATransitionTableBuilder<TTag> { | ||||
| DFAStateDescriptior<TTag>[] m_dfaTable; | ||||
| int m_stateCount; | ||||
| int m_symbolCount; | ||||
| int m_initialState; | ||||
| readonly Dictionary<int, TTag[]> m_finalStates = new Dictionary<int, TTag[]>(); | ||||
| readonly HashSet<AutomatonTransition> m_transitions = new HashSet<AutomatonTransition>(); | ||||
| #region IDFADefinition implementation | ||||
| public DFAStateDescriptior<TTag>[] 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_finalStates.ContainsKey(s); | ||||
| } | ||||
| public IEnumerable<KeyValuePair<int,TTag[]>> 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<TTag>[] ConstructTransitionTable() { | ||||
| var dfaTable = new DFAStateDescriptior<TTag>[m_stateCount]; | ||||
| foreach (var pair in m_finalStates) { | ||||
| var idx = pair.Key; | ||||
| dfaTable[idx].final = true; | ||||
| dfaTable[idx].tag = pair.Value; | ||||
| } | ||||
| foreach (var t in m_transitions) { | ||||
| if (dfaTable[t.s1].transitions == null) { | ||||
| dfaTable[t.s1].transitions = new int[m_symbolCount]; | ||||
| for (int i = 0; i < dfaTable[t.s1].transitions.Length; i++) | ||||
| dfaTable[t.s1].transitions[i] = DFAConst.UNREACHABLE_STATE; | ||||
| } | ||||
| dfaTable[t.s1].transitions[t.edge] = t.s2; | ||||
| } | ||||
| } | ||||
| #region IDFADefinitionBuilder | ||||
| public void DefineTransition(int s1, int s2, int symbol) { | ||||
| if (m_dfaTable != null) | ||||
| throw new InvalidOperationException("The transition table is already built"); | ||||
| Safe.ArgumentAssert(s1 > 0, "s1"); | ||||
| Safe.ArgumentAssert(s2 > 0, "s2"); | ||||
| Safe.ArgumentAssert(symbol >= 0, "symbol"); | ||||
| m_stateCount = Math.Max(Math.Max(m_stateCount, s1 + 1), s2 + 1); | ||||
| m_symbolCount = Math.Max(m_symbolCount, symbol + 1); | ||||
| m_transitions.Add(new AutomatonTransition(s1, s2, symbol)); | ||||
| } | ||||
| public void MarkFinalState(int state, params TTag[] tags) { | ||||
| if (m_dfaTable != null) | ||||
| throw new InvalidOperationException("The transition table is already built"); | ||||
| m_finalStates[state] = tags; | ||||
| } | ||||
| public void SetInitialState(int s) { | ||||
| Safe.ArgumentAssert(s >= 0, "s"); | ||||
| m_initialState = s; | ||||
| } | ||||
| #endregion | ||||
| protected void Optimize<TInput, TState>( | ||||
| IDFATransitionTableBuilder<TTag> 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 arrayComparer = new CustomEqualityComparer<TTag[]>( | ||||
| (x,y) => (new HashSet<int>(x)).SetEquals(new HashSet<int>(y)), | ||||
| a => a.Sum(x => x.GetHashCode()) | ||||
| ); | ||||
| var optimalStates = new HashSet<HashSet<int>>(setComparer); | ||||
| var queue = new HashSet<HashSet<int>>(setComparer); | ||||
| // получаем конечные состояния, сгруппированные по маркерам | ||||
| optimalStates.UnionWith( | ||||
| m_finalStates | ||||
| .GroupBy(pair => pair.Value, arrayComparer) | ||||
| .Select( | ||||
| g => new HashSet<int>( | ||||
| g.Select( pair => pair.Key) | ||||
| ) | ||||
| ) | ||||
| ); | ||||
| var state = new HashSet<int>( | ||||
| Enumerable | ||||
| .Range(0, m_stateCount - 1) | ||||
| .Where(i => !m_finalStates.ContainsKey(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); | ||||
| var optimalTags = m_finalStates | ||||
| .GroupBy(pair => statesMap[pair.Key]) | ||||
| .ToDictionary( | ||||
| g => g.Key, | ||||
| g => g.SelectMany(pair => pair.Value).ToArray() | ||||
| ); | ||||
| // построение автомата | ||||
| optimalDFA.SetInitialState(statesMap[m_initialState]); | ||||
| foreach (var pair in optimalTags) | ||||
| optimalDFA.MarkFinalState(pair.Key, pair.Value); | ||||
| foreach (var t in m_transitions.Select(t => new AutomatonTransition(statesMap[t.s1],statesMap[t.s2],alphabetMap[t.edge])).Distinct()) | ||||
| optimalDFA.DefineTransition(t.s1, t.s2, t.edge); | ||||
| } | ||||
| 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.ContainsKey(t.s2) ? "$" : "" | ||||
| ); | ||||
| } | ||||
| } | ||||
| } | ||||