COMP 301 - Study Guide for Test 1

The material covered on the test will be taken from chapters 1 and 2 of Sipser's book. Pretty much all of chapter 1 was covered. For chapter 2 you can safely ignore the sections on ambiguity, Chomsky normal form and the proof that CFGs and PDAs are equivalent (though not the result itself).

A good approach to studying would be to try some of the problems at the end of each of the chapters covered above. Use the assignment problems and the study problems as a guide:

• Chapter 1: 1.1,1.2,1.3,1.4,1.5,1.6,1.7,1.8,1.9,1.10,1.11, 1.12,1.13,1.14,1.15,1.16,1.17,1.18,1.23,1.24,1.25,1.26,1.27, 1.28,1.29,1.30,1.31,1.32,1.34,1.35,1.36,1.37,1.38, 1.41,1.42,1.43,1.44.
• Chapter 2: 2.1,2.2,2.3,2.4,2.5,2.6,2.7,2.8,2.9,2.10,2.13,2.15,2.16,2.17, 2.18,2.22,2.23,2.25.

Report problems to dkrizanc@wesleyan.edu