68
(b) {x 1 x E A,xx E A}.FINITE AUTOMATA(c) A, = {y 1 xy E A}, where x is a fixed string.
(d) (w2 l l ’ a271^1 a2ala4a3 l l ~nu2n-l E A}.
(e) (~1~3 •**~2n-3~2n-l 1~1~2 l **u2n E A}.
(f) (~lbl~2b2 l l l unbn I ~1~2 l l l un E A, blb2 l l l bn E I?}.
k> A @ B*
* 4. Give an alternative proof for Example 2.42 based on the following idea:
We may simulate NFA z on xy together with gi on x by simulating
two moves of a and one move of zi at each step. (Thus, the new NFA
for Lg has only n + 2 tracks.)
- Show that if A and B are regular languages, so are the following:
(a> {XYX I XYJ: E AI*
(b) {XYZ I ZYX E A Y E B)*
(4 {Y I w [Id = IYL XY E AlI*
(4 -b I PY, x> [Id = IYI = Id, XYX E Al).
(4 {Y I (W Z>I Cld = IYI = Id XYX E AlI*
(f) {YZ I (W [Id = IYI = kl,~Y~ E AlI*
(4 -bY I (32) [Id = IYI = ld>ZYZ E AlI*
(h) -b I W,Y, z> b = ulyx and WY% E A]}.- Consider a Boolean function d(ul, ~2,. l l , a,>. For any n binary strings
Xl7 X2, ’ ’ ’ J Xn of equal length, denote by f(xl, x2, l l 0, xn) the bitwise
function f on xl,x2,***,xn. That is, if xi = xilxi,...xik for i = 1, 2,
co
. , n, where each xij is a bit in (0, 1}, then f(xl , x2,... , xn) is equal
f (x11, x21, ’ l l 1 Xnl)‘f(~l2,~22~~n2)“‘f(~lk2k~~~~nk)~
Show that if languages Al, AZ, l l l , An are regular, then language
{f(21,X27"'~ Xn) I 1x11 = 1x21 = ‘**= IXnl9
~1 EAl,x2EA2,***,xnEAn}is also regular.
- In Exercise 3(c)
ber of distinct
assuming that
above, show that, for any regular language A, the num-
Ax’s is finite. Find an upper bound for this number,
4 is accepted by a DFA with s states.- Are the following statements true? Prove or disprove your answer.
(a) If A is regular and A C B, - then B is regular.
(b) If A is regular and B C A, - then B is regular.
(c) If A2 is regular, then A is regular.