honey the codewitch Ответов: 0

Как преобразовать конечный автомат в регулярное выражение в C#?

Я видел три метода, и каждый из них описан с использованием математики, которая мне недоступна.

Я бы предпочел метод леммы Ардена, поскольку он самый элегантный.

Мое текущее состояние узлов машины

класс CharFA : ICloneable {
public IDictionary<char,charfa> Transitions {get;} = new ...
public ICollection<charfa> EpsilonTransitions {get;} = new ...
общественного строка AcceptingSymbol {получить; набор } = значение null; // ненулевое в случае принятия
...
}

У меня есть функции более высокого уровня, такие как IsFinal, IsLoop и ToDfa. Я могу вычислить замыкания и Эпсилон замыкания и все такое

Я просто не могу понять лемму Ардена.

Я понимаю, что вы должны приказать штатам. Я могу сделать это, взяв закрытие в класс списка.

Я понимаю, что здесь задействована рекурсия, вплоть до определенного состояния, и я прототипировал функцию R (), чтобы попасть туда, хотя я точно не знаю, как она должна выглядеть.

Вот один из нескольких учебников, которые я нашел, но опять же, математика выше моего понимания. У меня нет формального образования в математике или compsci, но я кодирую уже более 30 лет, поэтому я понимаю код и концепции, но не символику.

Инг. Петр Земек - Проекты[^]

Что я уже пробовал:

Я пытался реализовать каждый из этих 3-х методов в учебнике, на который я ссылался, но не понимал его достаточно, чтобы каждый раз завершать код.

в настоящее время у меня есть 

public override string ToString()
{
	var dfa = ToDfa();
	var sb = new StringBuilder();
	dfa._AppendTo(sb, new List<CharFA>());
	return sb.ToString();
}
void _AppendTo(StringBuilder sb, ICollection<CharFA> visited)
{
	if (null != visited)
	{
		if (visited.Contains(this))
		{
			sb.Append("*");
			return;
		}
		visited.Add(this);
	}

	//var sb = new StringBuilder();
	var trgs = FillInputTransitionRangesGroupedByState();
	var delim = "";
	bool isAccepting = null != AcceptingSymbol;
	if (1 < trgs.Count)
		sb.Append("(");
	foreach (var trg in trgs)
	{
		sb.Append(delim);
		//sb.Append("(");
		if (1 == trg.Value.Count && 1 == trg.Value[0].Length)
			_AppendRangeTo(sb, trg.Value[0]);
		else
		{
			sb.Append("[");
			foreach (var rng in trg.Value)
				_AppendRangeTo(sb, rng);
			sb.Append("]");
		}
		trg.Key._AppendTo(sb, new List<CharFA>(visited));
		//sb.Append(")");
		delim = "|";
	}
	if (1 < trgs.Count)
		sb.Append(")");
	if (isAccepting && !IsFinal && !IsLoop)
		sb.Append("?");
}


где _AppendRangeTo() просто добавляет как "A-Z" или что-то еще, ToDfa() преобразует машину в клонированный DFA equiv, а FillInputTransitionRangesGroupedbystate() возвращает набор ключей-значений CharFA->{rangeset} или, другими словами, набор пар (destination state)<-(char ranges)

0 Ответов