Theory of Compu...

Recursive languages are closed under which of the following operations?

I. Union

II. Complement

III. Concatenation

IV. Kleene star

Consider the following statement:

(i). The class of languages recognized by three stack Turing machines is exactly the class of Turing recognizable languages.

(ii). Multi-tape Turing machines are more powerful then single tape Turing machines.

(iii). Non deterministic Turing machines are more powerful than deterministic Turing machines.

Which of the the above statement/s is/true?

Let L₁ be recursively enumerable language but not recursive, L₂ be recurive language and L₃ be context free language and L₄ be regular language.

Which one of the following statements is/are true?

I. L₁ ∩ L₂ is recursively enumerable language

II. L^*₃ . L^*₄ is context free language

III. L₂ ∩ L̅₂ are recursive language

Consider the following problems:

(i) Whether a finite automaton halts on all inputs?

(ii) Whether a given Context Free Language is Regular?

(iii) Whether a Turing Machine computes the product of two numbers?

Let L₁ and L₂ be recursively enumerable languages over the alphabet Σ such that L₁ ∩ L2 = ϕ and L₁ ∪ L₂ = Σ*  Which of the following statements is/are FALSE?

I. L1 and L2 are both recursive

II.The complements of L1 and L2 are both recursively enumerable.

Let L be a regular language and R be a Turing recognizable but not acceptable language. Which of the following is possible?

I) Compliment of R can be Turing recognizable.

II) L ∪ (R)' can be recursive(where ' is complement operation).

III) Set of all strings common in R' and L can be in not RE.

IV) L ∪ R can be recursive.

V) Set of strings common in R' and L can be Recursive.