CSCE 433/627 Formal Languages and Automata / Theory of Computability
Fall 24

Instructor: Sing-Hoi Sze
Email: shsze@cse.tamu.edu
Meeting: TR 8-9:15 ZACH 310
Office Hours: TR 9:30-10:30 PETR 427 or on zoom

Textbook

Sipser M. Introduction to the Theory of Computation.

Goal

This course studies formal models of computation and the relationships between them. The course will focus on the question "what is computable" versus "what is not computable" in each model.

Topics

• Finite automata and regular expressions: deterministic finite automata, nondeterministic finite automata, regular expressions, equivalence, closure properties, pumping lemma.
• Context-free grammar and pushdown automata: context-free grammar, pushdown automata, equivalence, closure properties, Chomsky normal form, pumping lemma.
• Turing machines: Turing machines, variants, nondeterministic Turing machines, decidability and undecidability, NP-completeness.

Grading

• Homework assignments (30%): written assignments handed out every one or two weeks.
• Two midterms (20% each).
• One final exam (30%).
• 627: a short paper on a topic of interest (pass/no pass).

Prerequisites

• 433: junior or senior classification or approval of instructor.
• 627: graduate standing or approval of instructor.