LATEX-L Archives

Mailing list for the LaTeX3 project


Options: Use Forum View

Use Monospaced Font
Show Text Part by Default
Show All Mail Headers

Message: [<< First] [< Prev] [Next >] [Last >>]
Topic: [<< First] [< Prev] [Next >] [Last >>]
Author: [<< First] [< Prev] [Next >] [Last >>]

Print Reply
Paulo Roberto Massa Cereda <[log in to unmask]>
Reply To:
Mailing list for the LaTeX3 project <[log in to unmask]>
Thu, 24 Oct 2013 11:06:17 -0200
text/plain (26 lines)
Hello, friends. :)

I'd like to add some humble points of view on the FSM discussion:

What I usually do is a conversion from a NFA to a DFA and then apply a 
state minimization algorithm.

What sometimes comes back to haunt me is the fact the in a DFA we have a 
transition function which has to be total by definition, so we might end 
up with a converted DFA which has 2^n states in the worst case, an the 
number of transition might end up being way greater than the number of 
states. This is not a problem in a DFA since we have a transition 
relation, but as the name suggests, we need to deal with nondeterminism.

I think we have benefits and shortcomings in both situations. I'm pro 
DFA, but the construction is quite time-consuming. One possible 
alternative is to use a NFA and applying Thompson's construction or a 
similar algorithm, but it's been a while since I had fun with them. :)

Knowing Bruno, he is probably taking all these performance tricks into 
consideration. :) After all, Bruno is the optimization master. :)

All the best,