**Description**: Grammars, sequential machines, equivalence, minimalization, analysis and synthesis, regular expressions, computability, unsolvability, Gödel’s theorem, Turing machines.

**Objectives**

- Students can write rigorous proofs.
- Students can compose analytical arguments.
- Students can conduct theoretical research on topics in fields of their interests.
- Students can write theoretical papers.

**Course Learning Outcomes**: See objectives.

**Program Learning Outcomes**

- a. Students can apply knowledge of computing and mathematics appropriate to the discipline
- b. Students can analyze a problem, and identify and define the computing requirements appropriate to its solution

**Prerequisites**: 311 or consent

**Textbook(s)**: “Introduction to Automata Theory, Languages, and Computation,” John E. Hopcroft and Jeffrey D. Ullman

**Grading**: A few assignments (100%) in which students have to solve given theoretical problems and write technical reports on their solutions to the given problems, where the last assignment is the take-home final exam

**Schedule**

- Weeks 1-2: Basics of Formal Languages and Automata Theory (Review of ICS241)
- Weeks 3-5: Regular Sets, Regular Grammars and Finite Automata. Assignment 1
- Weeks 6-8: Context-Free Languages, Regular Grammars and Pushdown Automata, Assignment 2
- Weeks 9-10: Turing Machines
- Weeks 11-12: Computability
- Weeks 13-15: Computational Complexity Theory Assignment 3
- Week 16 Review
- Week 17: Final exam