## Description

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