Understanding Recursive and Recursively Enumerable Languages

The question asks us to identify the statement that is not correct regarding formal languages, specifically focusing on recursive and recursively enumerable languages and their properties like closure under operations.

Let's analyze each statement provided in the options:

Analysis of Statement 1: Every recursive language is recursively enumerable

This statement is a fundamental concept in the theory of computation. A language is recursive if there exists a Turing Machine (TM) that halts on all inputs and accepts exactly the strings in the language. This TM is called a decider.

A language is recursively enumerable (RE) if there exists a Turing Machine that halts and accepts all strings in the language, but may loop forever on strings not in the language. This TM is called a recognizer.

Since a decider TM for a recursive language always halts, it also serves as a recognizer for the same language (it halts and accepts strings in the language, and halts and rejects strings not in the language, which satisfies the condition of a recognizer that halts and accepts strings in the language). Therefore, every recursive language is also recursively enumerable.

This statement is correct.

Analysis of Statement 2: L = {0ⁿ 1ⁿ 0ⁿ | n = 1, 2, 3, ....} is recursively enumerable

The language L = {0ⁿ 1ⁿ 0ⁿ | n $\ge$ 1} consists of strings with an equal number of 0s, followed by an equal number of 1s, followed by the same equal number of 0s. For example, 010, 001100, 000111000 are in L.

This language is known to be a context-sensitive language. Context-sensitive languages are a proper subset of recursive languages, and recursive languages are a proper subset of recursively enumerable languages.

A Turing Machine can be constructed to decide this language. The TM could, for instance, scan the input, mark off a 0, then mark off a 1, then mark off a 0, and repeat this process until all characters are marked. If it successfully marks all characters and the counts of 0s in the first and third parts match the count of 1s in the second part, the string is accepted. If at any point the pattern is wrong or the counts don't match, the string is rejected. Since this TM can decide the language (always halts), the language is recursive. As established earlier, every recursive language is also recursively enumerable.

Therefore, this statement is correct.

Analysis of Statement 3: Recursive languages are closed under intersection

Closure under intersection means that if you take two languages L1 and L2 that are both recursive, their intersection L1 $\cap$ L2 is also a recursive language.

Let L1 and L2 be two recursive languages. By definition, there exists a decider TM, say M1, for L1, and a decider TM, say M2, for L2. A decider always halts on all inputs.

To construct a decider for L1 $\cap$ L2, we can build a new Turing Machine, say M3. For any input string w, M3 can do the following:

• Run M1 on input w. Since M1 is a decider for a recursive language, it will halt and either accept or reject w for L1.
• If M1 rejects w, M3 immediately rejects w. (Since w is not in L1, it cannot be in L1 $\cap$ L2).
• If M1 accepts w, M3 then runs M2 on input w. Since M2 is a decider for a recursive language, it will halt and either accept or reject w for L2.
• If M2 accepts w, M3 accepts w. (Since w is in both L1 and L2, it is in L1 $\cap$ L2).
• If M2 rejects w, M3 rejects w. (Since w is not in L2, it cannot be in L1 $\cap$ L2).

Since both M1 and M2 are deciders and always halt, M3 will also always halt on any input w. M3 accepts w if and only if both M1 and M2 accept w, which means w is in L1 $\cap$ L2. Thus, M3 is a decider for L1 $\cap$ L2.

Therefore, L1 $\cap$ L2 is a recursive language. This shows that recursive languages are closed under intersection.

This statement is correct.

Analysis of Statement 4: Recursive languages are not closed under intersection

This statement directly contradicts the conclusion reached from the analysis of Statement 3. We have shown constructively that if two languages L1 and L2 are recursive, their intersection L1 $\cap$ L2 is also recursive. This means recursive languages *are* closed under intersection.

Therefore, this statement is not correct.

Identifying the Incorrect Statement

Based on our analysis, Statements 1, 2, and 3 are correct properties or facts about recursive and recursively enumerable languages. Statement 4 is false.

The statement that is not correct is that recursive languages are not closed under intersection.

Revision Table: Language Properties

Additional Information: Recursive vs. Recursively Enumerable

The key difference between a recursive language and a recursively enumerable (RE) language lies in the behavior of the Turing Machine on inputs not in the language.

• Recursive Language: Accepted by a Turing Machine that always halts. If the input string is in the language, it halts in an accept state. If the input string is not in the language, it halts in a reject state. This machine is called a decider.
• Recursively Enumerable Language: Accepted by a Turing Machine that halts in an accept state if the input string is in the language. However, if the input string is not in the language, the TM might halt in a reject state, or it might run forever (loop). This machine is called a recognizer or полурешатель (semi-decider).

The set of recursive languages is a proper subset of the set of recursively enumerable languages. This means there exist recursively enumerable languages that are not recursive. An example of such a language is the Halting Problem: L_H = { <M>, w > | Turing Machine M halts on input w }. This language is recursively enumerable but not recursive.

The closure properties under set operations like union, intersection, complementation, concatenation, and Kleene star are important for classifying language classes. Recursive languages are closed under all these standard operations except complementation, which distinguishes them from recursively enumerable languages (RE languages are closed under everything except complementation).