Description
1. (6 marks) This question tests your comfort with “boundary cases” of DFA’s. Draw the state diagrams of DFA’s
recognizing each of the following languages.
(a) (2 marks) L = {} for the empty string.
(b) (2 marks) L = ∅.
(c) (2 marks) L = {0, 1}
∗
.
2. (8 marks) This question tests your ability to design DFAs and NFAs.
(a) (2 marks) Draw the state diagram for a DFA recognizing language L1 = {x | x contains at least two 1s}.
(b) (2 marks) Draw the state diagram for a DFA recognizing language L2 = {x | x contains at most one 0}.
(c) (4 marks) Draw the state diagram for a NFA recognizing language L3 = L1 ∪ L2.
3. (3 marks) In this question, you will study closure of regular languages under certain operations. Specifically,
show that if M is a DFA that recognizes language B, then swapping the accept and nonaccept states in M yields
a new DFA M0
recognizing the complement of B, B. Which operation does this imply the regular languages
are closed under?
4. (6 marks) This question tests your ability to prove a language is regular using the closure properties of regular
languages. Given languages A and B, define the operation · as
A · B := {x | x ∈ A and x does not contain any string in B as a substring.}.
Prove that the class of regular languages is closed under the · operation. (Hint: Recall that by DeMorgan’s law,
for any sets X and Y , one has X ∩ Y = ¬(¬X ∪ ¬Y ).)
5. (6 marks) This question tests your understanding of the equivalence between DFAs and NFAs. Consider NFA
M = ({q1, q2}, {0, 1}, δ, q1, {q1}) for δ defined as:
δ 0 1
q1 {q1, q2} {q2} ∅
q2 ∅ {q1} {q1}
Draw both the state diagrams for M and for a DFA M0
equivalent to M based on the construction of Theorem
1.39 in the text (recall the latter proves that DFAs and NFAs are equivalent).
6. (Bonus, 5 marks) This question demonstrates that although DFAs and NFAs are equivalent in terms of the sets of
languages they recognize, they are provably not equivalent in terms of efficiency (i.e. DFAs may require many
more states to recognize a language than an NFA). Consider the language Ck = Σ∗0Σk−1
for k ≥ 1.
Convince
yourself that an NFA with k + 1 states for recognizing Ck exists (no need to include this in your assignment
answer). Now, prove that for any k, Ck cannot be recognized by a DFA with less than 2
k
states.
1