In the next part of this section we concentrate on the closure properties of the class of regular languages.

By the constructive proof of Theorem 3, it is also shown that the class of regular languages is closed under the regular operations. Now let us consider the set theoretical operations: intersection and complement.

**Theorem 7.** *The class of regular languages is closed under intersection and complement. *

**Proof.** The proof is constructive in both cases, and deterministic finite automata are used.
Let us start with the complement. Let a regular language be given by a complete deterministic
finite automaton *A* = (*Q, T, q*_{0}, *δ, F*) that recognizes it.
This automaton has exactly one run for
every word of *T*^{*}, and accepts a word if this run is finished in an accepting state.
Then recognize exactly those words that are not accepted
by *A*, and thus the finite automaton accepts the complement of the original regular language.

For the intersection, let two regular languages *L*_{1} and *L*_{2}
be given by complete deterministic
automata *A* = (*Q, T, q*_{0}, *δ,F*) and
*A'* = (*Q', T, q'*_{0}, *δ', F'*) that recognize them, respectively.
Then, let *A*^{∩} = (*Q* ×
*Q', T, *(*q*_{0}, *q'*_{0}), *δ'', F× F'*),
with transition function
*δ''* ((*q,q'*), *a*) = (*δ*(*q,a*), *δ'* (*q',a*))
for every *q* ∈ *Q, q'* ∈ *Q'* and *a* ∈ *T*.
The states are formed by pairs of the states of the automata *A* and *A'*.
Thus, *A*^{∩} simulates the work of these two automata simultaneously and accepts exactly those
words that are accepted by both of these machines. Thus the intersection of the languages *L*_{1} and
*L*_{2} is accepted by a finite automaton, and thus it is also a regular language.

QED.

**Example 28.** *Let the automaton A and A' accept the languages L*(*A*)
*and L*(*A'*), *respectively.
Let them be defined in the following way: the table of A as shown below.*

T Q | →q_{1} | q_{2} | ⊂q_{3}⊃ |
---|---|---|---|

a | q_{3} | q_{2} | q_{3} |

b | q_{2} | q_{2} | q_{3} |

*the table of A' as shown below*

T Q' | →q'_{1} | ⊂q'_{2}⊃ |
---|---|---|

a | q'_{1} | q'_{1} |

b | q'_{2} | q'_{2} |

*Give an automaton that accepts the complement of L*(*A*) *and an automaton that accepts the intersection of
L*(*A*) *and L*(*A'*).
*What are the languages accepted by these automata?*

*Solution: *

*Let us take the automaton that accepts the complement of L*(*A*) *by interchanging the role of
accepting and non-accepting states in A. Let
be defined by the following Cayley table:*

T Q | →⊂q_{1}⊃ | ⊂q_{2}⊃ | q_{3} |
---|---|---|---|

a | q_{3} | q_{2} | q_{3} |

b | q_{2} | q_{2} | q_{3} |

*Now let us construct A*^{∩} *by using the Cartesian product of the sets of states Q and Q'.*

T Q | →(q_{1}, q'_{1}) | (q_{2}, q'_{1}) | (q_{3}, q'_{1}) | (q_{1}, q'_{2}) | (q_{2}, q'_{2}) | ⊂(q_{3}, q'_{2})⊃ |
---|---|---|---|---|---|---|

a | (q_{3}, q'_{1}) | (q_{2}, q'_{1}) | (q_{3}, q'_{1}) | (q_{3}, q'_{1}) | (q_{2}, q'_{1}) | (q_{3}, q'_{1}) |

b | (q_{2}, q'_{2}) | (q_{2}, q'_{2}) | (q_{3}, q'_{2}) | (q_{2}, q'_{2}) | (q_{2}, q'_{2}) | (q_{3}, q'_{2}) |

*Actually, A accepts the language a*(*a+b*)^{*} *(words starting by letter a),
and A' accepts the language *(*a+b*)^{*} *b
(words that ends with letter b), the automaton
accepts the language λ + b(a+b)
^{*} (words do not start with letter a over the alphabet* {

**Exercise 36.** *Let the table of A be*

T Q | →q_{1} | q_{2} | ⊂q_{3}⊃ |
---|---|---|---|

0 | q_{1} | q_{3} | q_{2} |

1 | q_{2} | q_{2} | q_{2} |

*and the table of A' be*

T Q' | →q'_{1} | ⊂q'_{2}⊃ | ⊂q'_{3}⊃ |
---|---|---|---|

0 | q'_{3} | q'_{2} | q'_{3} |

1 | q'_{2} | q'_{1} | q'_{2} |

*Give an automaton that accepts the intersection of the languages accepted by A and A'.*

**Exercise 37.** *Let the language L*(*A*) *be defined
as the accepted language of the automaton A as it is shown in
Figure 2.10.*

*Give an automaton that accepts the complement of L*(*A*).
*(Hint: first the equivalent completely defined deterministic automaton must be obtained.) *

**Exercise 38.** *Let the table of A be*

T Q' | →q_{1} | q_{2} | ⊂q_{3}⊃ | ⊂q_{4}⊃ |
---|---|---|---|---|

a | q_{1} | q_{3} | q_{1} | q_{1} |

b | q_{1} | q_{4} | q_{2} | q_{2} |

c | q_{2} | q_{4} | q_{4} | q_{3} |

*and the table of A' be*

T Q' | →⊂q'_{1}⊃ | q'_{2} |
---|---|---|

a | q'_{1} | q'_{2} |

b | q'_{2} | q'_{1} |

c | q'_{2} | q'_{1} |

*They accept the languages L*(*A*) *and L*(*A'*), *respectively.*

*Give automata that accept the complement of L*(*A*) *and L*(*A'*).
*Give an automaton that accepts L*(*A*) ∩ *L*(*A'*).

In the next part we show an if and only if characterization of the class of regular languages.

Let us define congruence relations on *T*^{*} with the following property:
for every *u, v, w* ∈ *T*^{*}
if *u* ∼ *v*, then *uw* ∼ *vw*.
These relations are called *right-congruences*.
A congruence relation is of finite index, if the number of classes of *T*^{*} is finite.

**Theorem 8.** (Myhill-Nerode theorem). *A language over the alphabet T is regular if and only if there is
a finite index right-congruence relation on T ^{*} such that the language is obtained as (the union
of) some of the classes induced by the relation. *

Let a language *L* be given. Roughly speaking two words, *u* and *v* are equivalent if
their every possible continuation *w*
behaves in the same manner, i.e., *uw* ∈ *L* if and only if *vw* ∈ *L*.
If this equivalence relation induces finitely many classes on
*T*^{*}, then, and only then, *L* is regular.

Actually, this fact is also related to the minimal, completely
defined, accepting deterministic finite automaton (that uniquely identifies the given regular
language): the partitions of *T*^{*} can be assigned to the states of the minimal automaton:
the partition containing the empty word λ is assigned to the initial state; those
partitions that contain words such that their empty continuation is in L are assigned to the
accepting states. The transitions can also be easily defined by using the partitions, by checking
in which partition the words are that are given by the previous one by extending it with exactly
one letter.

Now, we are going to give an example for how this theorem can be used to show that some of the languages are not regular.

**Example 29.**
*Let us analyze language L* = {*a ^{n} b^{n}*∣

**Exercise 39.**
*Show that the language containing exactly the words having the same number of 0's and 1's (over the
alphabet* {*0,1*}*) is not regular. *

*(Apply the Myhill-Nerode theorem.)*

**Exercise 40.**
*Show that the language L = *{*a*^{n2}∣*n* ∈ ℕ}
*(over the alphabet* {*a*}), *i.e., the
unary words having square number length, is not regular.*

*(Apply the Myhill-Nerode theorem.)*