On 08/05/2013 09:26 PM, Orchid Win7 v1 wrote:
> I then began reading about how to transform a non-deterministic
> automaton into a deterministic one. It appears you can get rid of the
> "zero byte" moves by generating a new state for every collection of
> states reachable by zero-byte moves. I have yet to implement this yet,
> but it looks like it should significantly reduce the size of the
> generated code.
>
> I didn't actually get as far as the part where you remove the
> non-determinism completely...

It seems with a bit of clever coding, you can avoid generating null 
moves at all in the first place. However, I can't see a way to easily 
remove the non-determinism without a combinatorial explosion of states 
(i.e., producing a full decision tree like before).

Perhaps slightly disappointingly, I can't find any measurable 
performance difference between the laughably naive version, and the 
"optimised" NFA version... It seems the I/O takes so long that any 
changes to the actual data processing are of no significance.

Post a reply to this message