every regular language there is a regular expression, and for every regular
expression there is a regular language. We will show this in two parts.
Regular Expressions Denote Regular Languages
We first show that if r is a regular expression, then L(r) is a regular language.
Our definition says that a language is regular if it is accepted by some dfa.
Because of the equivalence of nfa's and dfa's, a language is also regular if it is
accepted by some nfa. We now show that if we have any regular expression r,
we can construct an nfa that accepts L(r). The construction for this relies on the
recursive definition for L(r). We first construct simple automata for parts (1), (2),
and (3) of Definition 3.2, then show how they can be combined to implement the
more complicated parts (4), (5), and (7).
Theorem 3.1
Let r be a regular expression. Then there exists some nondeterministic finite
accepter that accepts L(r). Consequently, L(r) is a regular language.
Proof: We begin with automata that accept the languages for the simple regular
expressions Ø,λ, and a ∈ Σ. These are shown in Figure 3.1(a), (b), and (c),
respectively. Assume now that we have automata M (r 1 ) and M (r 2 ) that accept
languages denoted by regular expressions r 1 and r 2 , respectively. We need not
explicitly construct these automata, but may represent them schematically, as in
Figure 3.2. In this scheme, the graph vertex at the left represents the initial state,
the one on the right the final state. In Exercise 7, Section 2.3, we claim that for
every nfa there is an equivalent one with a single final state, so we lose nothing
in assuming that there is only one final state. With M (r 1 ) and M (r 2 ) represented
in this way, we then construct automata for the regular expressions r 1 + r 2 , r 1 r 2 ,
and . The constructions are shown in Figures 3.3 to 3.5. As indicated in the
drawings, the initial and final states of the constituent machines lose their status
and are replaced by new initial and final states. By stringing together several
such steps, we can build automata for arbitrary complex regular expressions.
It should be clear from the interpretation of the graphs in Figures 3.3 to 3.5
that this construction works. To argue more rigorously, we can give a formal
method for constructing the states and transitions of the combined machine from
the states and transitions of the parts, then prove by induction on the number of
expression there is a regular language. We will show this in two parts.
Regular Expressions Denote Regular Languages
We first show that if r is a regular expression, then L(r) is a regular language.
Our definition says that a language is regular if it is accepted by some dfa.
Because of the equivalence of nfa's and dfa's, a language is also regular if it is
accepted by some nfa. We now show that if we have any regular expression r,
we can construct an nfa that accepts L(r). The construction for this relies on the
recursive definition for L(r). We first construct simple automata for parts (1), (2),
and (3) of Definition 3.2, then show how they can be combined to implement the
more complicated parts (4), (5), and (7).
Theorem 3.1
Let r be a regular expression. Then there exists some nondeterministic finite
accepter that accepts L(r). Consequently, L(r) is a regular language.
Proof: We begin with automata that accept the languages for the simple regular
expressions Ø,λ, and a ∈ Σ. These are shown in Figure 3.1(a), (b), and (c),
respectively. Assume now that we have automata M (r 1 ) and M (r 2 ) that accept
languages denoted by regular expressions r 1 and r 2 , respectively. We need not
explicitly construct these automata, but may represent them schematically, as in
Figure 3.2. In this scheme, the graph vertex at the left represents the initial state,
the one on the right the final state. In Exercise 7, Section 2.3, we claim that for
every nfa there is an equivalent one with a single final state, so we lose nothing
in assuming that there is only one final state. With M (r 1 ) and M (r 2 ) represented
in this way, we then construct automata for the regular expressions r 1 + r 2 , r 1 r 2 ,
and . The constructions are shown in Figures 3.3 to 3.5. As indicated in the
drawings, the initial and final states of the constituent machines lose their status
and are replaced by new initial and final states. By stringing together several
such steps, we can build automata for arbitrary complex regular expressions.
It should be clear from the interpretation of the graphs in Figures 3.3 to 3.5
that this construction works. To argue more rigorously, we can give a formal
method for constructing the states and transitions of the combined machine from
the states and transitions of the parts, then prove by induction on the number of