2
$\begingroup$

Given string w such that every odd position in w is a 1

My solution is

sol1

The book's solution is

sol2

from my understanding $\epsilon$ should not be an accepted state, however in the book's solution it is. How is it handling this case?

$\endgroup$
5
$\begingroup$

Yes, an empty string is a valid input to a DFA. If this were not the case, DFAs would not be closed under all of the Kleene algebra operations.

In this case, the argument is correct. Think of the problem statement as an implication. If $i$ is an odd position, then $S_i$ is 1.

$\endgroup$
  • $\begingroup$ then does that mean the book's answer is wrong? $\endgroup$ – Edqu3 Oct 2 '17 at 2:17
  • 3
    $\begingroup$ @Edqu3 : ​ ​ ​ ​ ​ ​ ​ No. ​ ​ ​ See ​ en.wikipedia.org/wiki/Vacuous_truth . ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ $\endgroup$ – user12859 Oct 2 '17 at 3:48
  • $\begingroup$ @Ricky Demer by that logic the string { } has a 1 in every odd position. $\endgroup$ – Edqu3 Oct 2 '17 at 4:13
  • 1
    $\begingroup$ @Edqu3 : ​ Exactly. ​ ​ ​ ​ $\endgroup$ – user12859 Oct 2 '17 at 4:51

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.