0
$\begingroup$

I had a question that asked for the DFA that accepts the following language:

{w | every odd position of w is a 0 }

Should this DFA accept the empty string, since it doesn't have an odd position?

$\endgroup$
  • 1
    $\begingroup$ "Should this DFA accept the empty string, since it doesn't have an odd position?" - Yes. The condition vacuously holds. $\endgroup$ – Guildenstern Mar 18 '15 at 13:46
  • 1
    $\begingroup$ $\forall x \in \emptyset : P(x)$ holds for all predicates $P$. $\endgroup$ – Raphael Mar 18 '15 at 14:19
2
$\begingroup$

Yes, since $|\epsilon| = 0$, there are no odd positions; therefore, that DFA would accept $\epsilon$.

$\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.