From: Hans Aberg (haberg@math.su.se)
Date: Sat Oct 13 2007 - 17:48:55 CDT
On 14 Oct 2007, at 00:05, Philippe Verdy wrote:
> All my regexps are first normalized to alternations and negations ONLY
> (instead of putting the negation at the beginning of the regexp
> ONLY and
> using multiple binary set operators "|", "&", "\" like suggested in
> the
> recent paper submitted to the UTC).
The definition in terms of a language L(x) has the advantage of
avoiding that problem, and being theoretically clearer exactly as to
what is being defined.
> This greatly simplifies the optimization of the transition graph,
> where I
> reduce and reorder the number of transitions per node in the graph
> to reduce
> the number of tests to perform at each state.
And leaving this to an implementation problem. For example, somebody
might want to implement a hybrid FA, where the DFA states are
computed dynamically from the NFA and cached. The book by Aho et al.
[loc.cit.] says this gives the best overall time and space complexity.
Hans Åberg
This archive was generated by hypermail 2.1.5 : Sat Oct 13 2007 - 17:50:34 CDT