05-01-2017, 03:50 PM
QUESTION PAPERS:-
SYLLABUS:-
UNIT- I
Overview: Alphabets, Strings & Languages, Chomsky Classification of Languages, Finite Automata, Deterministic finite Automata (DFA) & Nondeterministic finite Automata (NDFA), Equivalence of NDFA and DFA, Minimization of Finite Automata, Moore and Mealy machine and their equivalence, Regular expression and Kleen’s Theorem(with proof), Closure properties of Regular Languages, Pumping Lemma for regular Languages(with proof).
UNIT- II
Context free grammar, Derivation trees, Ambiguity in grammar and its removal, Simplification of Context Free grammar, Normal forms for CFGs: Chomsky Normal Form & Greibach Normal Form, Pumping Lemma for Context Free languages, Closure properties of CFL(proof required), Push Down Automata (PDA), Deterministic PDA, Non Deterministic PDA ,Equivalence of PDA and CFG, Overview of LEX and YACC.
UNIT- III
Turing machines, Turing Church’s Thesis, Variants and equivalence of Turing Machine, Recursive and recursively enumerable languages, Halting problem, Undecidability, Examples of Undecidable problem.
UNIT- IV
Introduction to Complexity classes, Computability and Intractability, time complexity, P, NP, Co-NP, Proof of Cook’s Theorem, Space Complexity, SPACE, PSPACE, Proof of Savitch’s Theorem, L ,NL ,Co-NL complexity classes.
UNIT- I
Overview: Alphabets, Strings & Languages, Chomsky Classification of Languages, Finite Automata, Deterministic finite Automata (DFA) & Nondeterministic finite Automata (NDFA), Equivalence of NDFA and DFA, Minimization of Finite Automata, Moore and Mealy machine and their equivalence, Regular expression and Kleen’s Theorem(with proof), Closure properties of Regular Languages, Pumping Lemma for regular Languages(with proof).
UNIT- II
Context free grammar, Derivation trees, Ambiguity in grammar and its removal, Simplification of Context Free grammar, Normal forms for CFGs: Chomsky Normal Form & Greibach Normal Form, Pumping Lemma for Context Free languages, Closure properties of CFL(proof required), Push Down Automata (PDA), Deterministic PDA, Non Deterministic PDA ,Equivalence of PDA and CFG, Overview of LEX and YACC.
UNIT- III
Turing machines, Turing Church’s Thesis, Variants and equivalence of Turing Machine, Recursive and recursively enumerable languages, Halting problem, Undecidability, Examples of Undecidable problem.
UNIT- IV
Introduction to Complexity classes, Computability and Intractability, time complexity, P, NP, Co-NP, Proof of Cook’s Theorem, Space Complexity, SPACE, PSPACE, Proof of Savitch’s Theorem, L ,NL ,Co-NL complexity classes.