## Description

1. Let L1 and L2 be two regular languages. They are specified by the

following regular expressions: L1 = 0(0 + 11)∗ and L2 = 0∗11∗

.

(1). Draw a DFA accepting L1.

(2). Draw a DFA accepting L2.

(3). Draw a DFA accepting L1 ∩ L2.

(4). What is the regular expression for L1 ∩ L2?

2. A natural number can be encoded as a unary string. For instance, 5=

the string of aaaaa. Therefore, we may treat a set of numbers as a language

over a unary alphabet (that contains only one symbol, e.g., a). Write down

the regular expression for the following sets of numbers: (1). all the n such

that n mod 3 = 1. (2). all the n such that n mod 3 = 0 or n mod 4 = 2.

3. Show that deterministic FAs are closed under complement. That is, for

any deterministic FA M, there is a deterministic FA M0

such that L(M0

) =

Σ

∗ − L(M), assuming that both M and M0 have the same alphabet.

4. According to your proof of Problem 3, draw a deterministic finite automaton that accepts the complement of (00 + 1)∗

. And also find a regular

expression for the language accepted by M0

.

5. Let L be a regular language on Σ and Σ0 ⊂ Σ. The result of dropping

symbols in Σ0

from a word w is denoted by w

−Σ0

. For instance, aaabacba−{b}

is aaaaca. Define L

−Σ0

= {w

−Σ0

: w ∈ L}. That is, L

−Σ0

is the result of dropping symbols in Σ0

from each word in L. Show that if L is a regular language,

then L

−Σ0

is also a regular language. (Hint: use structural induction)

1