Please Note: Someone other than me will be responsible for the breadth exam in formal languages beginning in the fall of 2010. Consequently, the reading list for the exam, and the scope of the exam, may change. Contact the Graduate Studies Committee for more information.
The reading list for the breadth exam is Chapters 1-5 and 7-9 of Introduction to Automata Theory by Hopcroft, Motwani and Ullman, Addison-Wesley, 2001.
But, until further notice, the breadth exam will have two questions. The first question will be a grammar synthesis problem. The second question will be a DFA synthesis and proof of correctness problem. See the past exams listed below for sample problems. (The Fall 2006 exam only had one problem.)
Before the breadth exam, I will give a help session in which I work some relevant problems and answer questions about the scope of the exam.