Why is the addition of a common language still a common language?

Question

According to my tutorial, the complement L1 = A * - L1 is a regular language if L1 is a regular language.
Does A * also include context languages, context-sensitive and recursively enumerated languages? A * -L1 will include all of them too, right? How can this be regular? By the presentation of a state machine, I understand why the add-on is still a common language. However, I cannot understand the theory underlying it.

In addition, the complement A * - L1 = A * intersection (L1). Is a definition a complement by a specific complement a tautology? I really don't understand how possible this is.

Thanks.

Answer 1

I think you are confused by the fact that when you say: "Doesn't A* also include context free languages, context-sensitive and recursively enumerated languages?" you confuse A* , which is a set of strings , with Powerset(A*) , which contains a set of languages .

It is true that Powerset(A*) - {L1} is a collection containing "Context Languages", "Context-Sensitive Languages ​​and Recursively Enumerated Languages", but in fact it is not related to the theorem that just says: when 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 is the confusion between the levels in your question: sets of strings versus sets of languages. Any two sections A* in L and A*-L in which L is regular must also have regular A*-L . A* cannot and cannot contain languages, because it is a collection of strings.

To your second question:

In addition, the complement A * - L1 = A * intersection (L1). Does tautology define an addition to something specific by addition?

Good question. I suspect this is presented as a definition that simply defines the - operator. As far as I can tell, it does not define a “complement function”. Perhaps the "complement" has already been defined, and your book is now trying to determine the subtraction operator. Or is it more a theorem than a definition.

Answer 2

I cannot find my copy of Hopcroft and Ullman , but I think I have found the correct definition to complement the regular language here . It seems correct and more colloquial to say that the complement L is a DFA that accepts any except line of those that are members of L. Thus, you move the receiving state to all (previously) receiving states and yours are made. Since the addition is simply a permutation of the DFA, the result is still DFA.

Regarding notation, I think you read it as L1 = A* - L1 , when it should be read as complement L1 = A* - L1 , where complement is the complement operator.

Answer 3

If you can understand the automaton, then you have everything. The intuition is that if you can recognize a regular language by starting the machine and seeing that it stops in the final state, you can find out the complement of this language (by the set of all lines) by simply starting the same machine and see if it stops at a condition other than the final. Since all lines stop in any state, and the language is regular if and only if it stops in the final state, it is irregular if and only if it stops in a state other than the final one. This is probably pretty intuitive. In addition, the only thing you need to prove to yourself that the language is regular is to create an automaton for it: just change all the finite and non-final states.