Computer Science Engineering > Theory of Computation
Theory of Computation
Learn the Concepts of Theory of Computation and test your knowledge
CHOOSE YOUR TOPIC
Introduction
In this topic, we learn about Complexity theory, Computability theory, Automata theory, Mathematical preliminaries, Proof techniques: Direct proofs, Constructive proofs, Nonconstructive proofs etc
Finite Automata and Regular Languages
In this topic, we learn about Deterministic finite automata, Regular operations, Nondeterministic finite automata, Equivalence of DFAs and NFAs, Closure under the regular operations, Regular expressions etc
Context-Free Languages
In this topic, we learn about Context-free grammar, Regular languages are context-free, Chomsky normal form, Pushdown automata, Equivalence of pushdown automata and context-free grammars etc
Turing Machines and the Church-Turing Thesis
In this topic, we learn about Definition of a Turing machine, Examples of Turing machines, Multi-tape Turing machines, The Church-Turing Thesis
5 Decidable and Undecidable Languages
In this topic, we learn about Decidability, Countable sets, Rice’s Theorem, Enumerability, The relationship between decidable and enumerable languages, A language A such that both A and A are not enumerable
Complexity Theory
In this topic, we learn about The running time of algorithms, The complexity class P, The complexity class NP, Non-deterministic algorithms, NP-complete languages