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@xxxxxxxxxxxxxxx /
/_http://www.almesberger.net/____________________________________________/
-
To unsubscribe from this list: send the line "unsubscribe linux-net" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
|
