4011 Formal Language and Automata Theory

Overall Course Description

4011 is a required class that CSci majors should take in their junior year. In the class students learn theoretical foundations of computer languages and computability. Students will encounter the finite state machine, pushdown automaton, and Turing machine models of computation, and will also learn about language classes such as the regular and context-free languages classes. The issues of decidability, undecidability, and the limits of computability will be studied, and the techniques of reductions and diagonalization as a means for establishing such properties for given languages will be explored. Further topics include time and space complexity, and the notion of NP-completeness.

Catalog Description

Logical and mathematical foundations of computer science. Formal languages and their correspondence to machine models. Relevance to practical issues such as lexical analysis, string matching and parsing. Decidability, undecidability, and the limits of computability. Computational complexity.

Course Outline

Optional or additional topics include the Recursion Theorem, the undecidability of number theory, and rudimentary descriptive complexity (Chapter 6); and space complexity (Chapter 8).

Why This Class is Important and its Role in the Curriculum

For most students this is their only look at computability, which is a fundamental and important concept in computer science. Also, many of the concepts used extensively in 4011, such as Turing machines, finite automata, or context-free grammars, occur heavily in the design and implementation of programming languages, as well as in other areas of computer science.

Most students will take 4011 in their junior year.

Prerequisites and Rationale

CSci 1902 (Structure of computer programming II) and CSci 2011 (Discrete Structures of Computer Science). From 1902 students will need some exposure to structured programming, elementary data structures, and recursion before studying computability and language foundations. From 2011 students need experience with proofs involving mathematical concepts they will use in computability.

Classes Having 4011 as a Prerequisite and Rationale

4011 is a prerequisite for 5106 (Programming Languages). A good number of topics in 5106 rely on concepts from 4011.

Class Format

3 hours of lecture + 1 hour of recitation per week.

Probable Textbook

Michael Sipser “Introduction to the Theory of Computation” 2nd Edition Thomson Publishing, 2006.

Outcomes

Upon successful completion of the class, students should be able to:

1. Design NFA and DFA, and provide regular expressions for particular languages;
2. Provide context-free grammars and argue their correctness;
3. Show that given languages are decidable, undecidable, or non-computable by using reductions or diagonalization arguments;
4. Show that given problems are in P, NP, or are NP-complete.