CS 161, Spring 2024: Homework 2
Homework 2: NFAs and Regular Expressions
0. (Ungraded exercise) We rushed/didn’t get to the exercises at the end of worksheet 3
(copied below for convenience). Make sure you understand what is wrong with these
proofs.
(a) Here is a false statement with a bad proof. What is wrong with the proof?
Theorem (Not actually true). Every binary language is regular.
Proof. Let A be any language. Here is a DFA M:
M q0
0,1
Note that any string in A is accepted by this DFA. Thus, this DFA recognizes A,
so A is regular.
(b) Here is a false statement with a bad proof. What is wrong with the proof?
Theorem (Not actually true). The language A = {00, 11} is not regular.
Proof. Here is a DFA M:
M q0 q1
0 1
1
0
The string 11, which is in A, is not accepted by this DFA. Thus, the DFA M does
not recognize A, so A is not regular.
1. (10 points) Let L be the language of binary strings with at least two 0s or at least
three 1s.
(a) (5 points) Draw a state diagram for an NFA that recognizes L.
(b) (5 points) Recall that an NFA is a 5-tuple N = (Q, Σ, δ, q0, F) for finite set of states
Q, finite set of alphabet characters Σ, transition function δ : Q × Σε → P(Q),
start state q0 ∈ Q, and accept states F ⊂ Q. Describe your NFA as a 5-tuple.
2. (10 points) Prove the following theorem by generalizing the construction from Worksheet 6.
Theorem. The set of regular languages are closed under concatenation.
(c) Sara Krehbiel, Ray Li 1
CS 161, Spring 2024: Homework 2
That is, prove that, for any two regular languages A and B, the language A ◦ B =
{ab : a ∈ A : b ∈ B} is regular.
3. (5 points) Consider the NFA N = ({1, 2, 3}, {0, 1}, δ, 1, {3}) with δ as depicted below (this is the same one from Quiz 6). Give a regular expression for the language
recognized by this NFA.
N 1 2 3
ε
1
0
1 0
4. (10 points) Find an NFA that recognizes the language of (0◦1)∗ ◦(0∪1) (the alphabet is
Σ = {0, 1}). Include both a state diagram and a formal specification of your automaton
as a 5-tuple.
5. (10 points) Let A be the language of strings over Σ = {0, 1} from the first day of class:
A = {1
a01b01a+b
: a, b ≥ 0}. Prove that A is not regular. (An informal interpretation
of this result is: DFAs cannot add in unary) Hint: 1
6. (15 points) We see in class on 4/15 how to convert any k-state NFA into an equivalent
2
k
-state DFA. This problem shows that this exponential blowup in the number of states
is necessary. Let A ⊂ {0, 1}
∗ be the set of all strings (of length at least 101) that have
a 0 exactly 100 places from the right hand end. That is
A = {w : |w| ≥ 101, w|w|−100 = 0}. (1)
(a) (5 points) Draw the state diagram for an NFA with 101102 states that recognizes
A. (You can use “· · · ” and don’t have to draw all 101102 states, as long as it’s
clear what the states/transitions would be in the omitted states) [Ray: Update: I
think you need 102 states. If you have 103 or 104 states, that’s fine.]
(b) (10 points) Show that no DFA on less than 2100 states can recognize A. Hint:2
1
In this class, we learn several methods for proving a language A is regular: constructing a DFA recognizing A, constructing an NFA recognizing A, finding a regular expression for A. However, we only learn
one method for proving a language is not regular. What is it?
2Give a proof by contradiction and assume such a DFA exists. Apply pigeonhole to all 2100 strings of
length 100 to get two strings x and y of length 100 that end up at the same state after digesting. Derive a
contradiction by considering the strings xz and yz for some carefully chosen string z.
(c) Sara Krehbiel, Ray Li 2
请加QQ：99515681 邮箱：99515681@qq.com WX：codinghelp
