Please enable JavaScript.
Coggle requires JavaScript to display documents.
CS3452:THEORY OF COMPUTATION - Coggle Diagram
CS3452:THEORY OF COMPUTATION
UNIT 1: AUTOMATA AND REGULAR EXPRESSIONS
Need for automata theory
Introduction to formal proof
Finite Automata (FA)
Deterministic Finite Automata (DFA)
Non-deterministic Finite Automata (NFA)
Equivalence between NFA and DFA
Finite Automata with Epsilon transitions
Equivalence of NFA and DFA
Equivalence of NFAs with and without ε-moves
Conversion of NFA into DFA
Minimization of DFAs.
UNIT II: REGULAR EXPRESSIONS AND LANGUAGES
Regular expression
Regular Languages
Equivalence of Finite Automata and regular expressions
Proving languages to be not regular (Pumping Lemma)
Closure properties of regular languages.
UNIT III:CONTEXT FREE GRAMMAR AND PUSH DOWN AUTOMATA
Types of Grammar
Chomsky‘s hierarchy of languages
Context-Free Grammar (CFG) and Languages
Derivations and Parse trees
Ambiguity in grammars and languages
Push Down Automata (PDA)
Definition
Moves
Instantaneous descriptions
Languages of Push Down Automata
Equivalence of pushdown automata and CFG
CFG to PDA
PDA to CFG
Deterministic Pushdown Automata
UNIT IV: NORMAL FORMS AND TURING MACHINES
Normal forms for CFG
Simplification of CFG
Chomsky Normal Form (CNF)
Greibach Normal Form (GNF)
Pumping lemma for CFL
Closure properties of Context Free Languages
Turing Machine
Basic model
Definition and representation
Instantaneous Description
Language acceptance by TM
TM as Computer of Integer functions
Programming techniques for Turing machines (subroutines).
UNIT V: UNDECIDABILITY
Unsolvable Problems and Computable Functions
PCP
MPCP
Recursive and recursively enumerable languages
Universal Turing machine
Tractable and Intractable problems
P and NP completeness
Kruskal’s algorithm
Travelling salesman problem
3-CNF SAT problems