Grammars and Languages: Programming and Language basics, Regular
expressions, Regular grammars, Contextfree grammars, context-sensitive
grammars, unrestricted grammars, Chomsky hierarchy.
Automata: Finite automata, pushdown automata, Pumping Lemmas and
Closure properties, Turing machines and recursively enumerable
languages.
Computability: Computable functions, non-recursively enumerable
languages, Undecidability, Rice's theorem, Post's correspondence
problem, Undecidability of validity problem of First Order Logic.
Complexity: Asymptotic order symbol, Space and Time complexity,
Classes P and NP, NP-completeness, Cook-Levin tehorem, Other NP-complete problems.
- Teacher: radharam RADHA R