Summing up ...

From the previous section we know that a language given by regular expression is also recognized by a NFA. What about the other way: Can a language recognized by a finite automaton (DFA or NFA) also be described by a regular expression? The answer is yes:

Theorem 3.2 (Theorem 3.4, page 91)   Given a DFA $A$ there is a regular expression $R(A)$ which recognizes the same language $L(A)=L(R(A))$.

We omit the proof (which can be found in the text book on pp.91-93). However, we conclude:

Corollary 3.3   Given a language $L\subseteq \Sigma^*$ the following is equivalent:

1. $L$ is given by a regular expression.

2. $L$ is the language accepted by an NFA.

3. $L$ is the language acceped by a DFA.

Proof: We have that 1.$\implies$ 2 by theorem 3.1. We know that 2.$\implies$3. by2.3 and 3.$\implies$1. by 3.2. $\Box$

As indicated in the introduction: the languages which are characterized by any of the three equivalent conditions are called regular languages or type-3-languages.