GATE CS 2022 Question 3: Undecidable Problems of Turing Machines

```

Computer Sciences > Gate 2022 > Automata

Which of the following is/are undecidable?

A

Given two Turing machines M₁and M₂, decide if L(M₁)=L(M₂).

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 &sube; {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

No tags found

Unique Visitor Count

Total Unique Visitors

Loading......