Re: [Fwd: [ANNOUNCE] Layer-7 Filter for Linux QoS]

[Werner Almesberger <wa@almesberger.net>]

Ethan Sommer wrote:
> Philippe Biondi wrote:
>> For every NDFA, there exist a DFA that recognize the same language.
>> So, it is possible.
>>
> 
> That is true only if you only care if either are matched. Not if you 
> care which is matched. By combining them you lose the ability to tell 
> which matched.

"exists a DFA" doesn't mean that there is only one :-) Typically,
there are a lot of DFAs for each NFA, usually an infinite number
of them. And among them are also those that don't combine states
you don't want to combine.

>> The question is : will we have enough memory to store a DFA that recognize
>> a big regexp ? The answer is : let loose some speed and use NDFA.

Also simpler DFAs would be interesting, e.g. acyclic ones. Size
shouldn't be a problem for them. In fact, for "traditional"
classification (i.e. well below layer 7), that's really all you
need.

- Werner

-- 
  _________________________________________________________________________
 / Werner Almesberger, Buenos Aires, Argentina         wa@almesberger.net /
/_http://www.almesberger.net/____________________________________________/