CSC 311 - Theory of Automata

Course objectives

The course introduces fundamental concepts in automata theory and formal languages including grammar, finite automaton, regular expressions, formal language, pushdown automaton, and Turing machine. Not only do they form basic models of computation, but are also the foundation of many branches of computer science, e.g., compilers, software engineering, concurrent systems, etc.

Course learning outcomes (CLOs)

CLO-1 - Explain and manipulate the different concepts in automata theory and formal languages such as formal proofs, automata, regular expressions, Turing machines etc. [C2 (Understand)]

CLO-2 - Prove properties of languages, grammars and automata with rigorously formal mathematical methods. [C2 (Understand)]

CLO-3 - Design of automata, RE and CFG. [C3 (Apply)]

CLO-4 - Transform between equivalent NFAs, DFAs and REs, Moore to Mealy and vice versa. [C3 (Apply)]

CLO-5 - Define Turing machines performing simple tasks. [C2 (Understand)]

Course Outline

Finite State Models: Language definitions preliminaries, Regular expressions/Regular languages, Finite automata (FAs), Transition graphs (TGs), NFAs, Kleene’s theorem, Transducers (automata with output), Pumping lemma and non-regular language Grammars and PDA: CFGs, Derivations, derivation trees and ambiguity, Simplifying CFLs, Normal form grammars and parsing, Decidability, Context sensitive languages, grammars and linear bounded automata (LBA), Chomsky’s hierarchy of grammars Turing Machines Theory: Turing machines, Post machine, Variations on TM, TM encoding, Universal Turing Machine, Defining Computers by TMs.