Formal Language & Automata Theory (BTCS 502-18)

Course Objectives

This course aims to:

Introduce the fundamental concepts of formal languages and automata theory.
Enable students to understand the relationship between different classes of languages and automata.
Teach students to design and analyze finite automata, pushdown automata, and Turing machines.
Equip students with the ability to prove the decidability and undecidability of problems.

Course Outcomes

Upon completion of this course, students will be able to:

Design finite automata, pushdown automata, and Turing machines for specific languages.
Analyze the capabilities and limitations of different types of automata.
Prove the equivalence of different formalisms for representing languages.
Identify and prove the decidability and undecidability of problems.
Apply the concepts of formal language theory to compiler design and other areas of computer science.

Detailed Syllabus

Module 1: Introduction & Finite Automata

Alphabets, Strings, and Languages
Regular Expressions
Finite Automata: Deterministic Finite Automata (DFA), Non-deterministic Finite Automata (NFA), Equivalence of DFA and NFA, Minimization of DFA.
Closure Properties of Regular Languages: Union, Intersection, Complementation, Concatenation, Kleene Closure.
Pumping Lemma for Regular Languages.

Module 2: Context-Free Grammars and Pushdown Automata

Context-Free Grammars (CFG)
Derivation Trees and Ambiguity
Chomsky Normal Form
Greibach Normal Form
Pushdown Automata (PDA)
Equivalence of CFG and PDA
Pumping Lemma for Context-Free Languages.

Module 3: Turing Machines & Undecidability

Turing Machines: Definition and Model
Variations of Turing Machines
Universal Turing Machine
Church-Turing Thesis
Recursive and Recursively Enumerable Languages
Undecidability: Halting Problem, Post Correspondence Problem, Other Undecidable Problems.

Suggested Readings

Introduction to Automata Theory, Languages, and Computation by John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman.
Theory of Computation by Michael Sipser.
An Introduction to Formal Languages and Automata by Peter Linz.