Theory of Computation:

Formal Language, Non-Computational Problems, Diagonal Argument, Russels’s Paradox. Regular Language Models: Deterministic Finite Automaton (DFA), Non-Deterministic Finite Automaton (NDFA), Equivalence of DFA and NDFA, Regular Languages, Regular Grammars, Regular Expressions, Properties of Regular Language, Pumping Lemma, Non- Regular Languages, Lexical Analysis. Context Free Language: Pushdown Automaton (PDA), Non-Deterministic Pushdown Automaton (NPDA), Context Free Grammar, Chomsky Normal Form, Greibach Normal Form, Ambiguity, Parse Tree Representation of Derivation Trees, Equivalence of PDA’s and Context Free Grammars; Properties of Context Free Language. 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. Syntax Analysis: Associativity, Precedence, Grammar Transformations, Top Down Parsing, Recursive Descent Predictive Parsing, LL(1) Parsing, Bottom up Parsing, LR Parser, LALR(1) Parser. Semantic Analysis: Attribute Grammar, Syntax Directed Definitions, Inherited and Synthesized Attributes; Dependency Graph, Evaluation Order, S-attributed and L-attributed Definitions; Type-Checking. 7 Run Time System: Storage Organization, Activation Tree, Activation Record, Stack Allocation of Activation Records, Parameter Passing Mechanisms, Symbol Table. Intermediate Code Generation: Intermediate Representations, Translation of Declarations, Assignments, Control Flow, Boolean Expressions and Procedure Calls. Code Generation and Code Optimization: Control-flow, Data-flow Analysis, Local Optimization, Global Optimization, Loop Optimization, Peep-Hole Optimization, Instruction Schedulin