Is the negation of a regular expression still regular?
https://softwareengineering.stackexchange.com/questions/340588
-
06-01-2021 - |
문제
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?
해결책
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.
다른 팁
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.