CS 332: Theory of Computation Professor Mark Bun Boston University March 18, 2020
Homework 5 – Due Wednesday, March 25, 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 the following exercises and solved problems in Chapter 4: 4.1 – 4.8, 4.10, 4.12, 4.14, 4.25. The material they cover may appear on exams.
Note For all proofs which require you to describe a Turing machine, please give a high-level description as in Chapter 4.1 of Sipser or in Lecture 13.
Problems There are 2 mandatory problems. 1. (Decidable languages)
(a) (AGREEDFA) Consider the problem of determining, given two DFAs, whether there is a string that both of them accept.
i. Formulate this problem as a language AGREEDFA.
ii. Show that AGREEDFA is decidable by using a decider for one of the languages from
Chapter 4 in the book.
iii. Show that AGREEDFA is decidable by testing the two DFAs on all strings up to a
certain length. Calculate the size that works.
(b) (REVDFA) Consider the problem of determining if the languages of two given DFAs are reverses of each other.
i. Formulate this problem as a language REVDFA and show that it is decidable.
ii. Why does a similar approach fail to show that REVPDA is decidable? (This language
is defined analogously to REVDFA, with PDAs instead of DFAs as inputs.)
(c) (Prefix of a generated string) A string w is called a prefix of string s if s starts with w.
i. Give a regular expression for all strings over alphabet Σ for which w is a prefix.
ii. Let L = {⟨G,w⟩ | G is a CFG, w is a string, and w is a prefix of some string s
generated by G}. Show that L is decidable.
Hint: The result of Problem 2.18a in the book might be useful.
2. (Countable and uncountable sets and diagonalization)
(a) Apolynomialinvariablexisanexpressionoftheformc0+c1x+c2x2+c3x3+···+cdxd, where d is a non-negative integer and c0, · · · , cd are constants, called coefficients. Let P be the set of polynomials with integer coefficients. Show that P is countable.
1
(b) Let F be the set of all context-free languages over alphabet {0,1}. Show that F is countable.
(c) Let L be the set of all languages over alphabet {0}. Show that L is uncountable using a proof by diagonalization.
(d) Let S be the set of all infinite sequences (x1, x2, . . . ) where xi is a natural number and xi+1 ≥ xi for every i. Show that S is uncountable using a proof by diagonalization.
2