|
|
using Implab;
|
|
|
using System;
|
|
|
using System.Collections.Generic;
|
|
|
using System.Linq;
|
|
|
using System.Diagnostics;
|
|
|
using System.IO;
|
|
|
using System.CodeDom.Compiler;
|
|
|
using System.CodeDom;
|
|
|
|
|
|
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");
|
|
|
|
|
|
return 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
|
|
|
|
|
|
public void SetInitialState(int s) {
|
|
|
Safe.ArgumentAssert(s >= 0, "s");
|
|
|
m_stateCount = Math.Max(m_stateCount, s + 1);
|
|
|
m_initialState = s;
|
|
|
}
|
|
|
|
|
|
public void MarkFinalState(int state) {
|
|
|
m_stateCount = Math.Max(m_stateCount, state + 1);
|
|
|
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 + 1);
|
|
|
|
|
|
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) {
|
|
|
return m_transitions.Remove(item);
|
|
|
}
|
|
|
|
|
|
public int Count {
|
|
|
get {
|
|
|
return m_transitions.Count;
|
|
|
}
|
|
|
}
|
|
|
|
|
|
public bool IsReadOnly {
|
|
|
get {
|
|
|
return false;
|
|
|
}
|
|
|
}
|
|
|
|
|
|
public IEnumerator<AutomatonTransition> GetEnumerator() {
|
|
|
return m_transitions.GetEnumerator();
|
|
|
}
|
|
|
|
|
|
System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() {
|
|
|
return GetEnumerator();
|
|
|
}
|
|
|
|
|
|
public void AddSymbol(int symbol) {
|
|
|
Safe.ArgumentAssert(symbol >= 0, "symbol");
|
|
|
m_symbolCount = Math.Max(symbol + 1, m_symbolCount);
|
|
|
}
|
|
|
|
|
|
public int[,] CreateTransitionTable() {
|
|
|
var table = new int[StateCount,AlphabetSize];
|
|
|
|
|
|
for (int i = 0; i < StateCount; i++)
|
|
|
for (int j = 0; j < AlphabetSize; j++)
|
|
|
table[i, j] = AutomatonConst.UnreachableState;
|
|
|
|
|
|
foreach (var t in this)
|
|
|
table[t.s1,t.edge] = (byte)t.s2;
|
|
|
|
|
|
return table;
|
|
|
}
|
|
|
|
|
|
public bool[] CreateFinalStateTable() {
|
|
|
var table = new bool[StateCount];
|
|
|
|
|
|
foreach (var s in FinalStates)
|
|
|
table[s] = true;
|
|
|
|
|
|
return table;
|
|
|
}
|
|
|
|
|
|
/// <summary>Формирует множества конечных состояний перед началом работы алгоритма минимизации.</summary>
|
|
|
/// <remarks>
|
|
|
/// В процессе построения минимального автомата требуется разделить множество состояний,
|
|
|
/// на два подмножества - конечные состояния и все остальные, после чего эти подмножества
|
|
|
/// будут резделены на более мелкие. Иногда требуется гарантировать различия конечных сосотяний,
|
|
|
/// для этого необходимо переопределить даннцю фукнцию, для получения множеств конечных состояний.
|
|
|
/// </remarks>
|
|
|
/// <returns>The final states.</returns>
|
|
|
protected virtual IEnumerable<HashSet<int>> SplitFinalStates(IEnumerable<int> states) {
|
|
|
return new [] { new HashSet<int>(states) };
|
|
|
}
|
|
|
|
|
|
protected void Optimize(
|
|
|
IDFATableBuilder optimalDFA,
|
|
|
IDictionary<int,int> alphabetMap,
|
|
|
IDictionary<int,int> stateMap
|
|
|
) {
|
|
|
Safe.ArgumentNotNull(optimalDFA, "dfa");
|
|
|
Safe.ArgumentNotNull(alphabetMap, "alphabetMap");
|
|
|
Safe.ArgumentNotNull(stateMap, "stateMap");
|
|
|
|
|
|
|
|
|
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.Add(new HashSet<int>(FinalStates));
|
|
|
|
|
|
var state = new HashSet<int>(
|
|
|
Enumerable
|
|
|
.Range(0, m_stateCount)
|
|
|
.Where(i => !m_finalStates.Contains(i))
|
|
|
);
|
|
|
|
|
|
optimalStates.Add(state);
|
|
|
queue.Add(state);
|
|
|
|
|
|
var rmap = m_transitions
|
|
|
.GroupBy(t => t.s2)
|
|
|
.ToDictionary(
|
|
|
g => g.Key, // s2
|
|
|
g => g.ToLookup(t => t.edge, t => t.s1)//.ToDictionary(p => p.Key)
|
|
|
);
|
|
|
|
|
|
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.Where(rmap.ContainsKey))
|
|
|
stateX.UnionWith(rmap[a][c]); // all states from wich the symbol 'c' leads to the state 'a'
|
|
|
|
|
|
var tmp = optimalStates.ToArray();
|
|
|
foreach (var stateY in tmp) {
|
|
|
var stateR1 = new HashSet<int>(stateY);
|
|
|
var stateR2 = new HashSet<int>(stateY);
|
|
|
|
|
|
stateR1.IntersectWith(stateX);
|
|
|
stateR2.ExceptWith(stateX);
|
|
|
|
|
|
if (stateR1.Count > 0 && stateR2.Count > 0) {
|
|
|
|
|
|
|
|
|
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);
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
|
|
|
// дополнительно разбиваем конечные состояния
|
|
|
foreach (var final in optimalStates.Where(s => s.Overlaps(m_finalStates)).ToArray()) {
|
|
|
optimalStates.Remove(final);
|
|
|
foreach (var split in SplitFinalStates(final))
|
|
|
optimalStates.Add(split);
|
|
|
}
|
|
|
|
|
|
|
|
|
// карта получения оптимального состояния по соотвествующему ему простому состоянию
|
|
|
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), для любого 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 s2 = m_transitions.Where(t => stateMap[t.s1] == s && t.edge == term).Select(t => stateMap[t.s2]).DefaultIfEmpty(-1).First();
|
|
|
|
|
|
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 == AutomatonConst.UnclassifiedInput)
|
|
|
nextCls++;
|
|
|
|
|
|
// сохраняем DFAConst.UNCLASSIFIED_INPUT
|
|
|
var cls = item.Contains(AutomatonConst.UnclassifiedInput) ? AutomatonConst.UnclassifiedInput : nextCls++;
|
|
|
optimalDFA.AddSymbol(cls);
|
|
|
|
|
|
foreach (var a in item)
|
|
|
alphabetMap[a] = cls;
|
|
|
}
|
|
|
|
|
|
// построение автомата
|
|
|
optimalDFA.SetInitialState(stateMap[m_initialState]);
|
|
|
|
|
|
foreach (var sf in m_finalStates.Select(s => stateMap[s]).Distinct())
|
|
|
optimalDFA.MarkFinalState(sf);
|
|
|
|
|
|
foreach (var t in m_transitions.Select(t => new AutomatonTransition(stateMap[t.s1],stateMap[t.s2],alphabetMap[t.edge])).Distinct())
|
|
|
optimalDFA.Add(t);
|
|
|
}
|
|
|
|
|
|
/*protected string PrintDFA<TInput, TState>(IAlphabet<TInput> inputAlphabet, IAlphabet<TState> stateAlphabet) {
|
|
|
Safe.ArgumentNotNull(inputAlphabet, "inputAlphabet");
|
|
|
Safe.ArgumentNotNull(stateAlphabet, "stateAlphabet");
|
|
|
|
|
|
var data = new List<string>();
|
|
|
|
|
|
data.Add("digraph dfa {");
|
|
|
|
|
|
foreach (var final in m_finalStates)
|
|
|
data.Add(String.Format("{0} [shape=box];",String.Join("", stateAlphabet.GetSymbols(final))));
|
|
|
|
|
|
foreach (var t in m_transitions)
|
|
|
data.Add(String.Format(
|
|
|
"{0} -> {2} [label={1}];",
|
|
|
String.Join("", stateAlphabet.GetSymbols(t.s1)),
|
|
|
ToLiteral(ToLiteral(String.Join("", t.edge == AutomatonConst.UnclassifiedInput ? new [] { "@" } : inputAlphabet.GetSymbols(t.edge).Select(x => x.ToString())))),
|
|
|
String.Join("", stateAlphabet.GetSymbols(t.s2))
|
|
|
));
|
|
|
data.Add("}");
|
|
|
return String.Join("\n", data);
|
|
|
}
|
|
|
|
|
|
static string ToLiteral(string input)
|
|
|
{
|
|
|
using (var writer = new StringWriter())
|
|
|
{
|
|
|
using (var provider = CodeDomProvider.CreateProvider("CSharp"))
|
|
|
{
|
|
|
provider.GenerateCodeFromExpression(new CodePrimitiveExpression(input), writer, null);
|
|
|
return writer.ToString();
|
|
|
}
|
|
|
}
|
|
|
}*/
|
|
|
}
|
|
|
}
|
|
|
|
