CMPSC 464: Intro to Theory of Computation Dr. Meiram Murzabulatov
Pennsylvania State University
Homework 5
Due Thursday, April 4 at 3pm
Exercises Please practice on exercises and solved problems in Sipser, Chapter 7. Problems
1. (5+5=10 points) Sipser, Problem 7.11.
Spring 2019
2. (2+2+6=10 points) An exponentiation cipher encodes a message A using a ciphertext
C = Ae( mod p) where p is a prime number and e is an integer exponent. (Here A and C are also integers.) You are given integers A, C, e and p, and you would like to determine whether C is a valid ciphertext for message A.
(a) Formulate this problem as a language EC.
(b) Explain why the following algorithm for EC does not run in polynomial time: Compute Ae using e − 1 multiplications. Take the result modulo p using one integer division, and compare the answer to C.
(c) Show that EC ∈ P. Hint: First solve it when e is a power of 2.
3. (3+7=10 points) Prove that P is closed under
(a) concatenation
(b) star (Hint: Use dynamic programming. On input y = y1 · · · yn for yi ∈ Σ, build a table
indicating for each i ≤ j whether the substring yi ···yj ∈ A∗ for any A ∈ P.)
1