Problem Solving in Automata, Languages, and Complexity

60 FIN..TE AUTOMATA

Lo. Finally, we use the method of Section 2.5 to construct an NFA M’
such that L(W) = L(s).
This process, however, is too complicated, with three nontrivial construc-
tions. Here, we present a different approach, with a simple idea that has many
applications in other construction problems involving NFA’s.
Assume that A4 = (Q, C, 6, ~0, F) is an NFA. Our construction of M’ is
based on the following idea: On input X, we simulate M on z, starting from a
final state and going backward. That is, we reverse the arrows in the transition
diagram of M, and search for a path from a final state qf of M to the initial
state ~0, with the labels X. Note that if such a path is found, then its reversed
path is an accepting path for IX: R. Also, if there is a computation path of M
on x R, then its reversal is a such a path for x. Thus, M accepts xR if and
only if the reversed machine M’ accepts x.
Formally, assume that Q = {~o,qr,... , qn}. We add a new starting state s
and let M’ = (Q u {s}, C, 6 s, {qo)), where

#(s, E) = F,

a’(qi, a) = {qj E Q 1 qa E d(qj, a)}, for qi E Q and a E C U {E}.

Finally, we remark that the machine M’ obtained from this reversal con-

struction is, in general, not a DFA even if A4 itself is a DFA: It is possible

that, for some state qi and some symbol a, there are more than one states qj

such that S(qj,a) = qi. In other words, the reversal simulation requires the

ability of nondeterministic search for the right path from a final state to the

initial state. cl

Next, we consider a new language operation called substitution. Let f
be a mapping which maps each symbol a E C to a language L, over an
alphabet I. We extend function f to the domain of C* by f(~) = {E} and

f(ala2 ’ l l ak) = f(al) f(w) o l l f(ak), for al,... , ak E c. Then, for any
language L C C*,
function f to-L:

we obtain a new language by applying the substitution

f(L) = u f(x)*

x:EL

For example, suppose that L = {Ol,lO} and f(0) = O(O+l), f(l) = (O+l)l.
Then,
f(L) = o(0 + 1>1 u l(0 + 1>0.

A substitution f is called a homomorphism if for any a E C, f(a) is a language
with a single string.

Example 2.35 Let f be a substitution ouer C. Assume that L C C* is a
regular language, and that f ( ) a is a regular language for each a EC. Then,
f(L) is also a regular language.