Я успешно реализовал построение powerset (я думаю, минимизация Хаффмана) над DFA, используя односимвольные значения, но я изменил состояния FA, чтобы иметь возможность обрабатывать диапазоны Юникода. Теперь они выглядят так:
sealed partial class FA
{
public readonly Dictionary<KeyValuePair<int,int>,FA> InputTransitions = new Dictionary<KeyValuePair<int,int>,FA>();
public readonly HashSet<FA> EpsilonTransitions = new HashSet<FA>();
public int AcceptSymbol = -1;
public bool IsAccepting = false;
Мои символы хранятся в виде целых чисел в формате UTF-32, поэтому мне не приходится иметь дело с суррогатами. Каждый входной переход может принимать диапазон с начальным и конечным UTF-32. значение, закодированное как keyvaluepair
Я изменил свою подпрограмму ToDfa () (ранее работавшую для отдельных значений) для работы с диапазонами, но она работает неправильно. NormalizeSortedRangeList () берет предварительно отсортированный список диапазонов пары значений ключа и объединяет перекрывающиеся диапазоны (заменяя несколько перекрывающихся диапазонов одним диапазоном, охватывающим их все). _SetComparer просто выполняет неупорядоченные сравнения списков и коллекций
public FA ToDfa(IProgress<FAProgress> progress=null)
{
// if it's already a DFA we don't need to do this transformation.
// however, we still need to clone the state machine it because
// the consumer expects a copy, not the original state.
if (IsDfa)
return Clone();
// The DFA states are keyed by the set of NFA states they represent.
var dfaMap = new Dictionary<List<FA>, FA>(_SetComparer.Default);
var unmarked = new HashSet<FA>();
// compute the epsilon closure of the initial state in the NFA
var states = new List<FA>();
FillEpsilonClosure(states);
// create a new state to represent the current set of states. If one
// of those states is accepting, set this whole state to be accepting.
FA dfa = new FA();
var al = new List<int>();
// find the accepting symbols for the current states
foreach (var fa in states)
if (fa.IsAccepting)
if (!al.Contains(fa.AcceptSymbol))
al.Add(fa.AcceptSymbol);
// here we assign the appropriate accepting symbol
int ac = al.Count;
//if (1 == ac)
if(0<ac)
dfa.AcceptSymbol = al[0];
//else if (1 < ac)
// dfa.AcceptSymbol = al[0]; // could throw, just choose the first one
dfa.IsAccepting = 0 < ac;
FA result = dfa; // store the initial state for later, so we can return it.
// add it to the dfa map
dfaMap.Add(states, dfa);
// add it to the unmarked states, signalling that we still have work to do.
unmarked.Add(dfa);
bool done = false;
var j = 0;
while (!done)
{
if(null!=progress)
{
progress.Report(new FAProgress(FAStatus.DfaTransform, j));
}
done = true;
// a new hashset used to hold our current key states
var mapKeys = new HashSet<List<FA>>(dfaMap.Keys, _SetComparer.Default);
foreach (var mapKey in mapKeys)
{
dfa = dfaMap[mapKey];
if (unmarked.Contains(dfa))
{
// when we get here, mapKey represents the epsilon closure of our
// current dfa state, which is indicated by kvp.Value
// build the transition list for the new state by combining the transitions
// from each of the old states
// retrieve every possible input for these states
var inputs = new List<KeyValuePair<int,int>>();
foreach (var state in mapKey)
{
foreach (var trns in state.InputTransitions)
if(!inputs.Contains(trns.Key))
inputs.Add(trns.Key);
}
inputs.Sort((x, y) => {
var c = x.Key.CompareTo(y.Key);
if (0 == c)
c = x.Value.CompareTo(y.Value);
return c;
});
RangeUtility.NormalizeSortedRangeList(inputs);
// for each input, create a new transition
foreach (var input in inputs)
{
var acc = new List<int>();
var ns = new List<FA>();
foreach (var state in mapKey)
{
foreach (var trns in state.InputTransitions)
{
if (RangeUtility.Intersects(trns.Key, input))
{
FA dst = trns.Value;
foreach (var d in dst.FillEpsilonClosure())
{
// add the accepting symbols
if (d.IsAccepting)
if (!acc.Contains(d.AcceptSymbol))
acc.Add(d.AcceptSymbol);
if (!ns.Contains(d))
ns.Add(d);
}
}
}
}
FA ndfa;
if (!dfaMap.TryGetValue(ns, out ndfa))
{
ac = acc.Count;
ndfa = new FA(0 < ac);
// assign the appropriate accepting symbol
//if (1 == ac)
if(0<ac)
ndfa.AcceptSymbol = acc[0];
//else if (1 < ac)
// ndfa.AcceptSymbol = acc[0]; // could throw, instead just set it to the first state's accept
dfaMap.Add(ns, ndfa);
// work on this new state
unmarked.Add(ndfa);
done = false;
}
dfa.InputTransitions.Add(input, ndfa);
}
// we're done with this state
unmarked.Remove(dfa);
}
}
++j;
}
return result;
}
Работает вроде, но не совсем. Проблема в том, что моя дальность действия плохая, но я не могу понять, как именно. Я опустил точку GraphViz для своих состояний, но не могу понять, где она идет не так.
Я пытался смотреть на Brics (Java) и Fare (C#), но не мог ' Я не вижу смысла в их подпрограммах NFA-> DFA, которые создают кучу нежелательных состояний, которые они затем удаляют.
Я не совсем уверен, что мне нужно уточнить для вас, читатель, поскольку я просто надеваю не достаточно хорошо разбираюсь в проблемной области, поэтому, пожалуйста, оставляйте свои вопросы в комментариях, и я сделаю все возможное.
Полный источник доступен здесь https://github.com/codewitch-honey-crisis/Rolex/tree/master/Rolex/FA
Как, черт возьми, вы делаете диапазоны в конструкции блока питания? Это делают несколько библиотек, ни одной из которых я не могу понять