CS 332: Theory of Computation Professor Mark Bun Boston University February 5, 2020
Homework 2 – Due Monday, February 10, 2020 before 2:00PM
Reminder Collaboration is permitted, but you must write the solutions by yourself without assistance, and be ready to explain them orally to the course staff if asked. You must also identify your collaborators. Getting solutions from outside sources such as the Web or students not enrolled in the class is strictly forbidden.
Exercises Please practice on exercises and solved problems in Chapter 1 and on the exercise below. The material they cover may appear on exams.
1. (Conversion procedures) Use asymptotic (big-O) notation to answer the following ques- tions. Provide brief explanations.
(a) Let N be an NFA that has n states. If we convert N to an equivalent DFA M using the procedure we described, how many states would M have?
(b) Let M be a DFA that has n states. If we convert M to an equivalent regular expression R using the procedure we described, how many symbols would R have in the worst case?
Problems There are 3 mandatory problems.
1. (Non-regular languages) Prove that the following languages are not regular. You may use the pumping lemma and the closure of the class of regular languages under union, intersection, complement, and reverse.
(a) L1 ={0n1m |n,m≥0andn=m2}.
(b) L2 = w | w ∈ {0, 1}∗ is not a palindrome. A palindrome is a string that reads the
same forward and backward.
(c) L3 = 1ky | y ∈ 0,1∗ and |y| = k.
(d) L4 =aibjck |i,j,k≥0andifi=1thenj=k.
(e) L4 satisfies conditions of the pumping lemma. Explain why this does not contradict the
fact that L4 is not regular.
2. (Number of states) Let Σ = {a, b}. For each k ≥ 1, let Ck be the language consisting of
all strings that contain an a exactly k places from the right-hand end. Thus Ck = Σ∗aΣk−1.
(a) Describe an NFA with k + 1 states that recognizes Ck in terms of both a state diagram
and a formal description.
(b) If a DFA enters different states after reading two different input strings xz and yz with the same suffix z then the DFA must enter different states after reading input strings x and y. Explain why.
1
(c) Find 2k strings on which every DFA recognizing Ck must enter different states. (Hint: Start by finding 2 such strings).
(d) Prove that for every k, no DFA with fewer than 2k states can recognize Ck. (Hint: Combine parts (b) and (c).)
3. (DFAs, NFAs, regular expressions and converting between them)
(a) (Description to NFA) Let Σ = {A, O, L}. Give an NFA with 4 states recognizing the
language{w∈Σ∗ |wendsinLOLorinLL}.
(b) (NFA to DFA) Convert your NFA from part (a) to an equivalent DFA. Give only the
portion of the DFA that is reachable from the start state.
(c) (Rex to NFA) Use the procedure described in class (also in Sipser, Lemma 1.55) to
convert (T(GGA)∗ ∪ C)∗ to an equivalent NFA. Simplify your NFA.
(d) (Description to rex) Give a regular expression that generates the following language:
{w | w is a binary string and the number of 0s in w is divisible by 3}.
2