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

[Ethan Sommer <sommere@xxxxxxxxxxx>]

Philippe Biondi wrote:

> > I take it back, it is regular (kinda) but you can't to it with a
> > deterministic finite atomaton. If there is a cycle in pattern1, off of
> > which pattern2 has a branch, then you would need to count how many times
> > you have gone around the cycle to know where to jump to in pattern2 if
> > it fails to match pattern1 (which you can't do, pumping lemma and all
> > that.) If you use a non-determistic FA, you should be able to just go
> > through each pattern until both crash or one matches and declare that
> > the winner.
> >    
>
> Strange way of reasoning... what if pattern1 is "(subpat1|subpat2)" ?
> regexp is a regular language so it is equivalent to a DFA.
> 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.
> 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.
>  
you will have to for the reason above.