Introduction
- Basic mathematical notation and techniques
- Finite state systems
- Basic definitions
Finite Automata
- Definition of finite automaton
- Deterministic Finite Automaton (DFA)
- Non-Deterministic Finite Automaton (NDFA)
- Finite automaton with ε-moves
Regular Languages
- Definition of regular languages
- Regular expressions
- Equivalence of NFA and DFA
- Equivalence of NDFA with and without ε-moves
- Equivalence of finite automaton and regular expressions
DFA Minimization
- Minimization of DFA
Pumping Lemma for Regular Sets
- Pumping lemma
- Problems based on pumping lemma

M2: Grammars

MODULE 2 - STRUCTURED SYLLABUS

Introduction to Grammars
- Types of grammars
Context-Free Grammars and Languages
- Definition of context-free grammars (CFG)
- Derivations and languages
- Ambiguity in CFGs
- Relationship between derivation and derivation trees
Simplification of Context-Free Grammars
- Elimination of useless symbols
- Elimination of unit productions
- Elimination of null productions
Normal Forms
- Greibach Normal Form (GNF)
- Chomsky Normal Form (CNF)
- Problems related to CNF and GNF
Chomsky Hierarchy
- Chomsky hierarchy of languages

M3: Pushdown Automata

MODULE 3 - STRUCTURED SYLLABUS

Pushdown Automata (PDA)
- Definitions
- Moves
- Deterministic Pushdown Automata
- Non-Deterministic Pushdown Automata
- Instantaneous descriptions
Relationship with Context-Free Languages
- Equivalence of pushdown automata and context-free languages (CFL)
- Conversion of CFG to n-PDA: Construction Principles
Pumping Lemma for Context-Free Languages
- Pumping lemma for CFL
- Problems based on pumping lemma
Linear Bounded Automata (LBA)
- Introduction to LBA

M4: Turing Machines

MODULE 4 - STRUCTURED SYLLABUS

Turing Machine Fundamentals
- Turing machine model
- Language acceptability of Turing machines
- Design of Turing machines
Variations and Extensions
- Variations of Turing machines
- Universal Turing machine
- Church Turing Thesis
Context-Sensitive Languages and LBA
- Context-sensitive languages
- Linear bounded automata (LBA)
Decidability and Undecidability
- The Halting Problem
- Decidability
- Post’s Correspondence Problem (PCP)
- Undecidability of PCP
- Modified PCP

M5: Introduction to compiler

MODULE 5 - STRUCTURED SYLLABUS

Overview of Compilers
- Language Processing System
  - Preprocessor
  - Compiler
  - Assembler
  - Interpreter
  - Loader / Link Editor
- Structure of Compiler
- Analysis of the source program
- Phases and passes in compilers
  - Lexical Analysis
  - Syntax Analysis
  - Semantic Analysis
  - Intermediate Code Generation
  - Code Optimization
  - Code Generation
  - Code Linking & Assembly
  - Error Handling (across all phases)
- Tasks of a compiler
- Cousins of the compiler
- Grouping of phases
- Compiler construction tools
  - Lexical Analyzer Generators
  - Parser Generators
  - Syntax-Directed Translation Engines
  - Intermediate Code Generators
  - Code Optimizers
  - Code Generators
  - Symbol Table Management Tools
  - Error Handling Tools
Lexical Analysis
- Role of the lexical analyzer
- Token, Lexeme, Pattern
- Input buffering
- Specification of tokens
- Recognition of tokens
- Language for specifying lexical analyzer
Finite Automata and Regular Expressions in Lexical Analysis
- Review of regular expressions
- Finite state machines
- Finite automata(NFA/DFA)-based pattern matching
- Specification and recognition of tokens