#### CSC 437: Theory of Computation and Automata

Offered Under: B.Sc. in Computer Science (CSC)
Description

This course introduces the mathematical foundations of all computation. Core concepts of automata, formal languages, grammar, decidability and computability will be discussed. Topics include: Basic notions: string, prefix, suffix, substring, concatenation; Cardinality; Distinction between uncountable and countable infinite; Different proof techniques: proof by construction, proof by contradiction, pigeon hole principle; Deterministic and non-deterministic  finite state automata; Regular language, regular expression; Equivalence of NFA and DFA; Pumping Lemma, non regular languages; Context free grammar (CFG) and push down automata (PDA; Chomsky normal form; Parsing; Turing machine, Universal Turing machine and Halting problem;  Goedel numbering; P/NP complexity.  Students taking this course should possess a strong background in discrete mathematics and data structures.

Course Type Major 3 45
Expected Outcome(s):
• Defineand describe formal models of computation, such as finite automata, pushdown automata, and Turing machines.
• demonstrate their the understanding of key notions, such as algorithm, computability, decidability, and complexity through problem solving.
• Convert between finite automata, regular grammars, and regular expression representations of regular languages.
• Apply the pumping lemma for regular languages to determine if a language is regular.
• Convert between grammars and push-down automata for context-free languages.
• Applylearned concepts to create proofs regarding the computational complexity of various problems.

Suggested Books:
1. Elements of the Theory of Computation (2nd Edition) by H. Lewis, C. Papadimitriou
2. Introduction to the Theory of Computation by M. Sipser
3. Introduction to Automata Theory, Languages & Computation (3rd Edition) by J. Hopcroft, R. Motwani, J. Ullman

Grading Policy:

Biweekly Quiz, One Midterm Exam, One Final Exam, Project

Letter Grade Marks Grade Point
A 90 - 100 4.00
A- 85 - 89 3.70
B+ 80 - 84 3.30
B 75 - 79 3.00
B- 70 - 74 2.70
C+ 65 - 69 2.30
C 60 - 64 2.00
C- 55 - 59 1.70
D+ 50 - 54 1.30
D 45 - 49 1.00
F 00 - 44 0.00