1
GATE CSE 2026 Set 2
MCQ (Single Correct Answer)
+1
-0

Which one of the following statements is equivalent to the following assertion?

Turing machine $M$ decides the language $L \subseteq\{0,1\}$.

A

Turing machine $M$ halts on all input strings in $\{0,1\}^*$

B

Turing machine $M$ accepts all input strings in $L$

C

Turing machine $M$ rejects all input strings in $\{0,1\}^*-L$

D

Turing machine $M$ accepts all input strings in $L$ and rejects all input strings in $\{0,1\}^*-L$

2
GATE CSE 2026 Set 2
MCQ (More than One Correct Answer)
+1
-0

Which of the following grammars is/are ambiguous?

A

$S \rightarrow a S b \mid \in$

B

$E \rightarrow E+E|E * E|$ id

C

$S \rightarrow a S|S a| \in$

D

$S \rightarrow a S \mid \in$

3
GATE CSE 2026 Set 2
MCQ (More than One Correct Answer)
+2
-0

Consider the following two finite automata $D_1$ and $D_2$.GATE CSE 2026 Set 2 Theory of Computation - Finite Automata and Regular Language Question 1 English

Which of the following statements is/are true?

A

$\angle\left(D_1\right)=\angle\left(D_2\right)$

B

$\angle\left(D_1\right)$ is a proper subset of $\angle\left(D_2\right)$

C

$\angle\left(D_1\right) \cap L\left(D_2\right)=\{\in\}$

D

$\left(L\left(D_1\right) \cup L\left(D_2\right)\right)^*$ consists of all strings in $\{0,1\}^*$ whose length is divisible by 3 .

4
GATE CSE 2026 Set 2
MCQ (More than One Correct Answer)
+2
-0

Let $\Sigma=\{a, b, c, d\}$ and let $L=\left\{a^i b^j c^k d^l \mid i, j, k, l \geq 0\right\}$.

Which of the following constraints ensure(s) that the language $L$ is context-free?

A

$i+k=j+l$

B

$i=k$ and $j=l$

C

$i=l$ and $j=k$

D

$i+j=k+l$