Formal language theory is a collection of formal computational methods drawn chiefly from fields such as mathematics and computer science. Formal languages can be used to represent the syntax of axiomatic systems that are studied in the guise of logical calculi, or as models of richer information-encoding systems like natural languages or human cognition. In philosophy of mathematics, there was an ambition to reduce all of math to the syntactic manipulation of formal languages. Beyond linguistics and philosophy, formal language theory also has practical applications in virtually every area where computers manipulate formal systems, such as natural language processing, artificial intelligence, and programming more generally. This course offers an introduction to this field and to selected applications in linguistics, philosophy, and computer science. Topics to be discussed include set theory, algebra, automata theory, the Chomsky hierarchy, parsing, tree-adjoining grammars, and effective decidability. The course does not presuppose any specific background in math or computer science; but students are required to have already taken one of the listed prerequisites, or to have equivalent preparation as determined by the instructors.
Introduction to the theory of computation by Michael Sipser (ISBN: 9781133187790)
We will make a limited amount of textbooks available to students free of charge as a semester loan. Contact us if you are interested.
This course has been awarded a team-teaching stipend by the NYU Center for the Humanities, whose support is gratefully acknowledged.