Finite automata. Closure properties of regular languages. Pumping lemma

Closure properties of regular languages
Theorem 1
The class of regular languages is closed under union, intersection, subtraction, complementation, concatenation, Kleene closure and reversal.
Proof.
The idea is to build a DFA for the union of two languages by combining the two DFA’s into one such that, at each step, the new DFA would keep track of the computation paths of both DFA’s.

Proof of theorem 1

Proof of theorem 1

Proof of theorem 1

Proof of theorem 1

Proof of theorem 1

Proof of theorem 1

Proof of theorem 1

Proof of theorem 1

Proof of theorem 1

Proof of theorem 1

Proof of theorem 1

Proof of theorem 1
Kleene closure of an NFA.

Proof of theorem 1

Closure properties of regular languages
In the following examples a language is given and we show how to construct a DFA or a NFA accepting the language.

Closure properties of regular languages

Solution of example 1

Solution of example 1

Solution of example 1

Closure properties of regular languages

Another solution of example 2.

Closure properties of regular languages

Closure properties of regular languages

Solution of example 4

Solution of example 4

Pumping lemmas

Pumping lemmas

?

?

?

?

?

?

?

?

Pumping lemmas