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?
1 Answer
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$:
-
$\begingroup$ I upvoted but I must say I would love for this answer to contain drawings of: a DFA with q0 \in F, a DFA with q0 \notin F, and an epsilon-NFA. $\endgroup$– StefNov 19, 2021 at 13:37
-
2$\begingroup$ That would be too much work for me, unfortunately. $\endgroup$ Nov 19, 2021 at 13:38