Next: Showing that a language
Up: Regular expressions
Previous: Translating regular expressions to
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$](img27.png)
there is a regular expression
![$ R(A)$](img296.png)
which
recognizes the same language
![$ L(A)=L(R(A))$](img297.png)
.
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^*$](img128.png)
the following is equivalent:
is given by a regular expression.
is the language accepted by an NFA.
is the language acceped by a DFA.
Proof:
We have that 1.
2 by theorem 3.1. We know that
2.
3. by2.3 and 3.
1. by 3.2.
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.
Next: Showing that a language
Up: Regular expressions
Previous: Translating regular expressions to
Thorsten Altenkirch
2001-05-08