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