What You Will Learn
Key objectives of CS501 Theory of Computation.
- To understand computability, decidability, and complexity through problem solving.
- To analyse and design abstract models of computation and formal languages.
- To understand and conduct mathematical proofs for computation and algorithms.
CS501 Unit-Wise Notes
Select a unit to read the complete notes.
I
Introduction of Automata Theory
Automata machines, finite automata, Moore and Mealy machines
- Examples of Automata Machines
- Finite Automata as a Language Acceptor
- Finite Automata as a Translator
- Moore Machines
- Mealy Machines
- Composite Machine
- Conversion from Mealy to Moore
- Conversion from Moore to Mealy
II
Types of Finite Automata
DFA, NDFA, regular expressions, Arden's theorem
- Non Deterministic Finite Automata (NDFA)
- Deterministic Finite Automata (DFA)
- Conversion of NDFA to DFA
- Minimization of Automata Machines
- Regular Expression
- Arden's Theorem
- Union, Intersection
- Concatenation and Closure
- Two Way DFA
III
Grammars
CFG, CSG, regular grammar and Chomsky hierarchy
- Types of Grammar
- Context Sensitive Grammar
- Context Free Grammar
- Regular Grammar
- Derivation Trees
- Ambiguity in Grammar
- Simplification of Context Free Grammar
- Conversion of Grammar to Automata
- Conversion of Automata to Grammar
- Chomsky Hierarchy of Grammar
- Elimination of Null Productions
- Elimination of Unit Productions
- Chomsky Normal Form
- Greibach Normal Form
IV
Push Down Automata
PDA, DPDA, NPDA, CFG-PDA equivalence
- Example of PDA
- Deterministic PDA
- Non-Deterministic PDA
- Conversion of PDA into CFG
- Conversion of CFG into PDA
- CFG Equivalent to PDA
- Petri Net Model
V
Turing Machine
TM, decidability, undecidability and computational problems
- Techniques for Construction of Turing Machine
- Universal Turing Machine
- Multitape Turing Machine
- Multihead Turing Machine
- Multidimensional Turing Machine
- N-P Complete Problems
- Decidability
- Recursively Enumerable Languages
- Decidable Languages
- Undecidable Languages
- Halting Problem of Turing Machine
- Post Correspondence Problem
Important Questions
Prepare these high-priority CS501 topics.
Explain Moore and Mealy machines. Compare Moore machine and Mealy machine.
Explain the conversion of Mealy machine to Moore machine with suitable example.
Explain NDFA and conversion of NDFA into DFA with suitable example.
Explain minimization of finite automata with suitable example.
State and explain Arden's theorem with suitable example.
Explain regular expressions and the operations on regular languages.
Explain different types of grammars and Chomsky hierarchy.
Explain ambiguity in grammar with derivation tree.
Explain Chomsky Normal Form and Greibach Normal Form.
Explain simplification of Context Free Grammar.
Explain Push Down Automata with suitable example.
Explain conversion of CFG into PDA and PDA into CFG.
Explain Turing Machine and techniques for its construction.
Explain Universal Turing Machine and Multitape Turing Machine.
Explain decidable and undecidable languages.
Explain Halting Problem of Turing Machine.
Explain Recursively Enumerable Languages.
Explain Post Correspondence Problem.
How to Prepare CS501
Focus on concepts, diagrams and conversions.
Learn Definitions
Prepare DFA, NDFA, CFG, PDA, Turing Machine, decidability and related definitions clearly.
Practice Conversions
Practice Mealy-Moore, NDFA-DFA, CFG-PDA and other important conversions.
Draw Diagrams
Use proper transition diagrams, derivation trees, PDA diagrams and Turing Machine representations.
CS501 FAQs
Common questions about Theory of Computation.
Ready for CS501?
Start with Unit 1 and prepare Theory of Computation topic by topic.