Computer Sciences > Gate 2022 > Automata
Which of the following is/are undecidable?
A
Given two Turing machines M1and 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.

Correct : a,b,c

Similar Questions

Consider the 5-state DFA M accepting the language L(M) ⊂ (0 + 1)* shown below. For any string w ∈ (0 + 1)* let n0(w) be the number of 0′s in w and n1(w) be the...
#886 MSQ
Which one of the following regular expressions is equivalent to the language accepted by the DFA given below?
#910 MCQ
Let L ⊆ {0,1}* be an arbitrary regular language accepted by a minimal DFA with k states. Which one of the following languages must necessarily be accepted...
#1074 MCQ

Related Topics

Turing machines problems GATE computer science 2022 Turing machine decidability undecidable problems regular language Turing complexity theory gate Turing machine acceptance Turing steps computation

Unique Visitor Count

Total Unique Visitors

Loading......

Question Options

Contributed by: