1
GATE CSE 2003
+2
-0.6
Consider the following deterministic finite state automation $$M.$$

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
+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
+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
+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.

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$$
GATE CSE Papers
2023
2022
2020
2019
2018
2013
2012
2011
2010
2009
2008
2007
2006
2005
2004
2003
2002
2001
2000
1999
1998
1997
1996
1995
1994
1993
1992
1991
1990
1989
1988
1987
EXAM MAP
Medical
NEET