Re: How to get a concatenation of the negations with rx (ex: [^a][^b])?

[tomas]

On Mon, Nov 13, 2023 at 08:46:15AM +0000, Anders Munch wrote:
> tomas@tuxteam.de wrote:
> > OK -- this was roughly my train of thought: build the NFA, then invert 
> > that... OMG. Then I decided this is better left as an exercise to the 
> > reader.
> 
> At the DFA level it's easy.  So you can just convert the NFA to a DFA and 
> work from there.  I did that exercise once upon a time, let me see if I can 
> remember it.
> 
> First convert to DFA.

Which already involves a power set. Uh, oh ;-)

>                       For every node, add an outgoing edge to the acceptance 
> state for every character that doesn't already have an outgoing node. Remove 
> all edges to the acceptance state that were in the original DFA.
> 
> The main problem is not implementation.  It's that it's not obvious what to 
> use them for in the variable-length searches that regexes are typically used 
> for.  It's just confusing that the string "abz" is a match for the regular 
> expression "not ab", and if you were looking for a two-character string that 
> is not "ab", then a general negation operator isn't going to help you, at 
> least not by itself.

Yes, I guess this is more or less what I hand-waved away with
my "modulo corner cases" (ain't natural language wonderful? ;)

For your example, one would have to append .* to all non-end
anchored (i.e. those not ending with $) regexps to better match
usual expectations. But who knows whether that's all.

Cheers
-- 
t

signature.asc
Description: PGP signature