CMPSC 464: Intro to Theory of Computation Dr. Meiram Murzabulatov
Pennsylvania State University
Homework 4
Due Friday, March 1 at 11:59pm
Exercises Please practice on exercises and solved problems in Sipser, Chapter 3.
Problems
Spring 2019
1. (4 points) Sipser, 3.2b. Please use the same representation for your configurations as on p. 168.
2. (4 points) Sipser, 3.7
3. (6 points) Formulate the language that Mbad in Problem 2 was intended to recognize and describe a correct TM that recognizes this language.
4. (6 points) Show that the class of decidable languages is closed under concatenation.
1