CS381 Fall 2001 -- Homework
1
Prof Shai Ben-David
DUE: Friday, 9/14, 9:00 am
1. Which of the following statements holds
for every three languages L1, L2, L3?
(i) (L1ÇL2)L3=L1L3ÇL2L3
(ii) L1*=L1*×L1*
(iii) (L1ÈL2)ÇL3=L1È(L2ÇL3)
Please prove your claims.
2. Prove that for every non-empty language
L, eÎL iff LÍLL
3. (i) Prove
that if x and y are both strings over the same 1-letter alphabet, then xy=yx
(ii) Find
strings x,y over the alphabet {0,1} such that x¹y, both 0 and 1 appear in x (and y), and yet xy=yx.
(iii) BONUS:
Find a general (as general as you can) condition on strings such that if x,y
satisfy this condition, then xy=yx.
4. (i) Find
an infinite set W of languages over {0,1} so that the following two conditions
hold (simultaneously):
a. Every intersection of finitely many members of
W is non-empty
b. There is a subset of W whose intersection is
empty
(ii) BONUS:
Does there exist a set W that in addition to satisfying a & b above
also satisfies:
c. Every
infinite subset of W has empty intersection
5. Find what are the languages computed by each of the following
automata (double circles indicate accepting states):
Explain
your claims (there's no need to prove them).
6. Describe
automata that compute each of the following languages:
(i) L5,3={wÎ{0,1}*:|w| is
divisible by either 3 or 5}
(ii) For a given string wÎ{0,1}*,
the language {w}*.