4 ms·
That example doesn’t really fit since one easily could compute the negation of “a|(aa)+” in linear time by simply returning the opposite of the top-level node i
by zeroimpl 3y ago
That example doesn’t really fit since one easily could compute the negation of “a|(aa)+” in linear time by simply returning the opposite of the top-level node in the tree.
Perhaps something like “X|!Y” or similar might be impossible?
- mcyc 3y agoThe parent comment asked specifically about negating the finality of each state, which I addressed. As for how to actually implement complement in a regex engine, there are certainly some strategies like the one you mentioned that could be used (but the point of my comment was that just swapping final/non-final states is not a valid one).
- zeroimpl 3y agoAh I thought they meant flipping the finality of the final state, but I guess they said "states" so your interpretation makes more sense.