1 Crore+ students have signed up on EduRev. Have you? Download the App 
Let M be a Turing Machine has Q = (q_{0}, q_{1}, q_{2}, q_{3}, q_{4}} a set of states, input alphabets {0, 1}. The tape alphabets are {0,1, B, X, V). The symbol B is used to represent end of input string. The final state is q_{4}. The transistions are as follows:
Which of the following is true about M?
If L_{1} and L_{2} are a pair of complementary languages. Which of the following statement is not possible?
Consider the following statements about L:
(i) L is accepted by multitape turing machine M_{1}.
(ii) L is also accpted by a single tape turing machine M_{2}.
Which of the following statement is correct?
A TM M The transition are
What is the laugnage accepted by TM?
Referring to Turing Machine in previous question, what will be the output when the input is
I_{1} = 0100 and I_{2} = 0010?
Nobody knows yets if p = NP consider the language L defined as follows:
Which of the following statement is true?
If the strings of a language L can be effectively enumerated in lexicographic (i.e. alphabetic) order which of the following statements is true?
he diagnoalization language, L_{d} is a
Time taken by one tape TM to simulate n moves of ktape TM is
Consider the transition table of a TM given below. Here "b" represents the blank symbol.
Q. Which of the following strings will not accepted?
The given turing machine accepts
Ram and Shyam have been asked to show that a cartain problem II is NPcomplete. Ram shows a polynomial time reduction from the 3SAT problem to II and Shyam shows a polynomial time reduction from II to 3SAT. Which of the following can be inferred from these reductions?
Which of the following is true?
Both P and NP are closed under the operation of
L ∈ NP does not obviously imply that
18 videos56 docs44 tests

18 videos56 docs44 tests
