4. (10 pts) Consider the problem of testing whether a machine has a redundant state, that...

  

Transcribed Image Text:

4. (10 pts) Consider the problem of testing whether a machine has a redundant state, that is, one that is not reachable on any input string. Assume the alphabet is 0, 1, convert this problem into a problem of testing membership in a language and determine whether the the language is decidable, undecidable, T-recognizable, co-T-recognizable, not T-recognizable: (a) Does a DFA have a redundant state? (b) Does a TM have a redundant state? 4. (10 pts) Consider the problem of testing whether a machine has a redundant state, that is, one that is not reachable on any input string. Assume the alphabet is 0, 1, convert this problem into a problem of testing membership in a language and determine whether the the language is decidable, undecidable, T-recognizable, co-T-recognizable, not T-recognizable: (a) Does a DFA have a redundant state? (b) Does a TM have a redundant state?

Answer rating: 100% (QA)

Step 13 a Does a DFA have a redundant state To convert this problem in to a problem of testing membership in a language we can define a language L tha... View the full answer