Topics List for Qualifying Examination: Automata & Languages

 
 

References
Introduction to the Theory of Computation by Michael Sipser. Study the following chapters:

Regular Languages: 1.1 to 1.4
Context Free Languages: 2.1 to 2.3
Turing Machines: 3.1 to 3.3
Decidability: 4.1 and 4.2


Other References
It might be helpful to also study from Introduction to Automata Theory, Languages and Computation by Hopcroft and Ullman.  Study the following chapters:  

2.1 - 2.5
3.1 - 3.3
4.1 - 4.5
5.1 - 5.3
6.1 - 6.2
7.1 - 7.7
8.1 - 8.3


Note: The students can study the same materials from other textbooks.