2.6 Closure Properties of Regular Languages 65
Proof. We use the second proof technique of the last example to solve this
problem.
Let M = (Q, C, 4 40, f’) b e a DFA accepting L, with Q = {a~, 41,... , an).
For every qi E Q, define a DFA Zi = (Q, C, S, qi, F) and an NFA Gi =
(Q, C, & qi, F) by
qq, a) = (s(% b) I b E cl*Also let a = Go.
Now. we construct an NFA M’ that contains 2n + 3 tracks simulating, in
parallel: Z and - Gi, gi for i = O,l,.. .) n. Intuitively2e useg to simulate
M on x=, use MO,... , Mn to simulate A4 on y, and use MO,... , A& to simulate
M on x. Therefore, after the machine M’ reads input x, if % is in state qi,
Gi is in state qj, and Gj is in a final state, then M’ accepts input x. That
is, M’ = (&I, C, s’, s, F’), where Q’ = Q2n+3, s = [qo,... ) qny qo, qo,... y qn],
I
6 (Ii7 joy l l l I qj,, % %co, l l l Y Qknl~ a>
= {[~(qjO~a)~~~~~s(qj,,a),t,tO~~~*~tnl I
tE~(q;,a),teE~(qk~,a),e=o,...,n},and
F’= {[qjo,*..,qjn,qi,qko,***,qknl Iqj,, E F]}-
(In the above implementation, the first n + 1 tracks simulate Go, Gl,... , zn,
the (n + 2)nd track simulates M, and the last n + 1 tracks simulate
Go, El,... , Gn. So, qj, denotes the state of DFA Gt, qi denotes the state of
a, and qkz denotes the state of NFA Et. The condition for the final states
F’ reads as follows: we accept the input x if a ends at state qi, Zi ends at
some state qki and &?,& ends at a state Qj,, E F .)^0
Using the above proof techniques, we can show that for any rational number
0 < r < 1, if L is regular then the language
Lr = ix I (W lIzI = r l IxyI, xy E L}
is also regular. Can we prove this type of closure properties for L, when r is
not a constant but is a nonlinear function of the length of Izyl? The answer is
yes for some simple functions r. However, the proof for such a result depends
on certain structural properties of the DFA A4 that accepts L, and is not a
direct construction from AL In the following, we show a simple example, and
leave the general cases as an exercise (see Exercise 10 of this section).
- Example 2.43 Let A and B be two regular languages. Show that the lan-
guage defined by
C(4B) = b E A I (3Y)[lYl = 1212,Y E Bl}
is also regular.