User-Agent: Mozilla/5.0 (X11; Linux i686; rv:24.0) Gecko/20100101
            Thunderbird/24.0
MIME-Version: 1.0
References: <CACKZBPX-udskZ1JNVDwBzgFOfS8wMr3cBw9JwMbZwuLodfS5=A@mail.gmail.com>           
            <5268D3D0.1050209@residenset.net>
            <CACKZBPX-UXh+s5nXbTuXPDi4rCMFbs_ebjjDPufu5RSJ+xD2FA@mail.gmail.com>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Message-ID:  <52691B49.1070503@gmail.com>
Date:         Thu, 24 Oct 2013 11:06:17 -0200
Reply-To: Mailing list for the LaTeX3 project
              <LATEX-L@LISTSERV.UNI-HEIDELBERG.DE>
Sender: Mailing list for the LaTeX3 project <LATEX-L@LISTSERV.UNI-HEIDELBERG.DE>
From: Paulo Roberto Massa Cereda <cereda.paulo@GMAIL.COM>
Subject: Re: l3regex feature request + a question about the implementation
To: LATEX-L@LISTSERV.UNI-HEIDELBERG.DE
In-Reply-To:  <CACKZBPX-UXh+s5nXbTuXPDi4rCMFbs_ebjjDPufu5RSJ+xD2FA@mail.gmail.com>
Precedence: list
Envelope-To: <rainer.schoepf@GMX.NET>
Status: R

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,

Paulo