Sender: |
|
Date: |
Thu, 24 Oct 2013 11:06:17 -0200 |
Reply-To: |
|
Message-ID: |
|
Subject: |
|
MIME-Version: |
1.0 |
Content-Transfer-Encoding: |
7bit |
In-Reply-To: |
|
Content-Type: |
text/plain; charset=ISO-8859-1; format=flowed |
From: |
|
Parts/Attachments: |
|
|
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
|
|
|