Consider the following statements : S
1 : These exists no algorithm for deciding if any M M two Turing machines 1 and 2 accept the same language. S M M
2 : Let 1 and 2 be arbitrary Turing ⊆ L (M ) machines. The problem to determine 2 is undecidable. Which of the statements is (are) correct? S
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: C. Both 1 and 2 S S
Explanation
Equivalence of two TMs' languages and containment L(M1) ⊆ L(M2) are both undecidable (Rice's theorem).
More Theory of Computation and Compilers questions
- Let A = {001, 0011, 11, 101} and B = {01, 111, 111, 010}; C = {00, 001, 1000} and D = {0, 11, 011}. Which pairs have a Post correspondence…
- Which data structure is used by the compiler for managing variables and their attributes?
- On translating the expression given below into quadruple representation, how many operations are required? (i*j)+(e+f)*(a*b+c)
- Replacing the expression by 8.56 is known as
- Shift-reduce parser consists of (a) input buffer (b) stack (c) parse table
- How many states are there in a minimum state automata equivalent to regular expression given below? a * b(a + b) Regular expression is