How do we decide whether or not to accept $\epsilon$ in dfa?

Question

Can I exclude $\epsilon$? Will that make a difference. This is really confusing me. It seems everything could contain $\epsilon$. Is there some way of thinking to realize this contains $\epsilon$ or not. I was looking at a DFA for $a$ followed by $b$. And it also contained $\epsilon$ which seems confusing to me. That means $\epsilon$ is there everywhere (most cases). Can I ignore it?

Answer 1

A DFA is a tuple $(Q,\Sigma,\delta,q_0,F)$, where $Q$ is a finite set, $\Sigma$ is a non-empty finite set, $\delta$ is a function from $Q \times \Sigma$ to $Q$, $q_0$ is an element of $Q$, and $F$ is a subset of $Q$. We extend $\delta$ to a function $\hat\delta$ from $Q \times \Sigma^*$ to $Q$ as follows: $\hat\delta(q,\epsilon) = q$ and $\hat\delta(q,x\sigma) = \delta(\hat\delta(q,x),\sigma)$. Finally, the language accepted by the DFA is $$ L=\{ w \in \Sigma^* : \hat\delta(q_0,w) \in F. \} $$ In particular, $\epsilon \in L$ iff $\hat\delta(q_0,\epsilon) \in F$ iff $q_0 \in F$.

---

You mention a DFA "containing $\epsilon$". My guess is that you saw an automaton with $\epsilon$ labelling one of the edges. This is a pictorial representation of an $\epsilon$-NFA, a generalization of DFAs which allows such transitions, and whose semantics we skip in this answer.

---

Examples:

A DFA where $q_0\in F$, whose language is the words not containing "ab", which includes $\epsilon$:

A DFA where $q_0\not\in F$, whose language is the words containing "ab", which does not include $\epsilon$:

An $\epsilon$-NFA, whose language is the words containing "a...b" ("ab" as a subsequence), which does not include $\epsilon$: