# Theory of Computation

 Question 1
Which of the following regular expressions represent(s) the set of all binary numbers that are divisible by three? Assume that the string $\epsilon$ is divisible by three.
[MSQ]
 A $(0+1(01^*0)^*1)^*$ B $(0+11+10(1+00)^*01)^*$ C $(0^*(1(01^*0)^*1)^*)^*$ D $(0+11+11(1+00)^*00)^*$
GATE CSE 2021 SET-2      Regular Expression
Question 1 Explanation:
 Question 2
For a string $w$, we define $w^R$ to be the reverse of $w$. For example, if $w=01101$ then $w^R=10110$.
Which of the following languages is/are context-free?
[MSQ]
 A $\{ wxw^Rx^R \mid w,x \in \{0,1\} ^* \}$ B $\{ ww^Rxx^R \mid w,x \in \{0,1\} ^* \}$ C $\{ wxw^R \mid w,x \in \{0,1\} ^* \}$ D $\{ wxx^Rw^R \mid w,x \in \{0,1\} ^* \}$
GATE CSE 2021 SET-2      Context Free Language
Question 2 Explanation:
 Question 3
Consider the following two statements about regular languages:

S1: Every infinite regular language contains an undecidable language as a subset.
S2: Every finite language is regular.

Which one of the following choices is correct?
 A Only S1 is true B Only S2 is true C Both S1 and S2 are true D Neither S1 nor S2 is true
GATE CSE 2021 SET-2      Regular Language
Question 3 Explanation:
 Question 4
Suppose we want to design a synchronous circuit that processes a string of 0's and 1's. Given a string, it produces another string by replacing the first 1 in any subsequence of consecutive 1's by a 0. Consider the following example.

$\begin{array}{ll} \text{Input sequence:} & 00100011000011100 \\ \text{Output sequence:} & 00000001000001100 \end{array}$

A Mealy Machine is a state machine where both the next state and the output are functions of the present state and the current input.
The above mentioned circuit can be designed as a two-state Mealy machine. The states in the Mealy machine can be represented using Boolean values 0 and 1. We denote the current state, the next state, the next incoming bit, and the output bit of the Mealy machine by the variables s, t, b and y respectively.
Assume the initial state of the Mealy machine is 0.

What are the Boolean expressions corresponding to t and y in terms of s and b?
 A t=s+by=sb B t=by=sb C t=by=s$\bar{b}$ D t=s+by=s$\bar{b}$
GATE CSE 2021 SET-2      Finite Automata
Question 4 Explanation:
 Question 5
Consider the following deterministic finite automaton (DFA)

The number of strings of length 8 accepted by the above automaton is _________
 A 32 B 256 C 64 D 512
GATE CSE 2021 SET-2      Finite Automata
Question 5 Explanation:
 Question 6
Let $L_1$ be a regular language and $L_2$ be a context-free language. Which of the following languages is/are context-free?
[MSQ]
 A $L_1 \cap \overline{L_2}$ B $\overline{\overline{L_1} \cup \overline{L_2}}$ C $L_1 \cup (L_2 \cup \overline{L_2})$ D $(L_1 \cap L_2) \cup (\overline{L_1} \cap L_2)$
GATE CSE 2021 SET-2      Context Free Language
Question 6 Explanation:
 Question 7
Let $L \subseteq \{0,1\}^*$ be an arbitrary regular language accepted by a minimal DFA with k states. Which one of the following languages must necessarily be accepted by a minimal DFA with k states?
 A $L - \{01\}$ B $L \cup \{01\}$ C $\{0,1\}^* -L$ D $L \cdot L$
GATE CSE 2021 SET-2      Regular Language
Question 7 Explanation:
 Question 8
In a pushdown automaton $P=(Q, \Sigma, \Gamma, \delta, q_0, F)$, a transition of the form,

where $p,q \in Q \; a \in \sigma \cup \{ \epsilon \} ,\;X,Y, \in \Gamma \cup \{ \epsilon \}$, represents

$(q,Y) \in \delta(p,a,X)$

Consider the following pushdown automaton over the input alphabet $\Sigma = \{a,b\}$ and stack alphabet $\Gamma = \{ \#, A\}$.

The number of strings of length 100 accepted by the above pushdown automaton is ___________
 A 50 B 49 C 101 D 100
GATE CSE 2021 SET-1      Push-down Automata
Question 8 Explanation:
 Question 9
For a Turing machine M, < M > denotes an encoding of M. Consider the following two languages.

$\begin{array}{ll} L1 = \{ \langle M \rangle \mid M \text{ takes more than } 2021 \text{ steps on all inputs} \} \\ L2 = \{ \langle M \rangle \mid M\text{ takes more than } 2021 \text{ steps on some input} \} \end{array}$

Which one of the following options is correct?
 A Both L1 and L2 are decidable. B L1 is decidable and L2 is undecidable. C L1 is undecidable and L2 is decidable. D Both L1 and L2 are undecidable.
GATE CSE 2021 SET-1      Turing Machine
Question 9 Explanation:
 Question 10
Consider the following language:

$L= \{ w \in \{0,1\}^* \mid w \text{ ends with the substring } 011 \}$

Which one of the following deterministic finite automata accepts $L$?

 A A B B C C D D
GATE CSE 2021 SET-1      Finite Automata
Question 10 Explanation:

There are 10 questions to complete.