Computer Science & IT – B.Tech, BCA, BBA, MCA, M.Tech Best Online Coaching Institute

Theory of Computation

Theory of Computation
Section A
Finite Automata and Regular Expression
Finite State system
Basic Definition Non-Deterministic Finite Automata (NDFA),Deterministic Finite Automata (DFA)
Equivalence of DFA and NDFA
Conversion of NFA to DFA Finite Automata
Regular expressions
Equivalence of Finite Automata and Regular expressions ,Regular expression conversion and vice versa
Introduction to Machines
Concept of basic machines
Properties and limitation of FSM
Moore and mealy machines
Equivalence of Moore and mealy machines
State and prove Arden’s Method
Section B
Properties of regular sets
The pumping Lemma for regular sets
Application of the pumping lemma
Closure   Properties of regular sets
Minimization algorithm
Grammars:definition
Context free and context sensitive grammar
Ambiguity regular grammar
Removal of useless symbols
Unit Production and null Production
Chomsky Normal Form
Griebach Normal Form
Section C
Push down Automata:Introduction to push down automata
Application of push down automata
Turing Machines: Deterministic and Non-Deterministic Turing Machines
Design of Turing Machines
Halting problem of Turing Machines
PCP Problem
Section D
Chomsky Hierarchies
Chomsky Hierarchies of grammars
Unrestricted Grammar
Context Sensitive Language