Part A)
Prove that the following language is decidable: Input: The description of a DFA A.
Output:
YES if A accepts the empty string.
NO if A does not accept the empty string.
I am struggling with how to prove this, or even what would count as proving this question.
My thinking for part A is currently,for a given Turing Machine the language will always halt because the input will either accept or reject the empty string by definition of DFA. So… DFA A will either accept the empty string or reject the empty string, but regardless the Turing Machine that represents the language will halt. Do I even need to be discussing turing machines in part a?
Honestly not sure if my thinking is at all on the right path…
S.O.S
Best Answer
Your attempt to answer is a bit hard to read, but the key elements for the right answer are already there:
The DFA will always halt on the empty string as input (as on any other). Therefore also a simulation of this DFA by the Turing Machine will come to an end. So you can let the Turing Machine simulate the DFA in the input and then check, whether the DFA has accepted or not. Since the FA is deterministic there is only one computation to simulate and the answer is definite. For NFAs you would have to simulate all possible paths in the worst case.
This approach works for any string. As you have observed correctly in the comments, the empty string is accepted only if the start state is an accepting one. Thus in your case the simulation consists only in checking whether the DFA's start state is accepting. The technical details depend on the way in which the DFA is encoded on the TM-tape.