Theory of Computation topics
In this article, we have list all topics in Theory of Computation including Advanced Research Topics like Super Recursive Algorithms. This list is useful for all students at any level (B. Tech, M. Tech, PhD) to get a good idea of how to get started with Theory of Computation.
Theory of Computation is mainly divided into 4 components:
- Type 3
- Type 2
- Type 1
- Type 0
We have listed the important topics in each component. Important topics in Theory of Computation are:
Practice questions (MCQ) on Theory of Computation
Introductory topics
- Introduction to Theory of Computation
- Chomsky Hierarchy
- Automata theory
- Computability theory
- Complexity theory
- Basic techniques for Proof
- Direct Proof
- Constructive Proof
- Nonconstructive Proof
- Proof by Contradiction
- Pigeon Hole Principle
- Proof by Induction
- Applications of Theory of Computation
Type 3
- Regular Languages
- Finite Automata
- Deterministic finite automata (DFA)
- Nondeterministic finite automata (NFA)
- Equivalence of DFAs and NFAs
- Regular operations
- Regular expressions
- Equivalence of regular expressions and regular languages
- Pumping Lemma for Regular Languages (with proof)
- Pumping Lemma in Theory of Computation
- Pumping Lemma Questions
- Higman's Theorem
- Dickson's Theorem
Type 2
- Context Free grammars
- Context Free Languages
- Context Free Grammar (CFG) for Chemistry
- Context free grammar (CFG) for Balanced Parentheses
- Applications of Context Free Grammar
- Regular Languages are Context Free Languages
- Chomsky normal form
- Pushdown Automata
- Pushdown Automata for 0^N 1^N
- Equivalence of Pushdown Automata and Context Free grammars
- Pumping lemma for Context Free languages
Type 1
- Context Sensitive Grammar (CSG)
- Context Sensitive Language (CSL)
- Grammar for a^N b^N c^N
- Linear Bounded Automaton
Type 0
- One Tape Turing machine
- Multi Tape Turing machines / K tape Turing Machine
- Non Deterministic Turing Machine
- Recursively Enumerable Languages
- Church Turing Thesis
- Limitations of Church Turing Thesis
- Halting Problem
Decidable and Undecidable Languages
- Decidability
- Undecidability
- Countable sets
- Rice's Theorem
- Enumerability
- Most languages are not enumerable
- Relationship between decidable and enumerable languages
- A language A such that both A and A' are not enumerable
Advance topics
- Halting Turing Machine
- Recursive Language
- Natural Languages
- Linear Context Free Rewriting Systems
- Definition of Algorithm in Theory of Computation
- Modern Computing Devices and Turing Machine
- Quantum Computers and Turing Machine
- Molecular Computer and Turing Machine
- Godel Incompleteness Theorem
- Super Recursive Algorithms
- Inductive Turing Machine
- Inductive Turing Machine + Structured Memory
- Inductive Turing Machine + Structured Rules (control device)
- Inductive Turing Machine + Structured Head (Operating Device)
- Extended Church Turing Thesis
With this article at OpenGenus, you must have a strong idea of the different topics in Theory of Computation you should have an idea of.