# Thompson's construction, transforming a regular expression into an equivalent NFA

There is this case of concatenation that says (from wikipedia):

The initial state of N(s) is the initial state of the whole NFA. The final state of N(s) becomes the initial state of N(t). The final state of N(t) is the final state of the whole NFA. My question is, does this mean that the final state of N(s) is linked to the initial state of N(t) with an edge labeled ε ?

• Yes, they are linked by epsilon edge. – fade2black Jun 8 '17 at 0:02
• No epsilon needed, the final state of N(s) is the initial state of N(t). Check the example on the Wiki page. – ryan Jun 8 '17 at 6:11

You can do concatenation with an epsilon transition, but it is not necessary. Many implementations avoid it because concatenations are common and the epsilon transitions significantly increase the machine size.

There is some​ nice code in Russ Cox's famous essay on regular expressions, which implements a common strategy: fragment machines are built without any endpoint. Instead, the fragment descriptor contains a list of states in the fragment which would have a transition to the endpoint if there were one. In this way, two fragments can be concatenated by backpatching the second fragment's start state number as the head (target) of all outgoing transitions from the states in the first fragment's endpoint list.

You will find real code (in C) in the linked essay; search for the heading starting "Implementation"

There is no need for an epsilon transition, it is a waste of space.

For a regular expression $E$, with resulting automaton $A$, must respect these properties of the transition function, $\delta$:

1. $A$ has exactly one initial state $q_0$, which is not accessible$^{*}$ from any state. That is, $$\delta(q, a) \neq q_0 \quad \forall q \in A, \forall a \in \Sigma$$

2. $A$ has exactly one final state $q_f$, which is not co-accessible$^{**}$ to any state. That is, $$\delta(q_f, a) = \emptyset \quad \forall a\in \Sigma$$

These two points are important. The initial state has no transitions into it, and the final state has no transitions out of it. This means we have no "merge conflicts", as it were.

Let $F$ be the set of all states co-accessible to the final state of $N(s)$, $s_f$.

Let $T$ be the set of all states accessible from the initial state of $N(t)$, $t_0$.

We then have the two states $s_f$ and $t_0$ and their transitions like so:

\begin{align} F \rightarrow & s_f \rightarrow \emptyset \\ \emptyset \rightarrow &t_0 \rightarrow T \\ \end{align}

You can see how merging the two creates no conflicts or discrepancies:

\begin{align} F \cup \emptyset \rightarrow & s_ft_0 \rightarrow \emptyset \cup T \\ F \rightarrow & s_ft_0 \rightarrow T \\ \end{align}

$^{*}$ A state $q$ of $A$ is accessible from a state $p$ if there is a computation in $A$ whose source is $p$ and whose destination is $q$. A state $q$ is accessible if it is accessible from an initial state.

$^{**}$ A state $p$ of $A$ is co-accessible to a state $q$ if there is a computation in $A$ whose source is $p$ and whose destination is $q$. A state $p$ is co-accessible if it is co-accessible to a final state.

Yes it is! But the final state of N(s) is no longer final

• As the other answer explains, the diagram actually means that the final state of the first automaton is identified with the initial state of the second. You could add an $\varepsilon$-transition instead but, as it explains, that leads to a much less efficient construction. – David Richerby Jun 8 '17 at 8:49