Test my Merit My Results Create Exam

Higher Study | Theory of Computation | Recursively Enumerable Sets

Which of the following statement(s) is/are FALSE? (i) There exists a recursively enumerable language whose complement is not recursively enumerable. (ii) If a language L is recursive, then its complement is NOT recursive.
What is the minimum number of states required by a Turing Machine to accept strings which consist of even number of 1's?
Which of the following problems is NOT NP-complete? I. Checking satisfiability of arbitrary Boolean formulae II. Checking satisfiability of Boolean formulae in conjunctive normal form (CNF/product of sums) III. Checking satisfiability of Boolean formulae in disjunctive normal form (DNF/sum of products)
Which of the following statement(s) is/are TRUE? (i) The family of context-free languages are the proper subset of the family of regular languages. (ii) The family of recursive languages is a proper subset of the family of recursively enumerable languages.
Which one of the following problems is undecidable?
Which of the following pairs have DIFFERENT expressive power?
Which of the following is/are undecidable? 1. G is a CFG. Is L(G) = Φ? 2. G is a CFG. Is L(G) = Σ*? 3. M is a Turing machine. Is L(M) regular? 4. A is a DFA and N is an NFA. Is L(A) = L(N)?
Which of the following statements is/are FALSE? 1. For every non-deterministic Turing machine, there exists an equivalent deterministic Turing machine. 2. Turing recognizable languages are closed under union and complementation. 3. Turing decidable languages are closed under intersection and complementation. 4. Turing recognizable languages are closed under union and intersection.
Which of the following is FALSE with respect to possible outcomes of executing a Turing Machine over a given input?
Which of the following problems is undecidable ?
Consider the following two statements about regular languages: S1: Every infinite regular language contains an undecidable language as a subset. S2: Every finite language is regular. Which one of the following choices is correct?
Which of the following problem is not NP complete but undecidable?
Let ∑ be a finite non-empty alphabet and let 2∑* be the power set of ∑*. Which one of the following is TRUE?
Let A ≤m B denotes that language A is mapping reducible (also known as many-to-one reducible) to language B. Which one of the following is FALSE?
Suppose a polynomial time algorithm is discovered that correctly computes the largest clique in a given graph. In this scenario, which one of the following represents the correct Venn diagram of the complexity classes P, NP and NP Complete (NPC)?
Ads