Chris Pollett>Old Classes>CS305, Fall 1997>Homeworks
Read Chapter 1
Exercises p.26 0.3, 0.4, 0.6, 0.7, 0.8
Problems p.27 0.11
Read Sipser to p.60
Exercises p.83-84 1.1, 1.2, 1.4, 1.5, 1.6
Problem 6. Give an automata which accepts the following set of movie titles: Alien, ALiens, Alien3, Alien4, Alien5, ...
Read Sipser to p.100
Exercises p.85-90 1.9, 1.10b, 1.14, 1.31, 1.39
Exercise p. 120 2.3
Read Sipser to p.128
Exercises 2.4, 2.5, 2.17, 2.19, 2.20
Problem 6. Show the class of CFL's not closed under intersection. i.e., Give two CFL's the intersection of whom is not a CFL.
Read Sipser to p.144
Exercises 3.1, 3.4, 3.5, 3.6, 3.7, 3.8
Read Sipser to p.178
Exercises 3.9, 3.12, 3.13, 4.2, 4.17
Problem 6. Show that A={(M_1, M_2) | L(M_1)=L(M_2) and L(M_1), L(M_2) are CFL's} is undecidable.
Read Sipser to p.201
Exercises 5.1, 5.2, 5.4, 5.9, 5.15
Problem 6. Show a language C is co-Turing recognized iff
there exists a CFL D such that:
C={x | forall y (x,y) in D}.
Read Sipser to p.213-220
Exercises 6.15, 6.16, 3.14, 4.11, 4.12, 5.20
Prepared by Chris Pollett.