CSE460 Computability and Formal Language Theory

Fall, 2005

Description

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.
Class:
Tuesday s and Thursdays 3:00pm-4:20pm, 1225 Engineering Building 
Instructor: John Weng
Office: 2325 Engineering Building; phone: 353-4388; e-mail: weng@cse.msu.edu.  Telephones and emails are not appropriate for homework questions.
URL: http://www.cse.msu.edu/~weng/.
Office hours: Wednesdays and Thursdays 7:00pm - 8:00pm and by appointment.
Prerequisites: Knowledge comparable to that taught in
CSE 331 Algorithms and Data Structures
CSE 260 Discrete Structures in Computer Science
Text:
John C. Martin, Introduction to Languages and the Theory of Computation, McGraw Hill, 3rd Edition, 2003.

Course material

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