Recursively Enumerable Languages Questions and Answers

Q: Consider the following types of languages: \(L_{1}\) : Regular, \(L_{2}\) : Context-free, \(L_{3}\) : Recursive, \(L_{4}\) : Recursively enumerable. Which of the following is/are TRUE?I. \(\overline{L_{3}} \cup L_{4}\) is recursively enumerableII. \(\overline{L_{2}} \cup L_{3}\) is recursiveIII. \(L_{1}^{*} \cap L_{2}\) is context-freeIV. \(L_{1} \cup \overline{L_{2}}\) is context-free

The true statements are I, II and III only.I: the complement of a recursive language is recursive, hence recursively enumerable, and the union of two recursively enumerable languages is recursively enumerable. True.II: every context-free language is recursive (membership is decidable, for example by the CYK algorithm), so its complement is recursive, and recursive languages are closed under union. True.III: \(L_{1}^{*}\) is regular, and the intersection of a regular language with a context-free language is context-free. True.IV: context-free languages are not closed under complement, so \(\overline{L_{2}}\) need not be context-free, and its union with a regular language need not be either. Not always true.So the options listing only I, or I with III, leave out true statements, and the option including IV includes a false one.

Q: The set of all recursively enumerable languages is

The recursively enumerable languages are closed under intersection.Given Turing machines that accept L1 and L2, a new machine can run both on the input, alternating steps, and accept once both have accepted. It accepts exactly the strings in both languages, so L1 ∩ L2 is recursively enumerable.The others are false. RE languages are not closed under complement: the halting language is RE, but its complement is not, since a language whose complement is also RE would be recursive. The recursive languages are a subset of the RE ones, not the other way round. And there are only countably many Turing machines, so the set of RE languages is countable.

Q: Which of the following are incorrect statements ?(i) A language L is said to be recursively enumerable if there exists a Turing machine that accepts L(ii) Let K \(\ge\) 1 be an integer. Any K-tape Turing machine cannot be converted to an equivalent one tape Turing machine(iii) Every computational process which can be considered to be algorithm can be converted to a Turing machine

Only statement (ii) is incorrect, so the answer is (ii) only.Statement (ii) is false: for any integer K \(\ge\) 1, a K-tape Turing machine can be converted into an equivalent single-tape Turing machine, which stores the K tapes as tracks on one tape and marks each head position. The simulation is slower, roughly quadratic in time, but accepts the same language.Statement (i) is the definition of a recursively enumerable language: some Turing machine accepts it. Statement (iii) is the Church-Turing thesis, accepted as true. Options that include (i) or (iii) are therefore wrong.

Consider the following types of languages: \(L_{1}\) : Regular, \(L_{2}\) : Context-free, \(L_{3}\) : Recursive, \(L_{4}\) : Recursively enumerable. Which of the following is/are TRUE?

I. \(\overline{L_{3}} \cup L_{4}\) is recursively enumerable
II. \(\overline{L_{2}} \cup L_{3}\) is recursive
III. \(L_{1}^{*} \cap L_{2}\) is context-free
IV. \(L_{1} \cup \overline{L_{2}}\) is context-free

A.I only
B.I and III only
C.I and IV only
D.I, II and III only

Exam Year(s)

GATE CS - 2016,

Answer: D

The true statements are I, II and III only.

I: the complement of a recursive language is recursive, hence recursively enumerable, and the union of two recursively enumerable languages is recursively enumerable. True.
II: every context-free language is recursive (membership is decidable, for example by the CYK algorithm), so its complement is recursive, and recursive languages are closed under union. True.
III: \(L_{1}^{*}\) is regular, and the intersection of a regular language with a context-free language is context-free. True.
IV: context-free languages are not closed under complement, so \(\overline{L_{2}}\) need not be context-free, and its union with a regular language need not be either. Not always true.

So the options listing only I, or I with III, leave out true statements, and the option including IV includes a false one.

Discuss in Forum

The set of all recursively enumerable languages is

A.closed under complementation.
B.closed under intersection.
C.a subset of the set of all recursive languages.
D.an uncountable set.

Exam Year(s)

GATE CS - 2018,

Answer: B

The recursively enumerable languages are closed under intersection.

Given Turing machines that accept L1 and L2, a new machine can run both on the input, alternating steps, and accept once both have accepted. It accepts exactly the strings in both languages, so L1 ∩ L2 is recursively enumerable.

The others are false. RE languages are not closed under complement: the halting language is RE, but its complement is not, since a language whose complement is also RE would be recursive. The recursive languages are a subset of the RE ones, not the other way round. And there are only countably many Turing machines, so the set of RE languages is countable.

Discuss in Forum

Which of the following production forms belongs to unrestricted grammar (Type 0) :

(i) S → ASA A → BCa BC → Aa
(ii) S → aSa/∈
(iii) BSA → aSb/ASB, A → aB/b B → Bb/a

A.(i) and (iii) only
B.(ii) and (iii) only
C.(i) and (ii) only
D.(i), (ii) and (iii) only

Exam Year(s)

MH SET - 2020, SET Exam - 2020,

Answer: D

All three belong to unrestricted grammars, so the answer is (i), (ii) and (iii) only.

A Type 0 (unrestricted) grammar allows productions \(\alpha \rightarrow \beta\) where \(\alpha\) is any string containing at least one non-terminal and \(\beta\) is any string. Every production in the three sets has a non-terminal on its left-hand side, including the context-sensitive looking BC → Aa and BSA → aSb, and the context-free S → aSa/∈.

Because the Chomsky hierarchy is nested, context-free and context-sensitive productions are also Type 0, so no set is excluded and the narrower options are wrong.

Discuss in Forum

Which of the following are incorrect statements ?

(i) A language L is said to be recursively enumerable if there exists a Turing machine that accepts L
(ii) Let K \(\ge\) 1 be an integer. Any K-tape Turing machine cannot be converted to an equivalent one tape Turing machine
(iii) Every computational process which can be considered to be algorithm can be converted to a Turing machine

A.(i) only
B.(ii) only
C.(iii) only
D.(i) and (ii) only

Exam Year(s)

MH SET - 2021, SET Exam - 2021,

Answer: B

Only statement (ii) is incorrect, so the answer is (ii) only.

Statement (ii) is false: for any integer K \(\ge\) 1, a K-tape Turing machine can be converted into an equivalent single-tape Turing machine, which stores the K tapes as tracks on one tape and marks each head position. The simulation is slower, roughly quadratic in time, but accepts the same language.

Statement (i) is the definition of a recursively enumerable language: some Turing machine accepts it. Statement (iii) is the Church-Turing thesis, accepted as true. Options that include (i) or (iii) are therefore wrong.

Discuss in Forum

Loading…

Topics

Other Subjects

Tags: Recursively Enumerable Languages Questions and Answers || Recursively Enumerable Languages MCQ Questions and Answers || Recursively Enumerable Languages GK Questions and Answers || Recursively Enumerable Languages GK MCQ Questions || Recursively Enumerable Languages Multiple Choice Questions and Answers || Recursively Enumerable Languages GK || GK on Recursively Enumerable Languages || Theory of Computation Questions and Answers || Theory of Computation MCQ Questions and Answers || Theory of Computation GK Questions and Answers || GK on Theory of Computation

Recursively Enumerable Languages Questions and Answers

Topics

Other Subjects

About Us

Stay informed about all important Dates & Notifications