Theory of Computation
4IT4-06 · Semester 4
0/60 topics
Course objective
Course scope
Course outcome
Basic machine concepts
Finite State Machine (FSM)
Transition graphs
Transition matrices
Deterministic Finite Automata (DFA)
Non-Deterministic Finite Automata (NDFA)
Equivalence of DFA and NDFA
Decision properties of finite automata
Minimization of finite automata
Mealy machines
Moore machines
Alphabets and words
Regular sets
Conversion between FA and regular expressions
Designing regular expressions
Closure properties of regular sets
Pumping Lemma for regular sets
Myhill-Nerode theorem
Applications of Pumping Lemma
Context Free Grammars (CFG)
Derivations and CFLs
Derivation trees
Leftmost derivations
Rightmost derivations
Sentential forms
Parsing and ambiguity in CFG
Simplification of CFG
Chomsky Normal Form (CNF)
Greibach Normal Form (GNF)
Membership problem in CFG
Non-Deterministic Pushdown Automata (NPDA)
Equivalence of PDA and CFL
Constructing CFG for PDA
Deterministic Pushdown Automata (DPDA)
Deterministic CFLs
Pumping Lemma for CFLs
Closure properties of CFLs
Decision properties of CFLs
Definition of Turing Machine (TM)
TM as language acceptors
TM as transducers
Computable languages and functions
Universal Turing Machine
Multiple track Turing Machines
Recursive languages
Recursively enumerable languages
Properties of recursive and recursively enumerable languages
Context Sensitive Grammars (CSG)
The Chomsky Hierarchy
Class P problems
Class NP problems
NP-Complete problems
NP-Hard problems
Undecidability
Vertex Cover problem undecidability
Hamiltonian Path problem
Traveling Salesman Problem