AI-Powered Learning Platform

Subject Syllabus

CB-301 - Formal Language & Automata Theory

CSBS · Semester 3

Course Modules

Learn topic-wise with Hyper AI and revise using mapped PYQs.

Alphabet, languages and grammars Productions and derivation Chomsky hierarchy of languages

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

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

Context-sensitive grammars (CSG) and languages Linear bounded automata and equivalence with CSG 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

Church-Turing thesis Universal Turing machine The universal and diagonalization languages Reduction between languages and Rice's theorem Undecidable problems about languages Introductory ideas on Time complexity of deterministic and nondeterministic Turing machines P and NP NP-completeness Cook's Theorem Other NP-Complete problems