COM S 331: Theory of Computing, Summer 2021
Exam 1
Designated exam time 11:00 am – 12:40 pm(100 min), Thursday, June 3, on Gradescope.
You have 100 minutes to complete and submit this exam. There are three problems, worth 100
points in total. Any problem that you leave blank or indicate clearly that you do not want graded
will receive 20% credit. Every other problem will be graded and receive 0-35 points for problem 1
and 3, 0-30 for problem 2. All answers should be explained, at least briefly.
While taking the exam you MAY
• consult your own notes and the lecture notes;
• consult the textbook and the class lectures;
• contact the instructor or TA with questions about the exam. (We’ll try to answer promptly,
but cannot guarantee that.)
While taking the exam you may NOT
• post questions or any information about the exam (etc on chegg);
• discuss the exam with anyone except the instructor and TA;
• work with anyone else or access any other resources or websites.
1
Problem 1 (35 points). Prove the language L = {x ∈ {a, b, c}∗ | no two consecutive symbols in
x are the same} is regular.
(To help you understand L, here are some sample strings in and not in L.
Sample strings in L: �, a, ac, abc, abab, abcb, abacb
Sample strings not in L: aab, abbc, abccba, acbcc)
Solution To prove a language is regular, you can build a DFA/NFA for it, find a regular expression
that describes it, or utilize the closure properties of regular languages.
s
qa
qb
qc
∅
a
b
c
a
b
c
Σ
b
c
c
a
a
b
All the states in this DFA are accept states except the trash state, therefore any string that does
not reach the trash state will be accepted. Since the transition function is defined as δ(s, n) =
qn, δ(qn,m) = qm and δ(qn, n) = ∅ where n,m ∈ {a, b, c} and n 6= m, the only way to reach state
qn is with a symbol n from any other state (except ∅), and the only way to reach the trash state is
with n from state qn, thus only strings containing two same consecutive symbols will be rejected.
Another approach that you can use is the closure properties. The complement of this language
is L = {x ∈ {a, b, c}∗ | there exists two consecutive symbols in x that are the same} where we can
write it as Σ∗aaΣ∗ ∪ Σ∗bbΣ∗ ∪ Σ∗ccΣ∗. Since L is regular, L must be regular.
Problem 2 (30 points). For a language L, we define LR = {x ∈ Σ∗ |xR ∈ L}. Prove that if L is
regular, then LR is regular.
(To help you understand the relationship between L and LR, here is an example. If L = {ab, abc, acbba},
then LR = {ba, cba, abbca}).
Solution Similar to proving the complement of a regular language is regular by flipping the accept
and non-accept state, to prove the reverse of a regular language is also regular, we can just flip the
transitions in the DFA of language L.
2
Given a DFA M = (Q,Σ, δ, s, F ) such that L(M) = L, we can just construct a NFA N = ({Q ∪
{s′}},Σ, δ′, s′, {s}). We can formally define the transition function as δ′(s′, ε) = f such that f ∈ F ,
and ∀q, p ∈ Q, a ∈ Σ, δ′(q, a) = p where δ(p, a) = q. Here we flipped the transitions in M , set the
start state in M as the only accept state in N , added a new start state s′ and ε-transitions from s′
to all f ∈ F .
x ∈ L, then there must be a path from s to some f ∈ F in M while reading x ⇔ xR ∈ LR as there
is a path from some f ∈ F to s in N and all f can be reach from s′ with ε-transition. Since M
accepts x⇔ N accepts xR, we showed that we can build a NFA N such that L(N) = LR, thus LR
is regular when L is regular.
Problem 3 (35 points). Use pumping lemma to prove the language L = {anbm |n,m ∈ N, n ≤
3m} is not regular.
(To help you understand L, here are some sample strings in and not in L.
Sample strings in L: �, b, ab, aab, aaab
Sample strings not in L: a, ba, aba, aaaab)
Solution Assume L is regular and p is the pumping length. Let s = apbp/3, s ∈ L and |s| ≥ p. s
can be divided into x, y, z such that x = ap−i−j , y = ai, z = ajbp/3 where i, j ∈ N, i > 0 (condition
(ii)) and |xy| = p − j ≤ p (condition (iii)). However, if we pump up the string, such that xy2z =
xyyz = ap+ibp/3, then it will violate condition (i) since p+ i > 3(p/3) and xyyz /∈ L. Thus L is not
regular.
3