# Theory of Computation

 Question 1
Consider the following languages:

\begin{aligned} L_1&= \{ ww|w \in \{a,b \}^* \} \\ L_2&= \{a^nb^nc^m | m,n \geq 0 \} \\ L_3 &= \{a^mb^nc^n|m,n \geq 0 \} \end{aligned}

Which of the following statements is/are FALSE?
MSQ
 A $L_1$ is not context-free but $L_2$ and $L_3$ are deterministic context-free. B Neither $L_1$ nor $L_2$ is context-free. C $L_2,L_3$ and $L_2 \cap L_3$ all are context-free. D Neither $L_1$ nor its complement is context-free.
GATE CSE 2022      Context Free Language
Question 1 Explanation:
 Question 2
Consider the following languages:

\begin{aligned} L_1&= \{a^n wa^n|w \in \{a,b \}^* \} \\ L_2&= \{wxw^R | w,x \in \{a,b \}^*, |w|,|x| \gt 0 \} \end{aligned}

Note that $w^R$ is the reversal of the string $w$. Which of the following is/are TRUE?
MSQ
 A $L_1$ and $L_2$ are regular. B $L_1$ and $L_2$ are context-free. C $L_1$ is regular and $L_2$ is context-free. D $L_1$ and $L_2$ are context-free but not regular.
GATE CSE 2022      Context Free Language
Question 2 Explanation:
 Question 3
Which of the following is/are undecidable?
MSQ
 A Given two Turing machines M1 and M2 , decide if L(M1 ) = L(M2 ). B Given a Turing machine M , decide if L(M ) is regular. C Given a Turing machine M , decide if M accepts all strings. D Given a Turing machine M , decide if M takes more than 1073 steps on every string.
GATE CSE 2022      Turing Machine
Question 3 Explanation:
 Question 4
Which of the following statements is/are TRUE?
MSQ
 A Every subset of a recursively enumerable language is recursive. B If a language $L$ and its complement $\bar{L}$ are both recursively enumerable, then $L$ must be recursive. C Complement of a context-free language must be recursive. D If $L_1$ and $L_2$ are regular, then $L_1 \cap L_2$must be deterministic context-free.
GATE CSE 2022      Recursive Language
Question 4 Explanation:
 Question 5
Which one of the following regular expressions correctly represents the language of the finite automaton given below?

 A ab*bab* + ba*aba* B (ab*b)*ab* + (ba*a)*ba* C (ab*b + ba*a)*(a* + b*) D (ba*a + ab*b)*(ab* + ba*)
GATE CSE 2022      Finite Automata
Question 5 Explanation:
 Question 6
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 6 Explanation:
 Question 7
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 7 Explanation:
 Question 8
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 8 Explanation:
 Question 9
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 9 Explanation:
 Question 10
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 10 Explanation:

There are 10 questions to complete.

### 1 thought on “Theory of Computation”

1. Two options of Q15 are the same.