The complement of a regular language is a regular language, and for any given regular language we can check whether a string is a member of that language in O(length of the string) time.
Yes, depending on how you represent your regular language, the complement operator might not work play nicely with that representation. But eg it's fairly trivial for finite state machines or when matching via Brzozowski derivatives. See https://en.wikipedia.org/wiki/Brzozowski_derivative
Comments
See https://en.wikipedia.org/wiki/Regular_language#Closure_prope...
The complement of a regular language is a regular language, and for any given regular language we can check whether a string is a member of that language in O(length of the string) time.
Yes, depending on how you represent your regular language, the complement operator might not work play nicely with that representation. But eg it's fairly trivial for finite state machines or when matching via Brzozowski derivatives. See https://en.wikipedia.org/wiki/Brzozowski_derivative
See also https://github.com/google/redgrep
Regular languages have a bunch of closure properties. In practice, intersection and complement are really useful. So you can say things like:
[regular_expression_for_matching_email_addresses] & ![my_list_of_naughty_words]
Exercise for the reader: expand the expression above to allow the town of 'Scunthorpe'.