62 FINITE AUTOMATA
Example 2.38 Prove that if L is regular, so is MIN(L).
Proof. Assume that A4 = (Q, C,S, q, F) is a DFA which accepts L. Then,
MIN(L) is accepted by the NFA M’ obtained from A4 by deleting all out-
edges from final states. cl
Foranytwobitsa,b~{O,1},aVbd enotes the disjunction of a and b; that
is,OVO=OandOVl= 1 V 0 = 1 V 1 = 1. For any two binary strings x and y
with 1x1 = )yl, x V y d enotes the bitwise disjunction of x and y. For example,
if x = 0011 and y = 0101, then x V y = 0111.
Example 2.39 Show that if A and B are regular lunguuges over (0, l}, then
A v B = {x v y I x E A, y E B, 1x1= 1~1)
is ulso regular.
Proof Assume that DFA’s MA = (&A, (0, l}, &J, SA, FA) and &!B = (QB,
(0, 1}, SB, SB, &) accept sets A and B, respectively. To accept language
A V B, we build a product DFA A4’ to simulate MA and &?B. At each move,
if the input symbol is 0, then we simulate them in a normal way. If the input
symbol is 1, then this symbol may come from 0 V 1, 1 V 0 or 1 V 1; we simulate
all three possible computation paths in MA and MB. More precisely, we let
AI’ = (&A x QB, {0,1), d’, [SA, SB], FA x FB), where
d’([p, Cd, 0) = {ktJ(& o>, 6dq, (81)
~‘([io,q],l) = {[SA(~,O),SB(~,~)~,[SA(P,~),SB(Q,~)],[SA(P,~),~B(~)~)I}~ q
- Example 2.40 Show that if L is a regular language, so is
{XY I YX E Lb
Proof. Let M = (Q, C, 6,qo, F) be a DFA accepting L. Assume that Q =
(40,41, * l. , qn}. Intuitively, we can simulate M to decide whether an input UI
is in {xy I yx E L} or not as follows:
(1) We nondeterministically divide ul into two parts 20 = xy.
(2) Then, we nondeterministically jump to a state qi, and simulate A& on x
starting from state qi.
(3) Suppose that S(qi,x) = qj is not in F, then this simulation fails. Oth-
erwise, we simulate A4 on y starting from state qo, and accept ul if
Qo, Y) = Qi*
How do we implement the nondeterministic guess of state qi in step (2)?
We create many copies of A4 and each copy implements one choice. The
following is a more formal construction: