Formal Language and Automata Theory

Course Objectives

At the end of the course, students will

• know the concepts formal languages, formal grammars, and automata,
• be introduced to the mathematical notation of sets, graphs, and trees,
• understand about (Finite) Automata concepts,
• study and understand about grammars, languages and normal forms, and
• be introduced to the mechanism of Turing Machine.

Course Description

Introduction to the theory of computation (sets, functions and relations, graphs and trees, languages, grammars, automata); finite automata (deterministic and nondeterministic finite automata, equivalence of deterministic and non-deterministic finite automata, reducing number of states in finite automata); regular languages and regular grammars (regular expressions, connection between regular expressions and regular languages, regular grammars); context free languages (context free grammars, parsing and ambiguity, context free grammars and programming languages); simplification of context free grammars and normal forms; push down automata (nondeterministic push down automata, push down automata and context free languages, deterministic push down automata and deterministic context free languages).

Course Content

1. Basics
2. Introduction to grammars
3. Regular languages
4. Context Free Languages
5. Push Down Automata