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


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

A DFA containing epsilon

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

A DFA not containing epsilon

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

An epsilon-NFA not containing 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$
    – Stef
    Nov 19, 2021 at 13:37
  • 2
    $\begingroup$ That would be too much work for me, unfortunately. $\endgroup$ Nov 19, 2021 at 13:38

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.