Basics: Sets, Set Operations, Properties of Sets
Automata: Deterministic Finite Automaton (DFA), Non – deterministic Finite Automaton (NFA), Regular languages and regular sets, Equivalence of DFA and NFA. Minimizing the number of states of a DFA. Non-regular languages and Pumping lemma.
PDA: Pushdown Automaton (PDA), Deterministic Pushdown Automaton (DPDA), Non – equivalence of PDA and DPDA.
Chomsky Hierarchy of languages: Type-0, Type-1, Type-2 & Type-3 languages, Recursive and recursively-enumerable languages.
Context free Grammars : Greibach Normal Form (GNF) and Chomsky Normal Form (CNF), Ambiguity, Parse Tree Representation of Derivations. Equivalence of PDA and CFG. Parsing techniques for parsing of general CFG – Early’s, Cook-Kassami-Younger (CKY) and Tomita’s parsing. RTNs, ATNs, Parsing of Ambiguous CFGs.
Linear Bounded Automata (LBA) : Power of LBA Closure properties.
Turing Machine (TM) : One tape, multi-tape, time and space complexity in terms of TM. Construction of TM, Computational complexity, Non-computability and Examples of non – computable problems.