Why does the concatenation operation imply the empty string?

Question

I'm a noob reading Michael Sipser's Introduction to the Theory of Computation, and I'm at a part where he's demonstrating how to construct finite automata that accept languages described by regular expressions. He does this by giving regular expressions, breaking them down into simpler regular expressions that represent the constituent pieces of the whole expression, creating a finite automata for each piece of the expression, and finally connecting them with the finite automata at the bottom that accepts the language described by the regular expression.

One of his examples is the sequence of finite automata in the picture attached, meant to illustrate how one might work through creating a finite automata that accepts the regular expression $(a\cup b)^* aba$.

With his definitions of union, concatenation, and star below.

Concatenation: $A+B=\{xy\mid x\in A\wedge y \in B\}$

Star: $A* = \{x_1x_2...x_k \mid k\geq 0 \wedge x_i \in A\}$

Union: $A\cup B = \{x\mid x\in A\vee x\in B\}$

At one point in the book he explains that two characters next to one another with no symbol between can imply concatenation so I am interpreting the "$aba$" piece as $a+b+a$.

I would think a finite automata that accepts $aba$ would have four states, with an "$a$" transition arrow between the first and second states, a "$b$" transition arrow between the second and third states, and an "$a$" transition arrow between the third state and the accept (fourth) state. The diagram instead is similar to what I imagined but adding a state with an empty string transition arrow between each state I described. See the 5th diagram, given for expression $aba $below $(a \cup b)^*aba$ illustrating how one might go about constructing a finite automaton that accepts the language described by that regular expression.">

These states with associated empty string transition arrows appear in both of the regular expression examples with concatenation he gives, so I must be misunderstanding something. There's a section in the book when he introduces nondeterministic finite automata in part of an effort to prove that regular languages are closed under the concatenation operation and mentions that "In general, an NFA may have arrows labeled with members of the alphabet or $\varepsilon$", and I figure the answer must have something to do with that, but I still don't understand why.

Answer 1

An $\varepsilon$ transition (called the empty transition from here on out) from $A$ to $B$ means that if you end up in $A$ after a transition you can go to $B$ for free without consuming a character from the input.

When concatenating $a$ and $b$, $a$ may have multiple end states so it is easier to add an empty transition from every end state of $a$ to the start state of $b$.

You can make the rule so when you concatenate all outgoing transitions of the start state of $b$ is copied to every end state of $a$ and if the start state of $b$ is not an end state then the end states of $a$ are not end states of the concatenated NFA.

This is a much more complicated rule than: every end state of $a$ is no longer an end state and gets a new empty transition to the start state of $b$.

Adding the empty transitions does not change the language being accepted and you can do a minimization/optimization pass after constructing the NFA to eliminate the excess empty transitions.

This is actually a common practice in compilers, the early code generation is dumb and does the obvious, easy and non-optimal but correct thing. Then optimization passes look for patterns that can be simplified or optimized. This means that the pattern can be optimized everywhere even when it wasn't generated by the construct that commonly creates it.