1 Crore+ students have signed up on EduRev. Have you? 
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?
Drawing the equivalent turing machine we have
This is a standard turing machine program for
If L_{1} and L_{2} are a pair of complementary languages. Which of the following statement is not possible?
The correct statement follows from following theorem:
Theorem: If L_{1} and L_{2} is a pair of complementary language then either
• Both L_{1} and L_{2} are recursive.
• Neither L_{1}, and L_{2} are recursively enumerable.
• One is recursively enumerable but not recursive, the other is not RE.
Option (b) is not possible, since if L_{1} is recursive, then will also be recursive.
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?
While simulating multitape TM on a single tape TM, the head has to move at least 2k cells per move, where k is the number of tracks on single tape TM. Thus for k moves, we get
which means quadratic slow down. Thus, acceptance by singletape is slower by 0(n^{2}).
A TM M The transition are
What is the laugnage accepted by TM?
The analysis of transition of TM, M shows that is accepts language 0*10*.
Referring to Turing Machine in previous question, what will be the output when the input is
I_{1} = 0100 and I_{2} = 0010?
The Turing Machine carries out the functions of ( m  n) in (0^{m} 10^{n}).
• When m≥n, the output is difference between m and n.
• when m < n, the output is blank.
Nobody knows yets if p = NP consider the language L defined as follows:
Which of the following statement is true?
L = (0 + 1 )* or {}. A trivial TM which accepts all words or another which rejects all. One of these two TMs will surely accept this language. So L is recursive.
If the strings of a language L can be effectively enumerated in lexicographic (i.e. alphabetic) order which of the following statements is true?
L is recursive iff L is enumerable in Lexicographic order (alphabetic).
It is also known that context free language is a subset of recursive languages.
he diagnoalization language, L_{d} is a
Time taken by one tape TM to simulate n moves of ktape TM is
Single tape turing machine can simulate nmoves of ktape TM in O(n^{2}).
Consider the transition table of a TM given below. Here "b" represents the blank symbol.
Q. Which of the following strings will not accepted?
Hence, not accepted.
Hence, also not accepted.
The given turing machine accepts
It can be observed from the image that this machine will accept only those strings which contains even number of 1’s. And strings with odd number of 1 ’s are rejected.
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?
Since 3SAT problem is NPcomplete and 3SAT is polynomial time reducible to π hence π is is also NPcomplete.
Which of the following is true?
Both P and NP are closed under the operation of
P and NP language are closed under union, intersection, kleene closure and concatenation, P is close under complement also while closure of NP under complement is still unsolved problem.
L ∈ NP does not obviously imply that
L ∈ NP does not imply that L' ∈ NP. Since closure of NP under complementation is as yet unresolved problem. Also L ∈ NP does not imply L' ∈ P, unless L ∈ P, which may or may not be so.
61 videos7 docs102 tests

Use Code STAYHOME200 and get INR 200 additional OFF

Use Coupon Code 
61 videos7 docs102 tests








