Formal Language, Non-Computational Problems, Diagonal Argument,
Russels’s Paradox.
Theory of Automata: Deterministic Finite Automaton (DFA), Non-
Deterministic Finite Automaton (NDFA), Equivalence of DFA and
NDFA, Mealy and Moore Models, Minimization of Finite Automata.
Regular Sets and Regular Grammars: Regular Languages, Regular
Grammars, Regular Expressions, Properties of Regular Language,
Pumping Lemma, Non-Regular Languages, Lexical Analysis.
Context Free Language: Properties of Context Free Language,
Chomsky Classification of Languages, Context Free Grammar,
Simplification of Context Free Grammar, Chomsky Normal Form,
Greibach Normal Form.
Push Down Automata: Ambiguity, Parse Tree Representation of
Derivation Trees, Equivalence of PDA’s and Pushdown Automaton
(PDA), Non-Deterministic Pushdown Automaton (NPDA).
Turing Machines (TM): Standard Turing Machine and its Variations;
Universal Turing Machines, Models of Computation and Church-Turing
Thesis.
Recursive and Recursively-Enumerable Languages; Context-
Sensitive Languages, Unrestricted Grammars, Chomsky Hierarchy of
Languages, Construction of TM for Simple Problems.
Unsolvable Problems and Computational Complexity: Unsolvable
Problem, Halting Problem, Post Correspondence Problem, Unsolvable
Problems for Context-Free Languages, Measuring and Classifying
Complexity, Tractable and Intractable Problems.
