Is the negation of a regular expression still regular?

Question

All articles (example) I read till now about regular expressions and NFAs explain three operations:

• sequence
• alternation (union)
• repetition (Kleene star)

No one talks about negation. Is the negation not regular?

Update:

@RemcoGerlich What does it mean "swap the states". Can you explain it with the Kleene closure?

How would the Kleene closure look with swapped states?

Answer 1

Yes; first, every non-deterministic finite automaton can be converted to a deterministic finite automaton that accepts the same language.

Now, just make all accepting states non-accepting and vice versa: this new DFA accepts a string exactly when the original DFA wouldn't, so its language is the complement of the orignal language.

Answer 2

An insight about my own question.

The reason why articles explaining the conversion of regular expression to NFAs do not explain negation seems to be a particular problem of NFAs, which make negation complicated. As RemcoGerlich explained the NFA must be converted to a DFA to negate it. But normally the regular expression first gets converted to a NFA and after that to a DFA.

I found a paper which describes how to avoid the creation of a NFA. Instead the regular expression is converted directly into a DFA by the use of derivatives: "Regular-expression derivatives reexamined". And this approach makes it quite easy to implement also negation.