Regular languages are closed under complement. And any regular language can be generated using a regular grammar. Is there a systematic way to create the rewrite rules for the complement of a regular language?
Example: Below are some rewrite rules that generate this regular language: zero or more x's followed by zero or more y's:
S → xS | yA | ε
A → yA | ε
Note: ε is the empty string.
The complement of that regular language is this regular language: all strings containing at least one occurrence of yx (i.e., y before x).
I figured out some rewrite rules which generate that complement language:
T → yB | yT | xT
B → xT | xC
C → ε
But I had to figure out those rewrite rules from scratch. I didn't reuse the other rewrite rules. Intuitively, it seems like the rewrite rules for a complement language should reuse the rewrite rules of the non-complement language. But how?