FA Proofs

Regular Languages are closed under Union, Concatenation, Star, and Complementation

Union Proof

Let FA M1 recognize L1 and let M2 recognize L2. Consider the following NFA that
will recognize L1 ∪ L2

Steps:

1. Add a new start state with epsilon transitions to the start states of M1 and M2
   
   

Concatenation Proof

Let FA M1 recognize L1 and let M2 recognize L2. Consider the following NFA that
will recognize L1 ◦ L2:M1 M2

Steps:

1. We start at the start state of M1 and add epsilon transitions from the accept states of M1 to the start state of M2.

2. The accept states are the accept states from M2 only.

Star Proof

Let FA M1 recognize L. Consider the following NFA that will recognize L∗:

Steps:

1. add a new start state with an epsilon transition to the start state of M1.

2. from every accept state we add epsilon transitions back to the start state of M1.

3. The accept states are the original accept states plus the new state to accept the empty string.