Theory of Automata

Objectives: Main objective of the course is to cover basic computation models that provide basics of computing in various computer science fields. The purpose of the course is to discuss the computation theories in detail; their capabilities, limitation, and applications. The course will also provide a baseline for compiler construction.

Contents: Introduction to Automata, Language, Alphabets, and strings; Kleen Closure; Recursive definition of sets, Regular Languages and Regular Expressions; Finite Automata; Transition Graphs and Generalized Transition Graphs; Non-determinism; Non deterministic Finite Automata (NFA), NFA-A, and Kleen's Theorem; Minimal Finite Automata; Finite Automata with outputs: Moore and Mealy Machines; Regular and Non-regular Languages; Pumping Lemma for Regular Languages; Context Free Grammars (CFG) and Regular Grammars; Derivation trees and ambiguity, Simplified forms and Normal Forms; Context free and Non-Context free languages; Pushdown Automata (PDA), Deterministic PDA; Turing machines and variation in Turing machines; Decidability.