714 views
1 votes
1 votes
Which of the following statements is Decidable?

S1: The set of all TM's that given an input eventually write a non blank symbol on their tapes

S2: The set of all TM's that given an input visits an arbitrary state q

(A). S1 only

(B). S2 only

(C). Both

(D). None

Please log in or register to answer this question.

Related questions

0 votes
0 votes
0 answers
1
baofbuiafbi asked Nov 14, 2023
151 views
Prove the language L={(G,H)|G is a CFG, H is a DFA, and L(G)∩L(H)=∅} is undecidable.