Theory of Computation Important Questions - Anna University Syllabus

Unit-I

• Inductive proofs – problems
• Finite Automata(FA)
• Non Deterministic Finite Automata(NFA) - Theorem and problem
• Deterministic Finite Automata (DFA) - Theorem and problem
• Finite Automata(FA with e Moves) - Theorem and problem

Unit-II

• Finite Automata(FA) to Regular Expression(RE) - Theorem and problem
• Regular Expression(RE) to Finite Automata(FA) - Theorem and problem
• Minimization of Automata - Problem
• Pumbimg Lema - Problem

Unit - III

• Parse Tree - (Ambiguity)
• PushDown Automata(PDA) to Context-Free Grammar(CFG) - Problem

Unit - IV

• Pumping lema for Context-Free Languages(CFL)
• Closure properties of Context-Free Languages(CFL)
• Turing Machine

Unit - V

• A language in not recursive enumerable
• Post’s Correspondence Problem
• Undecidable problems about Turing Machine
• The classes P and NP.

Get Related News: Anna University, Education, Exam Questions