The class of languages accepted by finite automata is closed under

1. union
2. concatenation
3. Kleene star
4. complementation
5. intersection

Proof

1. union

Let M1 = (K1, ∑, Δ1, s1, F1), M2 = (K2, ∑, Δ2, s2, F2)
We construct a non-deterministic automaton M = (K, ∑, Δ, s, F), where


K = K1 È K2 È {s}
F = F1 È F2
Δ = Δ1 È Δ2 È {(s, e, s1), (s, e, s2)}

We introduce a new start state s, and M “guesses” whether the input is for M1 or M2.
Formally,


if w є ∑* then
(s,w) ├ *_M (q, e) for some q є F iff
either (s1, w) ├ *_M1 (q, e) for some q є F1
or      (s2, w) ├ *_M2 (q, e) for some q є F2

Hence M accepts w iff M1 accepts w or M2 accepts w, thus L(M) = L(M1) Ç L(M2)

2. concatenation

We will construct an automaton M that accepts L(M) = L(M1) ° L(M2)
Let M1 = (K1, ∑, Δ1, s1, F1), M2 = (K2, ∑, Δ2, s2, F2)
We construct a non-deterministic automaton M = (K, ∑, Δ, s, F), where


K = K1 È K2
s = s1
F = F2
Δ = Δ1 È Δ2 È {(q, e, s2)| q є F1}

Here the idea is the connect all final states of M1 with empty links to the start state of M2.

Formally,
if w є ∑* then
(s,w) ├ *_M (q, e) for some q є F iff
w = uv, and
(s1, u) ├ *_M1 (q, e) for some q є F1, i.e. u є L(M1)
(s2, v) ├ *_M2 (q, e) for some q є F2, i.e. v є L(M2)

Hence M accepts w iff M1 accepts part of w and then M2 accepts the remaining part. Thus L(M) = L(M1) ° L(M2)

3. Kleene star
Let M1 = (K1, ∑, Δ1, s1, F1)
We construct a non-deterministic automaton M that accepts L(M) = L(M)* in the following way:
M = (K, ∑, Δ, s, F), where
K = K1 È {s}
F = F1 È {s}
Δ = Δ1 È {(s, e, s1) }È { (q, e, s1) | q є F1}

The idea here is to have a new start state connected to s1 with an empty link, so that M accepts the empty string, and to have e-transitions from all final states of M1 to s1, so that once a string has been read, the computation can resume from the initial state.

4. complementation
Let M = (K, ∑, δ, s, F), accepting L(M). The complement of L(M) is ∑* - L(M). It is accepted by a deterministic FSA constructed in the following way:
M' = (K, ∑, δ, s, K - F)
M' is identical to M except that the final and non-final states are interchanged.
Thus a string that is accepted by M will not be accepted by M’ and vice versa.
5. intersection
Here we apply the equality:
L1 Ç L2 = ∑* - ((∑* - L1) È (∑* - L2))
The closedness under intersection follows from the closedness under union and complementation.
How to construct M (we consider deterministic complete automata):
Let M1 = (K1, ∑, δ1, s1, F1), M2 = (K2, ∑, δ2, s2, F2)
We construct a deterministic automaton M = (K, ∑, δ, s, F), where
K = K1 x K2
s = (s1,s2)
F = {(q, p) | q є F1, p є F2}
δ = { (q1, p1), a, (q2,p2)) | (q1,a, q2) є δ1,(p1,a,p2) є δ2 }

Let M1 and M2 are accepting L(M1) and L(M2) respectively.
The new automaton M has to accept strings { w | w L(M1) Ç L(M2)}, i.e. both M1 and M2 on w have to stop in final states.

Rule 1: An FSA that accepts a string of one letter or the empty string:

When applying Rule 2, Rule 3, and Rule 4 below, assume that an FSA has one final state only.
If there are more final states, we can replace them by internal states and link them
to a new final state by the empty string.

Rule 2: Sequential linking of two FSAs.

We link the final state of the first FSA with the starting state of the second FSA by an empty link.
The final state of the first FSA is not a final state in the new FSA.
The starting state of the second FSA is not anymore a starting state in the new FSA.
Thus we obtain a new FSA. If the first FSA accepts L1, and the second FSA accepts L2,
then the new FSA will accept L1L2

Rule 3: Parallel linking of two FSAs

1. Introduce a new starting state.
2. Link the new starting state with the starting states of each FSA by an empty link
   (the starting states of the two FSAs are no more starting states)
3. Introduce a new final state
4. Link the final states of each FSA to the new final state by an empty link.
   The final states of the two FSAs are no more final states.

Rule 4: Kleene star on a FSA.

Given an FSA that accepts the language L, how do we build an FSA hat accepts L*?

We link its starting state to its final state by an empty link,
and its final state to its starting state by an empty link.

Rule 5: Complementation

Rule 6: Intersection

Rule1, Rule2 Rule3 and Rule4 give the method to build an FSA that accepts a language represented by some regular expression.

Example 1

Build an FSA that accepts (ab U b*)*

1. We build an FSA that accepts 'a' - FSA1 (Rule 1)


 

2. We build an FSA that accepts 'b' - FSA2 (Rule 1)


 

3. We link these two FSA sequentially - FSA3 (Rule 2)


 

Here we can simplify the FSA:



 

4. Next we build an FSA that accepts b (same as in 2.): - FSA4 (Rule 1)


 

5. The FSA that accepts b* will be FSA5 (Rule 4)


 

6. Now we link in parallel FSA3 and FSA5. The new FSA is FSA6 (Rule 3)


 

7. Last we build FSA7 = FSA6* (Rule 4)


Example 2

Construct automaton that accepts L1 Ç L2, where
L1 = {w є ∑* | w contains even number of a’s}
L2 = {w є ∑* | w contains odd number of b’s}

Let M1 accept L1, and M2 accept L2. We will describe M1 and M2 by transition tables:

M1:  
	K1 = {q1, q2}
	S1 = q1
	F1 = {q1}

		transition table:
		a	b

        q1	q2	q1
	q2	q1	q2


M2:
	K2 = {p1, p2}
	S2= p1
	F2 = {p2}

		transition table:
		a	b

	p1	p1	p2
	p2	p2	p1

The new automaton M will have the following states:


K = {(q1, p1), (q1, p2), (q2, p1), (q2, p2)}
S = (q1, p1)
F = {(q1, p2)}

The transition table is:

		a		b
(q1, p1)      ( q2, p1)		(q1, p2)
(q1, p2)      ( q2, p2)		(q1, p1)
(q2, p1)      ( q1, p1)		(q2, p2)
(q2, p2)      ( q1, p2)         (q2, p1)

We will show now that the string aabaabb is accepted, while the strings aabb and abbb will not be accepted

((q1, p1), aabaabb) ├ ((q2, p1), abaabb) ├ ((q1, p1), baabb) ├ ((q1, p2), aabb) ├ ((q2, p2), abb) ├ ((q1, p2), bb) ├
((q1, p1), b) ├((q1, p2), e)
(q1, p2) is a final state in M, so the string aabaabb is accepted
((q1, p1), aabb) ├ ((q2, p1), abb) ├ ((q1, p1), bb) ├ ((q1, p2), b) ├ ((q1, p1), e)
(q1,p1) is not a final state, so aabb is not accepted
((q1, p1), abbb) ├ ((q2, p1), bbb) ├ ((q2, p2), bb) ├ ((q2, p1), b) ├ ((q2, p2), e)
(q2, p2) is not a final state, so abbb is not accepted