Which of the following problems is/are decidable problem(s) (recursively enumerable) on turing M machine ? G L(G) = ϕ
(a) is a CFG with M M
(b) There exist two TMs 1 and 2 such that L(M) ⊆ {L (M ) ∪ L (M )} = 1 2 language of TMs all ω 2|ω|
(c) M is a TM that accepts using at most cells of tape
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: C. (a), (b) and (c)
Explanation
CFG emptiness is decidable, and a TM restricted to 2|ω| tape cells is linearly bounded, so its acceptance is decidable. The official key accepts all three.
More Theory of Computation and Compilers questions
- For a statement L ⊆ Σ∗ A language is recursive if there exists M some turing machine . Which of the following conditions is satisfied for ω…
- Let r = a(a + b)*, s = aa*b and t = a*b be three regular expressions. Consider: (i) L(s) ⊆ L(r) and L(s) ⊆ L(t) (ii) L(r) ⊆ L(s) and L(s) ⊆…
- Consider the language L = {a^(nk) | k > 0}, where n is a fixed non-negative integer. The minimum number of states of a finite automaton acc…
- The number of substrings that can be formed from a string given by a d e f b g h n m p is
- Consider the languages L₁ = {x | for some y with |y| = 2|x|, xy ∈ L} and L₂ = {x | for some y with |x| = |y|, xy ∈ L}, where L is a regular…
- Consider L₁ = {a^(n+m) bⁿ aᵐ | n, m ≥ 0} and L₂ = {a^(n+m) b^(n+m) a^(n+m) | n, m ≥ 0}. Which one is correct?