Exams › GATE › Technical
Let \(<M>\) be the encoding of a Turing machine as a string over \(\Sigma = \{0,1\}\). Let \(L = \{<M> \mid M\text{ is a Turing machine that accepts a string of length }2014\}\). Then, \(L\) is
- decidable and recursively enumerable
- undecidable but recursively enumerable
- decidable and not recursively enumerable
- decidable but not recursively enumerable
Correct answer: decidable and recursively enumerable
Solution
To decide membership in L, enumerate all strings of length 2014 and simulate M on each one. If M accepts at least one such string, accept; otherwise reject. Since the set of candidate strings is finite, the language is decidable, and every decidable language is recursively enumerable.
Related GATE Technical questions
- Consider the following context-free grammar where the set of terminals is {a, b, c, d, f}: S → daT | Rf T → aS | baT | ε R → caTR | ε Which of the following is correct?
- For a Turing machine $M$, $\langle M\rangle$ denotes an encoding of $M$. Consider the following two languages: $L_1=\{\langle M\rangle \mid M$ takes more than 2021 steps on all inputs$\}$ $L_2=\{\langle M\rangle \mid M$ takes more than 2021 steps on some input$\}$
- Consider the 5-state DFA $M$ accepting the language $L(M)=(0+1)^*$. For any string $w\in(0+1)^*$, let $n_0(w)$ be the number of 0s in $w$ and $n_1(w)$ be the number of 1s in $w$. Which of the following statements is/are FALSE?
- A regular language $L$ is accepted by a nondeterministic finite automaton (NFA) with $n$ states. Which of the following statement(s) is/are FALSE?
- Consider the following two languages over the alphabet \(\{a,b\}\): \[ L_1=\{\alpha\beta\alpha \mid \alpha\in\{a,b\}^* \text{ and } \beta\in\{a,b\}^+\} \] \[ L_2=\{\alpha\beta\alpha \mid \alpha\in\{a\}^* \text{ and } \beta\in\{a,b\}^+\} \] Which ONE of the following statements is CORRECT?
- Consider the following languages over the alphabet \(\{a,b,c\}\), where \(m\) and \(n\) are natural numbers: \[ L_1=\{a^m b^m c^{m+n} \mid m,n\ge 1\} \] \[ L_2=\{a^m b^n c^{m+n} \mid m,n\ge 1\} \] Which ONE of the following statements is CORRECT?
⚔️ Practice GATE Technical free + battle 1v1 →