CSE460 Computability and Formal Language Theory

Fall, 2020

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:
Tuesdays and Thursdays 3:00pm-4:20pm, Zoom
Instructor: John Weng
Office: Virtual; e-mail: weng@cse.msu.edu.
URL: http://www.cse.msu.edu/~weng/.
Office hours: Mondays and Fridays 5:00pm - 6:00pm and by appointment, Zoom.
TA: Jamie Schmidt
Office: Virtual; e-mail: schmi710@msu.edu.
Office hours: Tuesday 11:99am - 12:00pm, Fridays 10:30am - 11:30am and by appointment.
Prerequisites: Knowledge comparable to that taught in CSE 331 : Algorithms and Data Structures
Text:
John C. Martin, Introduction to Languages and the Theory of Computation, McGraw Hill, 4th Edition, 2011.

Course material

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