arguments.
Theorem 4.2
The family of regular languages is closed under reversal.
Proof: The proof of this theorem was suggested as an exercise in Section 2.3.
Here are the details. Suppose that L is a regular language. We then construct an
nfa with a single final state for it. By Exercise 7, Section 2.3, this is always
possible. In the transition graph for this nfa we make the initial vertex a final
vertex, the final vertex the initial vertex, and reverse the direction on all the
edges. It is a fairly straightforward matter to show that the modified nfa accepts
w R if and only if the original nfa accepts w. Therefore, the modified nfa accepts
L R , proving closure under reversal.
Closure under Other Operations
In addition to the standard operations on languages, one can define other
operations and investigate closure properties for them. There are many such
results; we select only two typical ones. Others are explored in the exercises at
the end of this section.
Definition 4.1
Suppose Σ and Γ are alphabets. Then a function
is called a homomorphism. In words, a homomorphism is a substitution in
which a single letter is replaced with a string. The domain of the function h is
extended to strings in an obvious fashion; if
then
Theorem 4.2
The family of regular languages is closed under reversal.
Proof: The proof of this theorem was suggested as an exercise in Section 2.3.
Here are the details. Suppose that L is a regular language. We then construct an
nfa with a single final state for it. By Exercise 7, Section 2.3, this is always
possible. In the transition graph for this nfa we make the initial vertex a final
vertex, the final vertex the initial vertex, and reverse the direction on all the
edges. It is a fairly straightforward matter to show that the modified nfa accepts
w R if and only if the original nfa accepts w. Therefore, the modified nfa accepts
L R , proving closure under reversal.
Closure under Other Operations
In addition to the standard operations on languages, one can define other
operations and investigate closure properties for them. There are many such
results; we select only two typical ones. Others are explored in the exercises at
the end of this section.
Definition 4.1
Suppose Σ and Γ are alphabets. Then a function
is called a homomorphism. In words, a homomorphism is a substitution in
which a single letter is replaced with a string. The domain of the function h is
extended to strings in an obvious fashion; if
then