CSE501 / TOC
Syllabus
Resources
MI: Finite Automata and Regular Languages
Introduction
Basic mathematical notation and techniques
Finite state systems and basic definitions
Finite automata models
Deterministic finite automaton (DFA)
Nondeterministic finite automaton (NDFA/NFA)
Finite automaton with ε\varepsilonε-moves
Regular languages and expressions
Regular languages
Regular expressions
Equivalence of NFA and DFA
Equivalence of NFA with and without ε\varepsilonε-moves
Equivalence of finite automata and regular expressions
DFA minimization
Minimization techniques for DFA
Pumping lemma for regular sets
Statement of pumping lemma
Problems based on pumping lemma
MII: Grammars
Introduction to grammars
Basic concepts of grammars
Types of grammars
Context-free grammars (CFG) and languages
Definitions of CFG and CFL
Derivations and generated languages
Ambiguity in grammars
Relationship between derivations and derivation trees
Simplification of CFG
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
MIII: Pushdown Automata and Linear Bounded Automata
Pushdown automata (PDA)
Definitions and basic components
Moves and instantaneous descriptions
Deterministic pushdown automata (DPDA)
PDA and CFL
Equivalence of PDA and context-free languages
Pumping lemma for CFL
Statement of pumping lemma for CFL
Problems based on pumping lemma
Linear bounded automata (LBA)
Definition and basic idea
MIV: Turing Machines
Turing machine model
Basic model and components
Language acceptability of Turing machines
Design of Turing machines
Construction for simple languages and functions
Variants of Turing machines
Variations of TM
Universal Turing machine
Church’s machine (Church–Turing thesis context)
Undecidability examples
Turing machine halting problem
Post correspondence problem (PCP)
Modified PCP
MV: Unsolvable Problems and Computable Functions
Computable functions
Primitive recursive functions
Recursive and recursively enumerable languages
Unsolvable problems
Examples of unsolvable problems
Tractability and intractability
Tractable vs. intractable problems
Class P and class NP problems
NP-completeness
Satisfiability problem (SAT)
Notes
Question Directory
Previous Year Questions
Mid-Sem-PYQ
End-Sem-PYQ
External Sources
Last updated