7

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?

Kleene closure

How would the Kleene closure look with swapped states?

Improve this question
1
  • 1
    Could you please add an example to explain what precisely you mean by negation? I assume you are asking “Given a regular language L over an alphabet S, is the language L' = {w | w ∈ S*, w ∉ L} also regular?” E.g. if S = {a}, and L = {aaa}, then L' = {'', a, aa, aaaa, aaaaa, …}. Is that what you mean?
    – amon
    Jan 20, 2017 at 12:05

2 Answers 2

Reset to default
12

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.

Improve this answer
7
  • And how to convert not (A and (B or C)) into an NFA?
    – ceving
    Jan 20, 2017 at 12:13
  • @ceving: create the DFA for (A and (B or C)) and swap the states.
    – RemcoGerlich
    Jan 20, 2017 at 12:14
  • 6
    It should be added that negating a regular language is always possible formally, but it can be infeasibly expensive practically: if you use any of the convenient shorthand notations instead of an actual DFA, there is no guarantee that the complement of one small, tidy regex will be another small, tidy regex. It might become a huge, unwieldy monster.
    – Kilian Foth
    Jan 20, 2017 at 12:19
  • 1
    Your example is a NDFA (it allows going to a next state with an empty string), it has to be converted to a DFA first, I don't have time for that nor tools to make pictures. If it were a DFA, the only accepting state is 3 (the double circle). With "swap the state" I mean to make 0, 1, and 2 accepting states, and 3 not an accepting state. But with an NDFA that doesn't yield a complement of the language.
    – RemcoGerlich
    Jan 20, 2017 at 12:33
  • 1
    To phrase this a bit more abstractly: the bidirectional connection between DFAs and regular languages means that the defining fact about regular languages is that they can be recognized using only finite state. From this it is obvious that the negation of a regular language is regular, just run the original state machine and accept if it rejects and vice versa. This clearly only requires finite state and so it corresponds to a regular language.
    – Derek Elkins left SE
    Jan 20, 2017 at 21:17
3

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.

Improve this answer
1

Not the answer you're looking for? Browse other questions tagged or ask your own question.