1
GATE CSE 2003
MCQ (Single Correct Answer)
+2
-0.6
Consider the following deterministic finite state automation $$M.$$ GATE CSE 2003 Theory of Computation - Finite Automata and Regular Language Question 23 English

Let $$S$$ denote the set of seven bit binary strings in which the first, the fourth, and the last bits are $$1$$. The number of strings in $$S$$ that are accepted by $$M$$ is

A
$$1$$
B
$$5$$
C
$$7$$
D
$$8$$
2
GATE CSE 2003
MCQ (Single Correct Answer)
+1
-0.3
Nobody knows yet if $$P=NP$$. Consider the language $$L$$ defined as follows
$$L = \left\{ {\matrix{ {{{\left( {0 + 1} \right)}^ * }\,\,\,if\,\,P = NP} \cr {\,\,\,\,\,\,\,\phi \,\,\,\,Otherwise} \cr } } \right.$$

Which of the following statement is true?

A
$$L$$ is recursive
B
$$L$$ is recursively enumerable but not recursive
C
$$L$$ is not recursively enumerable
D
Whether $$L$$ is recursive or not will be known after we find out if $$P=NP.$$
3
GATE CSE 2003
MCQ (Single Correct Answer)
+1
-0.3
If the strings of a language $$L$$ can be effectively enumerated in lexicographic (i.e., alphabetic$$(c)$$ order, which of the following statements is true?
A
$$L$$ is necessarily finite
B
$$L$$ is regular but not necessarily finite
C
$$L$$ is context free but not necessarily regular
D
$$L$$ is recursive but not necessarily context free
4
GATE CSE 2003
MCQ (Single Correct Answer)
+2
-0.6
A single tape Turing Machine $$M$$ has two states $${q_0}$$ and $${q_1}$$, of which $${q_0}$$ is the starting state. The tape alphabet of $$M$$ is $$\left\{ {0,\,\,1,\,\,B} \right\}$$ and its input alphabet is $$\left\{ {0,\,\,1} \right\}$$. 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. GATE CSE 2003 Theory of Computation - Recursively Enumerable Language and Turing Machine Question 21 English

The table is interpreted as illustrated below. The entry $$\left( {{q_1},1,\,R} \right)$$ in row $${{q_0}}$$ and column $$1$$ signifies that if $$M$$ is in state $${{q_0}}$$ 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 $${{q_1}}$$.

Which of the following statements is true about $$M?$$

A
$$M$$ does not halt on any string in $${\left( {0 + 1} \right)^ + }$$
B
$$M$$ does not halt on any string in $${\left( {00 + 1} \right)^ + }$$
C
$$M$$ halts on all string ending in a $$0$$
D
$$M$$ halts on all string ending in $$a$$
EXAM MAP
Medical
NEET
Graduate Aptitude Test in Engineering
GATE CSEGATE ECEGATE EEGATE MEGATE CEGATE PIGATE IN
CBSE
Class 12