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
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
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

Related Topics

No tags found

Unique Visitor Count

Total Unique Visitors

Loading......
Question Options

Contributed by: