0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Given a DFA, can you think of a way to check whether it accepts the empty string? $\endgroup$ – mrp Apr 14 at 20:05
  • $\begingroup$ uhh... if the start state is an accept state? $\endgroup$ – csstudent9030 Apr 14 at 20:19
  • $\begingroup$ So with that in mind, how can you make an algorithm that, given a DFA, determines whether or not that DFA accepts the empty string? $\endgroup$ – mrp Apr 15 at 6:51
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.