Re: [Haskell-cafe] DFAs and self-referential data
Maxime Henrion wrote:
I've been playing with some code to work with DFAs, but I'm now faced with an implementation problem. In order to have states that can transition to themselves, it seems I would need self-referential data; otherwise I would need to separate those transitions from the rest and handle them specially in the code.
Perhaps an old article http://okmij.org/ftp/misc.html#ccard-transform might be of some help. The article describes not only running a finite automaton (represented as a cyclic graph) on given input but also printing the automaton out and determinizing it: converting NFA to an equivalent DFA. The latter operation converts one cyclic graph to another.
On Tue, Dec 28, 2010 at 3:09 AM,
Maxime Henrion wrote:
I've been playing with some code to work with DFAs, but I'm now faced with an implementation problem. In order to have states that can transition to themselves, it seems I would need self-referential data; otherwise I would need to separate those transitions from the rest and handle them specially in the code.
Perhaps an old article http://okmij.org/ftp/misc.html#ccard-transform
might be of some help. The article describes not only running a finite automaton (represented as a cyclic graph) on given input but also printing the automaton out and determinizing it: converting NFA to an equivalent DFA. The latter operation converts one cyclic graph to another.
That link was a 404 for me. I think you meant this link: http://okmij.org/ftp/Haskell/misc.html#ccard-transform Thanks! Jason
participants (2)
-
Jason Dagit -
oleg＠okmij.org