The dragon book lists properties of an NFA N(r) created using Thompson's construction, in particular:

  1. Each state of N(r) other than the accepting state has either one outgoing transition on a symbol in Σ or two outgoing transitions, both on ϵ.

However, the same book shows NFAs created using Thompson's construction that seem to contradict that very statement, like this one:

Figure 3.44: NFA for r3

Here, nodes 3 and 5, which are not accepting states, have only one outgoing ϵ transition each. What am I missing?

  • 1
    $\begingroup$ Yes, I think they made a small mistake here, as the rules both for converting $\epsilon$ and a union of two expressions explicitly state that they include states with one $\epsilon$-transition to the accepting state. They probably should have said "Each state ... has either one outgoing transition in $\Sigma\cup\{\epsilon\}$ ...". $\endgroup$
    – Highheath
    Jun 22, 2023 at 12:28

1 Answer 1


Thanks @Highheath in the comments, you are right.

At first I found it hard to believe that I should be the first one to have found such an error in the 36+ years since this - apparently very popular - book is out. It is in its second edition since 2008, but I would have expected this part to have been in the first edition as well.

Be that as it may, the error shows up in the errata:



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.