COM S 331: Theory of Computing, Summer 2021
Homework Assignment 3
Due at 11:59PM, Wednesday, June 2, on Gradescope.
Problem 10 (20 points). Prove: for every NFA N, there exists an NFA N’ with a single final
state, i.e., F of N’ is a singleton set. (Hint: you can use �-transitions in your proof.)
Solution The general idea is that we can just add a new final state and have epsilon transitions
from all the old final state to the new final state.
Given an NFA N = (Q,Σ, δ, s, F ), we can build an equivalent NFA N ′ = (Q′,Σ, δ′, s, F ′) where
|F ′| = 1. Let Q′ = Q∪{f}, F ′ = {f}, δ′(q, a) = δ(q, a) for ∀q ∈ Q and ∀a ∈ Σ∪{�}. The only thing
we’ll add here is δ′(q, �) = f for ∀q ∈ F . Since N ′ has all the transitions of N , a string can only
reach the accept state in N ′ if and only if it reaches an accept state in N , thus they are equivalent.
Problem 11 (20 points). Give a regular expression that generates the language L = {x ∈
{a, b, c}∗|a is never followed immediately by b}.
Sample strings in L: aa, bb, cc, ac, acb
Sample strings not in L: ab, cab, cabb, abc
Solution (a∗c ∪ b)∗a∗ is one of the acceptable answer. There are plenty of equivalent regular ex-
pressions that describe this language. You can also build a DFA/NFA for this language if you’re
more comfortable in doing that and then convert it to an equivalent regex.
Problem 12 (20 points). Use the procedure described in class, convert the following DFA to an
equivalent regular expression.
21
b
a
b
a
Solution Removing state 1 first will result in a∗b(a ∪ ba∗b)∗ OR removing state 2 first to result in
(a ∪ ba∗b)∗ba∗
1
Problem 13 (20 points). We define the avoid operation for languages A and B to be
A avoid B = {w |w ∈ A and w does not contain any string in B as a substring}
Prove: if A and B are both regular languages, then A avoid B is regular.
(Hint: consider showing the language C = {w |w contains some string in B as a substring} is regular)
Solution You can use closure properties of regular languages for this problem. Assuming both
A and B are regular, we can create a new language C as defined in the hint as C = Σ∗BΣ∗. C
is clearly regular because B and Σ∗ are regular and concatenation of regular languages is regular.
Then AavoidB = A ∩C where C is the complement of C (all the strings that do not contain some
string in B as a substring), and complement of a regular language is regular, intersection of regular
languages is also regular, thus AavoidB is regular.
Problem 14 (20 points). Let A = {1ky | y ∈ {0, 1}∗ and |y|1 ≤ k, for k ≥ 1}.
Prove A is not regular using pumping lemma.
Solution According to the pumping lemma, if A is regular, then there must be a pumping length
p where if s is some string in A with length of at least p, then s can be divided into three piece,
s = xyz while satisfying the following conditions.
(i) ∀i ≥ 0, xyiz ∈ A
(ii) |y| > 0
(iii) |xy| ≤ p
Assume A is regular and p is the pumping length. Let s = 1p01p, s ∈ A and |s| > p. s can
be divided into x, y, z such that x = 1p−a−b, y = 1a, z = 1b01p where a, b ∈ N, a > 0 (condition
(ii)) and |xy| = p − b ≤ p (condition (iii)). However, if we pump down the string, such that
xy0z = xz = 1p−a01p, then it will violate condition (i) since xz /∈ A. Thus A is not regular.
*Why not just say xy = 1p so x = 1p−a, y = 1a, z = 01p? Because we have to show that no
matter how we split the string into 3 parts while satisfying the conditions, once we pump up
or down the string it will fail condition (i). Therefore we will have to show when |xy| = p (so
x = 1p−a, y = 1a, z = 01p) and also when |xy| < p (x = 1p−a−b, y = 1a, z = 1b01p).
*Also, never set a specific value for p (eg saying p = 3) because you will have to show that no matter
what the pumping length is, the language will not satisfy one or more of those conditions.
More on pumping lemma in Theorem 1.70 of textbook and also lecture on 6/1.
2