Syllabus - Formal Language & Automata Theory (CB-301)

Computer Science and Business System

Formal Language & Automata Theory (CB-301)

III

Unit 1

Introduction

Alphabet, languages and grammars, productions and derivation, Chomsky hierarchy of languages.

Regular languages and finite automata

Regular expressions and languages, deterministic finite automata (DFA) and equivalence with regular expressions, nondeterministic finite automata (NFA) and equivalence with DFA, regular grammars and equivalence with finite automata, properties of regular languages, Kleene’s theorem, pumping lemma for regular languages, Myhill-Nerode theorem and its uses, minimization of finite automata.

Unit 2

Context-free languages and pushdown automata

Context-free grammars (CFG) and languages (CFL), Chomsky and Greibach normal forms, nondeterministic pushdown automata (PDA) and equivalence with CFG, parse trees, ambiguity in CFG, pumping lemma for context-free languages, deterministic pushdown automata, closure properties of CFLs.

Unit 3

Context-sensitive languages

Context-sensitive grammars (CSG) and languages, linear bounded automata and equivalence with CSG.

Unit 4

Turing machines

The basic model for Turing machines (TM), Turing recognizable (recursively enumerable) and Turing-decidable (recursive) languages and their closure properties, variants of Turing machines, nondeterministic TMs and equivalence with deterministic TMs, unrestricted grammars and equivalence with Turing machines, TMs as enumerators.

Unit 5

Undecidability

Church-Turing thesis, universal Turing machine, the universal and diagonalization languages, reduction between languages and Rice's theorem, undecidable problems about languages.

Unit 6

Basic Introduction to Complexity

Introductory ideas on Time complexity of deterministic and nondeterministic Turing machines, P and NP, NP-completeness, Cook's Theorem, other NP-Complete problems.

Course Objective

To provide students with a strong foundation in formal languages and automata theory, and to develop their understanding of regular languages, context-free languages, Turing machines, and undecidability.

Course Outcome

Upon completion of this course, students will be able to: 1. Understand the concepts of formal languages and automata theory. 2. Apply regular expressions and finite automata to solve problems. 3. Analyze context-free grammars and pushdown automata. 4. Comprehend the working of Turing machines and their variants. 5. Recognize undecidable problems and their implications. 6. Use YACC as a parser-generating tool.

Practicals

  • YACC, the parser-generating tool

    Chapter 5 of Introduction to Automata Theory, Languages, and Computation by John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman.

Reference Books

  • Elements of the Theory of Computation, Harry R. Lewis and Christos H. Papadimitriou.

  • Automata and Computability, Dexter C. Kozen.

  • Introduction to the Theory of Computation, Michael Sipser.

  • Introduction to Languages and the Theory of Computation, John Martin.

  • Computers and Intractability: A Guide to the Theory of NP Completeness, M. R. Garey and D. S. Johnson.