Description
Problem 1 (20 points)
If L is any language, let L1
2
−
be the set of all first halves of strings
in L so that
L1
2
− = { w | for some w0
, |w| = |w
0
| & ww0
∈ L }.
Prove that, if L is regular, then so is L1
2
−
.
Hint: Meet In The Middle. Let A, B be automata such that
L (A) = L and L (B) = L R (L R is defined as in Problem 2 in
HW2). Use A and B to construct an automaton C that recognizes
L1
2
−
.
2 / 6
CS 331: Theory of Computing
Problem 2 (20 points)
A universal finite automaton (UFA) A is a 5-tuple hQ, Σ, Q0, δ, Fi
(syntactically just like an NFA) that accepts a word w if every run
of A over w ends in F. Note that an NFA accepts a word if there
exists a run of A over w that ends in F.
Prove that UFAs recognize the class of regular languages, that is,
a language L is recognized by a UFA if and only if L is regular.
Hint: Given a UFA A, can you construct an NFA that recognizes
L (A), the complement of L (A)?
3 / 6
CS 331: Theory of Computing
Problem 3 (20 points)
Let Σ = {0, 1}. A palindrome is a word that reads the same forward
and backward. For example, “ABLE WAS I ERE I SAW ELBA” is
palindromic. Prove that the following language
{ w ∈ Σ
∗
| w is not a palindrome }
is not regular.
4 / 6
CS 331: Theory of Computing
Problem 4 (20 points)
Let k > 1 and Lk = {, a, aa, . . . , a
k−2
}. Prove the following
statements:
1 Lk can be recognized by a DFA with k states. (5 points)
2 Lk cannot be recognized by any DFA with k − 1 states. (15 points)
Hint: Use the pigeonhole principle as in the proof of the Pumping
Lemma to prove Part 2.
5 / 6
CS 331: Theory of Computing
Problem 5 (20 points)
Let Ln = {w ∈ {0, 1}
∗
| the n-th letter of w from the end is 1 } for
n ≥ 1. Prove that
an NFA with n + 1 recognizes Ln (5 points).
any DFA that recognizes Ln needs at least 2n
states (15 points).
Hint: Let Sn be the set of all words of length n. Show that any DFA
A that recognizes Ln should have a distinctive state qw for each
w ∈ Sn such that whenever A reaches qw, w is the suffix of the
word that has been read by A.
6 / 6
CS 331: Theory of Computing
