1 Crore+ students have signed up on EduRev. Have you? Download the App 
Let < M > be the encoding of a Turing machine as a string over {0, 1}. Let L = { < M > M is a Turing machine that accepts a string of length 2014 }. Then, L is
Which of the following problems is undecidable?
Consider three decision problems P1, P2 and P3. It is known that P1 is decidable and P2 is undecidable. Which one of the following is TRUE?
Consider two languages L1 and L2 each on the alphabet ∑. Let f : ∑ → ∑ be a polynomial time computable bijection such that (∀ x) [x ∈ L1 iff f(x) ∈ L2]. Further, let f^{1} be also polynomial time computable. Which of the following CANNOT be true?
Consider the following problem X.
Given a Turing machine M over the input alphabet Σ, any state q of M And a word w∈Σ*, does the computation of M on w visit the state q?
Q. Which of the following statements about X is correct?
Consider the following decision problems:
(P1) Does a given finite state machine accept a given string
(P2) Does a given context free grammar generate an infinite number of stings
Q. Which of the following statements is true?
Consider the following statements:
1. The complement of every Turning decidable language is Turning decidable
2. There exists some language which is in NP but is not Turing decidable
3. If L is a language in NP, L is Turing decidable
Q. Which of the above statements is/are True?
Which of the following decision problems are undecidable
Let L be a language and L' be its complement. Which one of the following is NOT a viable possibility?
Let A ≤m B denotes that language A is mapping reducible (also known as manytoone reducible) to language B. Which one of the following is FALSE?
For S ∈ (0 + 1) * let d(s) denote the decimal value of s (e.g. d(101) = 5). Let L = {s ∈ (0 + 1)* d(s)mod5 = 2 and d(s)mod7 != 4}. Which one of the following statements is true?
Let L1 be a recursive language, and let L2 be a recursively enumerable but not a recursive language. Which one of the following is TRUE?
L1' > Complement of L1
L2' > Complement of L2
L1 is a recursively enumerable language over Σ. An algorithm A effectively enumerates its words as w1, w2, w3, ... Define another language L2 over Σ Union {#} as {wi # wj : wi, wj ∈ L1, i < j}. Here # is a new symbol. Consider the following assertions.
S1 : L1 is recursive implies L2 is recursive
S2 : L2 is recursive implies L1 is recursive
Q. Which of the following statements is true ?
Nobody knows yet if P = NP. Consider the language L defined as follows :
Q. Which of the following statements is true ?
A single tape Turing Machine M has two states q0 and q1, of which q0 is the starting state. The tape alphabet of M is {0, 1, B} and its input alphabet is {0, 1}. The symbol B is the blank symbol used to indicate end of an input string. The transition function of M is described in the following table.
Q. The table is interpreted as illustrated below. The entry (q1, 1, R) in row q0 and column 1 signifies that if M is in state q0 and reads 1 on the current tape square, then it writes 1 on the same tape square, moves its tape head one position to the right and transitions to state q1. Which of the following statements is true about M ?
Define languages L0 and L1 as follows :
L0 = {< M, w, 0 >  M halts on w}
L1 = {< M, w, 1 >  M does not halts on w}
Here < M, w, i > is a triplet, whose first component. M is an encoding of a Turing Machine, second component, w, is a string, and third component, i, is a bit. Let L = L0 ∪ L1. Which of the following is true ?
For any two languages L1 and L2 such that L1 is context free and L2 is recursively enumerable but not recursive, which of the following is/are necessarily true?
1. L1' (complement of L1) is recursive
2. L2' (complement of L2) is recursive
3. L1' is contextfree
4. L1' ∪ L2 is recursively enumerable
Let X be a recursive language and Y be a recursively enumerable but not recursive language. Let W and Z be two languages such that Y' reduces to W, and Z reduces to X' (reduction means the standard manyone reduction). Which one of the following statements is TRUE
Consider the following types of languages:
L1 Regular,
L2: Contextfree,
L3: Recursive,
L4: Recursively enumerable.
Q. Which of the following is/are TRUE?
I. L3' U L4 is recursively enumerable
II. L2 U L3 is recursive
III. L1* U L2 is contextfree
IV. L1 U L2' is contextfree
150 docs216 tests

150 docs216 tests
