Why is the complement of a regular language still a regular language?

Question

According to my textbook, the complement of L1 = A* - L1 is a regular language as long as L1 is a regular language.
Doesn't A* also include Context Free languages, Context Sensitive languages, and Recursively Enumerable languages? A*-L1 would include all of them too, wouldn't it? How can it be regular then?
Under the representation of a Finite State Machine I understand why the complement is still a regular language. However, I can't understand the theory behind it.

Also, A* - L1 = A* intersection complement(L1) . Isn't defining a complement with something defined by the complement a tautology? I don't really understand how that can be valid.

Thanks.

Answer 1

I think where you are confused is that when you say "Doesn't A* also include Context Free languages, Context Sensitive languages, and Recursively Enumerable languages?" you are confusing A*, which is a set of strings, with Powerset(A*), which is a set of languages.

It is true that Powerset(A*) - {L1} is a set containing "Context Free languages, Context Sensitive languages, and Recursively Enumerable languages" but it actually isn't relevant to the theorem which just says: given any regular language L (a set of strings), then the language A*-L, also a set of strings, is also a regular language.

TL;DR there's a confusion between levels in your question: sets of strings vs. sets of languages. Any two-partition of A* into L and A*-L in which L is regular must also have A*-L regular. A* does not and cannot "contain languages" because it is a set of strings.

To your second question:

Also, A* - L1 = A* intersection complement(L1) . Isn't defining a complement with something defined by the complement a tautology?

Nice question. I suspect if this is presented as a definition, that is just defining operator -. It is not defining the "complement function" as far as I can tell. Perhaps "complement" was already defined, and your book is now trying to define the subtraction operator. Or else this is a theorem rather than a definition.

Answer 2

I can't find my copy of Hopcroft & Ullman, but I think I found the correct definition for the complement of a regular language here. It seems correct and more conversationally clear to say that the complement of L is a DFA that accepts any string except those that are a member of L. So you move the accepting state to all (formerly) non-accepting states and your are done. Since the complement is just a permutation of the DFA, the result is still a DFA.

As far as the notation goes, I think you are reading it as L1 = A* - L1 when it should be properly read as complement L1 = A* - L1 where complement is the complement operator.