Cpt S 317 Homework #3
Please print your name!
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
