Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

enter image description here

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$

share|cite|improve this question
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$. – vonbrand Feb 26 '13 at 12:18
@vonbrand When $a=\epsilon$, what it means for $\delta(q,a)$? – user5507 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. – vonbrand 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$.

Same goes for the construction for Kleene star.

share|cite|improve this answer
When $a=\epsilon$, what it means for $\delta(q,a)$? – user5507 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. – Shaull Feb 26 '13 at 13:12

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.