This course is of interest to those students seeking a deeper understanding of classical formal language theory and computability.

Prerequisites:  COMP 3602 or the former COMP 3719

Availability: ⚠ This course is not planned to be offered in the near future.

Course Objectives

This course is an in-depth discussion of classical models of computation, their computational power and their use in the classification of problems into classes. In addition, the correspondence between the models of computation and the different types of grammars is established.

Representative Workload

• Assignments (5) 40%
• In-class Exam 25%
• Final Exam 35%

Representative Course Outline

• Review of mathematical preliminaries:
• Sets
• Binary relations and equivalence relations
• partial orders
• Functions
• Finite and infinite sets
• Countable and non-countable sets
• Alphabet strings and string operations
• Languages and operations on languages
• Finite state automata:
• Minimization
• Nondeterminism
• Closure properties of regular languages
• Regular expressions
• Pumping lemma
• Pushdown automata:
• Context-free languages and grammars
• Equivalence
• Ambiguity
• Pumping lemma
• Parsing
• Turing machines:
• Nondeterminism
• Multiple tapes
• Recursive and recursively enumerable languages
• The Chomsky hierarchy
• Decidability of problems concerning regular languages, context free languages and general languages
• Undecidability of the Halting Problem
• Reducibility and its application in proving undecidable and decidable languages
• The Post correspondence problem
• Oracle reductions and the arithmetic hierarchy
• The Recursion Theorem and its applications

Notes

• Students can receive credit for only one of Computer Science 4741 or the former Computer Science 3740.

Page last updated May 24th 2021