Cpt S 317 Homework #1
Please print your name!
Absolutely no late homework!
1. Give an example (i.e., a word in the language represented by regular expression) and a counter example (i.e., a word not in the language represented
by regular expression) to the following regular expressions: 0(10 + 0)∗11 and
(0 + 110)∗1(01 + 1)∗
.
2. Find a regular expression for each of the following languages on {0, 1}:
(1). all strings containing more than two 0’s,
(2). all strings do not contain 01,
(3). all strings contain both 1011 and 0111 as substrings,
(4). all strings do not ended with 01.
3. Show that, for any languages L1 and L2, we have
(1). L1L
∗
1 = L
∗
1L1L
∗
1
,
(2). (L
∗
1L2)
∗L
∗
1 = (L1 + L2)
∗
.
4. Show me (through an example) why this is not true: for any languages
L1 and L2, we have L
∗
1 + (L
∗
1L2)
∗ = (L1 + L2)
∗
.
5. Any pets in your house? I have a 10gal fish tank. You may not want to
keep more than three fishes in such a small tank, so I choose to maintain a
population of exactly 3 (no more, no less, and don’t ask me why). Unfortunately, every day, exactly one fish dies and I immediately buy a new one
from a local fish store and put it in the tank by the end of the day. This
happens until someday later no fish dies and I have always the same three
fish in my tank. Here are some rules about the tank:
(1). At most these two kinds of fish in the tank: damsels and clowns,
(2). Since damsels are pretty aggressive, if the tank has at least one
clown, then there is no more than one damsel in the tank.
At the end of each day, my tank is in one of the following possible configurations:
A: three damsels,
B: three clowns,
C: 2 clowns and 1 damsel.
1
From day one to day n, I may observe a sequence (with length n) of these
configurations, which is a word on alphabet {A, B, C}. Write a regular expression that represents all the possible observed sequences for all n.
2
