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.

union

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.

concat

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:

star

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

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s