*From “Introduction to Computation Theory” by Michael Sipser*

### Union Operation:

Theorem: The class of regular languages is closed under the union operation. If *A _{1}* and

*A*two regular languages, is also a regular language.

_{2}Proof: We have two NFAs (Non-deterministic Finite Automata) *N _{1}* and

*N*for

_{2}*A*and

_{1}*A*respectively. We combine them into a new NFA,

_{2}*N*. We want to show that

*N*accepts its input if either

*A*or

_{1}*A*accepts the input.

_{2}1) *N* has a start state that branches to the start states of *N _{1}* and

*N*via ε arrows.

_{2}2) The accept states of

*N*are the accept states of the other two machines.

3) The states of

*N*are the states of the other two machines, plus the additional start state of 1).

Essentially, we are combining the two machines to form a bigger one that can accept both of the regular languages.

### Concatenation Operation

Theorem: The class of regular languages is closed under the concatenation operation. If *A _{1}* and

*A*two regular languages, is also a regular language.

_{2}Proof: We have two NFAs *N _{1}* and

*N*for

_{2}*A*and

_{1}*A*respectively. We combine them into a new NFA,

_{2}*N*. We want to show that

*N*accepts its input if either

*A*or

_{1}*A*accepts the input.

_{2}1) The start state of *N* is the start state of *N _{1}*.

2) The accept states of

*N*have arrows to the start state of

_{1}*N*.

_{2}3) The accept states of

*N*are the accept states of

*N*.

_{2}4) The states of

*N*are the states of the other two machines.

Again, we are combining the two machines to form a bigger one that can accept both of the regular languages.

### Star Operation

Theorem: The class of regular languages is closed under the star operation. If *A* a regular language, *A** is also a regular language.

Proof: We have an NFA for *A*, *N _{A}*. We want to create an NFA

*N*that recognizes

*A**.

*N*will accept its input if it can be broken in pieces and each piece can be recognized by

*N*.

_{A}We can construct *N* from *N _{A}* by having arrows leaving

*N*‘s accept states back to its start state. We also need to take care of the case where

_{A}*A**gives . To do that we will create a new start state for

*N*that will also serve as an accept state. From this start state there will leave an arrow for the start state of

*N*.

_{A}In the end, we have this:

In this case, we are reusing the previous machine to recognize the input piece by piece.