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

[Ethan Sommer <sommere@ethanet.com>]

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.