DFATable.cs
291 lines
| 11.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 { | ||||
| 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>(); | ||||
| #region IDFADefinition implementation | ||||
| public bool IsFinalState(int s) { | ||||
| Safe.ArgumentInRange(s, 0, m_stateCount, "s"); | ||||
|
cin
|
r171 | return m_finalStates.Contains(s); | ||
|
cin
|
r169 | } | ||
| 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 | ||||
| public void SetInitialState(int s) { | ||||
| Safe.ArgumentAssert(s >= 0, "s"); | ||||
| m_initialState = s; | ||||
| } | ||||
| public void MarkFinalState(int state) { | ||||
| m_finalStates.Add(state); | ||||
| } | ||||
| public void Add(AutomatonTransition item) { | ||||
| 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() { | ||||
| 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) { | ||||
| m_transitions.Remove(item); | ||||
| } | ||||
| public int Count { | ||||
| get { | ||||
| return m_transitions.Count; | ||||
| } | ||||
| } | ||||
| public bool IsReadOnly { | ||||
| get { | ||||
|
cin
|
r171 | return false; | ||
|
cin
|
r169 | } | ||
| } | ||||
| 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 }; | ||||
| } | ||||
|
cin
|
r171 | protected void Optimize( | ||
|
cin
|
r169 | IDFATableBuilder optimalDFA, | ||
|
cin
|
r171 | IDictionary<int,int> alphabetMap, | ||
| IDictionary<int,int> stateMap | ||||
|
cin
|
r169 | ) { | ||
| Safe.ArgumentNotNull(optimalDFA, "dfa"); | ||||
|
cin
|
r171 | Safe.ArgumentNotNull(alphabetMap, "alphabetMap"); | ||
| Safe.ArgumentNotNull(stateMap, "stateMap"); | ||||
|
cin
|
r169 | |||
| 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); | ||||
| } | ||||
| } | ||||
| } | ||||
| } | ||||
| } | ||||
| // карта получения оптимального состояния по соотвествующему ему простому состоянию | ||||
|
cin
|
r171 | var nextState = 0; | ||
| foreach (var item in optimalStates) { | ||||
| var id = nextState++; | ||||
| foreach (var s in item) | ||||
| stateMap[s] = id; | ||||
| } | ||||
|
cin
|
r169 | |||
| // получаем минимальный алфавит | ||||
|
cin
|
r171 | // входные символы не различимы, если 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(); | ||||
|
cin
|
r169 | |||
|
cin
|
r171 | 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++; | ||||
| } | ||||
|
cin
|
r169 | |||
| // построение автомата | ||||
|
cin
|
r171 | optimalDFA.SetInitialState(stateMap[m_initialState]); | ||
|
cin
|
r169 | |||
|
cin
|
r171 | foreach (var sf in m_finalStates.Select(s => stateMap[s]).Distinct()) | ||
| optimalDFA.MarkFinalState(sf); | ||||
|
cin
|
r169 | |||
|
cin
|
r171 | foreach (var t in m_transitions.Select(t => new AutomatonTransition(stateMap[t.s1],stateMap[t.s2],alphabetMap[t.edge])).Distinct()) | ||
|
cin
|
r169 | optimalDFA.Add(t); | ||
| } | ||||
| protected void PrintDFA<TInput, TState>(IAlphabet<TInput> inputAlphabet, IAlphabet<TState> stateAlphabet) { | ||||
| Safe.ArgumentNotNull(inputAlphabet, "inputAlphabet"); | ||||
| Safe.ArgumentNotNull(stateAlphabet, "stateAlphabet"); | ||||
| foreach(var t in m_transitions) | ||||
| Console.WriteLine( | ||||
| "[{0}] -{{{1}}}-> [{2}]{3}", | ||||
|
cin
|
r171 | String.Join(",", stateAlphabet.GetSymbols(t.s1)), | ||
| String.Join("", inputAlphabet.GetSymbols(t.edge)), | ||||
| String.Join(",", stateAlphabet.GetSymbols(t.s2)), | ||||
|
cin
|
r169 | m_finalStates.Contains(t.s2) ? "$" : "" | ||
| ); | ||||
| } | ||||
| } | ||||
| } | ||||