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

1 Answer 1

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 and acknowledge you have read our privacy policy.

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