# Closure of regular Language - Transition Function : Sipser Proof

I was going through construction proofs for closure of regular languages under union, star and concatenation operation in the book: "Introduction to Theory of Computation" by Michael Sipser.

I have doubts regarding how he wrote the transition function.

When $Q \in F_1$ and $a=\epsilon$ he wrote $\delta_1(q,a) \cup \{q_2\}$. I couldn't understand why its so. When the input is epsilon, the state moves to $q_2$ and what is the need for writing that $\delta_1(q,a)$

Also if that is so, the $A^*$ example he wrote for the transition function $\{q_1\}$ only when $q=q_0$ and $a=\epsilon$

• There might be a transition from $q$ inside $N_1$ on $\epsilon$ in that case, he wants to also have the possibility of starting $N_2$. Feb 26 '13 at 12:18
• @vonbrand When $a=\epsilon$, what it means for $\delta(q,a)$? Feb 26 '13 at 12:27
• It means the automaton can jump to one of the states in $\delta(q, \epsilon)$ without advancing in the input. Feb 26 '13 at 12:34

The idea is that whenever $A_1$ reaches an accepting state, it "guesses" that this is a good place to split the word, and run the second part in $A_2$. But maybe this guess is wrong? There are many ways to split a word, and you only need one such splitting to work.
As an example, consider the languages $L_1=(a+b)^*a$ and $L_2=b(a+b)^*$. Now consider what would happen in your suggestion with the word $aab$. After reading the first $a$, $A_1$ will be in an accepting state, so it will move to the initial state of $A_2$, and upon reading the second $a$, will move to a rejecting sink.
However, as Sipser suggests, $A_1$ may continue using $\delta_1$ for the second $a$ as well, and only then move to $A_2$.
• When $a=\epsilon$, what it means for $\delta(q,a)$? Feb 26 '13 at 12:34
• If (for example) $\Sigma=\{a,b\}$, then $a$ and $b$ are letters. $\epsilon$ denotes the empty word. An $\epsilon$ transition in an NFA means that the NFA can take that transition without reading a letter from the word. Feb 26 '13 at 13:12