CSE460 Computability and Formal Language Theory

Fall, 2017


Formal models of computation such as finite state automata, pushdown automata and Turing machines. Formal definitions of languages, problems, and language classes including recursive, recursively enumerable, regular, and context free languages. The relationships among various models of computation, language classes, and problems. Church's thesis and the limits of computability.
Tuesday s and Thursdays 3:00pm-4:20pm, 1257 Anthony Hall
Instructor: John Weng
Office: 3144 Engineering Building; phone: 353-4388; e-mail: weng@cse.msu.edu.
URL: http://www.cse.msu.edu/~weng/.
Office hours: Wednesdays and Fridays 5:00pm - 6:00pm and by appointment.
TA: Atra Akandeh
Office: 3203 (bone Lab) Engineering Building; Tel: (517) 432-1650; e-mail: akandeha@cse.msu.edu.
URL: http://www.cse.msu.edu/~weng/.
Office hours: Wednesday 6:00pm - 7:00pm, and Fridays 9:00am - 10:00am, and by appointment.
Prerequisites: Knowledge comparable to that taught in CSE 331 : Algorithms and Data Structures
John C. Martin, Introduction to Languages and the Theory of Computation, McGraw Hill, 4th Edition, 2011.

Course material

 Back To Weng's Home Page: http://www.cse.msu.edu/~weng/