Bissoy.com
Doctors Medicines MCQs Q&A

What is the minimum number of states required by a Turing Machine to accept strings which consist of even number of 1's?

What is the minimum number of states required by a Turing Machine to accept strings which consist of even number of 1's? Correct Answer 2

The correct answer is option 3.

Concept:

The given problem is an even number of 1's.

It accepts the 2 states for DFA.

[ alt="F1 Harshita11-2-22 Savita D20" src="//storage.googleapis.com/tb-img/production/22/02/F1__Harshita11-2-22_Savita_D20.png" style="width: 255px; height: 126px;">

 

A Turing Machine must have at least two states:

one that accepts input and one that rejects it. Because the machine cannot accept and reject at the same time, the accepting and rejecting states must be separate. As a result, at least two states are required.

You can't accept anything when you're in a single state. The transition of a Turing Machine is (X, Y, R/L). With a single state, you'll have to define at least one transition, which will almost certainly contain R/L. As a result, the Turing Machine will never cease moving, either right or left or oscillating between the two.

[ alt="F1 Harshita11-2-22 Savita D21" src="//storage.googleapis.com/tb-img/production/22/02/F1__Harshita11-2-22_Savita_D21.png" style=" width: 256px; height: 119px;">

Hence the correct answer is 2.

Related Questions

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.
Consider the following statements. I. The complement of every Turing decidable language is Turing decidable II. There exists some language which is in NP but is not Turing decidable III. If L is a language in NP, L is Turing decidable Which of the above statements is/are true?
There are two rows, each containing 3 numbers. Below are some rules to be used to get the resultant number for each row separately. Use the rule from left to right for each row and find the answer to the question. Rule: 1. If an even number is followed by an even number, then the first number will be subtracted from the second. 2. If an odd number is followed by an odd number, then both will be added. 3. If an odd number is followed by an even number, then the even number will be subtracted from the square of the odd number. 4. If an even number is followed by an odd number, then the odd number will be subtracted from the even number. Row I: 9,11, 34 Row II: 16, 9, 8 What is the difference between the resultant numbers in the first row and the second row
There are two rows, each containing 3 numbers. Some rules are given below to be used for obtaining the resultant number for each row separately. Apply the rules for each row from left to right and answer the question. Rules: i. If an even number is followed by an even number, the first is to be subtracted from the second. ii. If an odd number is followed by an odd number, both are to be added. iii. If an odd number is followed by an even number, the even number is to be subtracted from the square of the odd number. iv. If an even number is followed by an odd number, the odd number is to be subtracted from the even number. Row I: 28, 19, 12 Row II: 13, 7, 32 What is the average of the resultant numbers of the first row and the second row?
A suit, a trouser, and a shirt are to be stitched from a cloth. The cloth required for the suit is the average of cloth required for trousers and shirt. The length of the cloth for suit is 1.5 times the cloth required for the shirt. The length of cloth required for shirt is 5 times the even prime number. Which of the following is/are correct? A. Cloth required for trousers is 20 m B. Average length of cloth required for all the dresses = Cloth required for suit C. Initially, the cloth was 45 m D. Cloth required for shirt is 15 m
Consider the following statements : A = If n is even, then n2 is even. B = If n2 is not even, n is not even. C = If n2 is even, then n is even. D = If n is not even, then n2 is not even. Which of the following statements is true?
In the question two statements are given, followed by two conclusions, I and II. You have to consider the statements to be true even if it seems to beat variance from commonly known facts. You have to decide which of the given conclusions, if any, follows from the given statements. Statement I: All threads are strings. Statement II: All fibres are threads. Conclusion I: All strings are fibres. Conclusion II: All fibres are strings.
In the question two statements are given, followed by two conclusions, I and II. You have to consider the statements to be true even if it seems to beat variance from commonly known facts. You have to decide which of the given conclusions, if any, follows from the given statements. Statement I: All threads are strings Statement II: All fibres are threads Conclusion I: All strings are fibres Conclusion II: All fibres are strings
Let L(R) be the language represented by regular expression R. Let L(G) be the language generated by a context free grammar G. Let L(M) be the language accepted by a Turing machine M. Which of the following decision problems are undecidable? I. Given a regular expression R and a string w, is w ∈ L(R)? II. Given a context-free grammar G, is L(G) = ϕ? III. Given a context-free grammar G, is L(G) = ∑* for some alphabet ∑? IV. Given a Turing machine M and a string w, is w ∈ L(M)?  
State true or false: Statement: Two track turing machine is equivalent to a standard turing machine.