CS 332: Theory of Computation Professor Mark Bun Boston University February 13, 2020
Homework 3 – Due Tuesday, February 18, 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 2. The material they cover may appear on exams. Pay particular attention to Problem 2.18. It will be helpful for one of the problems on this homework and you can use the result of this problem without proof.
Problems There are 4 mandatory problems and one bonus problem.
1. (NFA to rex) Use the procedure described in Lemma 1.60 to convert the following finite
automaton to a regular expression.
G
q2 C
q0 A q1
T
G
no more than requested). Unless specified otherwise, the alphabet is Σ = {0, 1}. (a) L1 = {w| w starts with 0i1 and ends with 10i for some i ≥ 0}.
Use at most 3 variables.
(b) L2 = {w| w = wR which means w is a palindrome}
Recall that wR represents string w written backwards. Use at most 2 variables. (c) L3 = {w| w represents a binary number that starts with 1 and is divisible by 3}.
Use at most 4 variables.
(d) Consider the alphabet Σ = {0,1,#}. Let L4 = {x1#x2#···#xk| k ≥ 1, every xi ∈ {0,1}∗ for i = 1,…,k, and there exists a pair of indices l,m with l ̸= m such that xl = xRm}. Recall that wR represents string w written backwards. Use at most 4 variables.
3. (PDAs) Draw state diagrams of PDAs (with as few states as you can) that recognize the following languages. Write algorithmic descriptions for your PDAs.
1
q3
2. (CFGs) Give CFGs that generate the following languages. Use as few variables as you can (and
(a) The language L1 from Problem 2(a): (i) diagram; (ii) algorithmic description. (b) The language L2 from Problem 2(b): (i) diagram; (ii) algorithmic description.
4. (Non-CFLs) Prove that the following languages are not context-free.
(a) A = {0m1n0m1n | m,n ≥ 0}.
(b) The following language over the alphabet {a, b, c}:
B = {aix| i ≥ 0,x ∈ {b,c}∗, and if i = 1 then x = ww for some string w}.
(Careful: B satisfies the pumping lemma for CFLs! Make sure you understand why, but you don’t need to write it down.)
6∗ (Optional, no collaboration is allowed) Give a PDA that recognizes the following language overthealphabetΣ={0,1}:L={xyz|x,z∈Σ∗ andy∈Σ∗1Σ∗,where|x|=|z|≥|y|}.
2