From “Introduction to Computation Theory” by Michael Sipser

### Union Operation:

Theorem: The class of regular languages is closed under the union operation. If A1 and A2 two regular languages, $A_{1} \cup A_{2}$ is also a regular language.

Proof: We have two NFAs (Non-deterministic Finite Automata) N1 and N2 for A1 and A2 respectively. We combine them into a new NFA, N. We want to show that N accepts its input if either A1 or A2 accepts the input.

1) N has a start state that branches to the start states of N1 and N2 via ε arrows.
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 A1 and A2 two regular languages, $A_{1} \circ A_{2}$ is also a regular language.

Proof: We have two NFAs N1 and N2 for A1 and A2 respectively. We combine them into a new NFA, N. We want to show that N accepts its input if either A1 or A2 accepts the input.

1) The start state of N is the start state of N1.
2) The accept states of N1 have $\epsilon$ arrows to the start state of N2.
3) The accept states of N are the accept states of N2.
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, NA. 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 NA.

We can construct N from NA by having $\epsilon$ arrows leaving NA‘s accept states back to its start state. We also need to take care of the case where A* gives $\epsilon$. 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 $\epsilon$ arrow for the start state of NA.

In the end, we have this:

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

Advertisements