Click here to Skip to main content
15,745,270 members
Please Sign up or sign in to vote.
2.50/5 (2 votes)
I've seen three methods and they each are described using math that is beyond me.

I'd prefer Arden's Lemma method as it is the most elegant.

My current state machine node is

class CharFA : ICloneable {
public IDictionary<char,charfa> Transitions {get;} = new ...
public ICollection<charfa> EpsilonTransitions {get;} = new ...
public string AcceptingSymbol {get; set } = null; // non-null if accepting

I have higher level functions like IsFinal, IsLoop, and ToDfa. I can compute the closures and epsilon closures and all that

I simply cannot understand arden's lemma.

I get the idea that you have to order the states. I can do that by taking the closure into a List class.

I get that there's recursion involved, up to a certain state, and I've prototyped a function R() to get me there, though I don't know exactly how it should look.

Here is one of several tutorials i've found but again, the math is beyond me. I don't have a formal education in math or compsci, but I've been coding for over 30 years so I understand code and concepts, but not the symbology.

Ing. Petr Zemek - Projekty[^]

What I have tried:

I've tried to implement each of these 3 methods in the tutorial i linked to but didn't understand enough of it to complete the code each time.

currently I have

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))

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

where _AppendRangeTo() just appends like "A-Z" or whatever, ToDfa() transforms the machine to a cloned DFA equiv, and FillInputTransitionRangesGroupedByState() returns a key-value-set of CharFA->{rangeset} or in other words a set of (destination state)<-(char ranges) pairs

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900