Principles in Theory of Computation

Automata Theory, Computability Theory, Computational Complexity Theory

Theoretical Computer Science is a field where all the real world computational problems come under it. Theoretical Computer Science is also called as Theory of Computation. Theory of computation speaks about “How efficiently the real world problems can be solved by using an algorithm in a model of computation. The model of computation denotes any mathematical model which is embedded on any electronic hardware through the software. Theory of computation is divided in to three sub fields. They are automata theory, computability theory and computational complexity theory. Automata theory denotes the study of problem solving in abstract machines. Here the abstract machines are called as mathematical model rather than it’s not a hardware. Automata theory has various types of automata such as Deterministic Finite Automata, Non-deterministic finite automata, Pushdown Automata and Linear Bounded Automata. These entire automata can be performed in a single hardware called “Turing Machine”. Till now nobody proved that, a problem that cannot be solved by a Turing Machine can be solved by a real world computer. The Computability speaks about “what are all the problems can be solved by a computer and cannot be solved by a computer”. This is called as decidability and un-decidability. The computational complexity theory speaks about “how much time and space an algorithm takes to solve a problem. This is called as Time and Space Complexity. These are the topics are discussed in this course “Principles in Theory of Computation”.

What you’ll learn

• Understanding the operation of Finite Automata and Hierarchy of Grammars in solving the problems.
• Examining the Grammars and Languages using Pumping Lemma.
• Design Pushdown Automata for Computational Logic.
• Design Turing Machine for general purpose computer operations.
• Evaluate decidability, undecidabilty and Polynomial class of Problems.

Course Content

• Introduction –> 1 lecture • 7min.
• Minimization of Finite Automata –> 1 lecture • 20min.
• Regular Expression to Finite Automata –> 1 lecture • 12min.
• Regular Expression to Finite Automata Continuation –> 1 lecture • 7min.
• Regular Expression to Finite Automata Continuation –> 1 lecture • 13min.
• Finite Automata to Regular Expression –> 1 lecture • 7min.
• Finite Automata to Regular Expression Continuation –> 1 lecture • 9min.
• Finite Automata to Regular Expression Continuation –> 1 lecture • 12min.
• Finite Automata to Regular Expression using Arden’s Theorem –> 1 lecture • 6min.
• Pumping Lemma for Regular Languages –> 1 lecture • 8min.
• Pumping Lemma for Regular Languages Continuation –> 1 lecture • 8min.
• Pumping Lemma for Regular Languages Continuation –> 1 lecture • 10min.
• Leftmost Derivation & Rightmost Derivation –> 1 lecture • 11min.
• Ambiguous Grammar –> 1 lecture • 4min.
• Simplification of CFG –> 1 lecture • 5min.
• Simplification of CFG continuation –> 1 lecture • 5min.
• Simplification of CFG continuation –> 1 lecture • 5min.
• Chomsky Normal Form (CNF) –> 1 lecture • 10min.
• Greibach Normal Form (GNF) –> 1 lecture • 13min.
• Greibach Normal Form (GNF) Continuation –> 1 lecture • 14min.
• Introduction to Pushdown Automata (PDA) –> 1 lecture • 8min.
• Introduction to Pushdown Automata (PDA) Continuation –> 1 lecture • 8min.
• Equivalence of PDA & CFG –> 1 lecture • 4min.
• Equivalence of PDA & CFG Continuation –> 1 lecture • 12min.
• Equivalence of PDA & CFG Continuation –> 1 lecture • 6min.
• Push Down Automata Solved Examples –> 1 lecture • 9min.
• Push Down Automata Solved Examples Continuation –> 1 lecture • 9min.
• Turing Machine Introduction –> 1 lecture • 10min.
• Turing Machine Introduction Continuation –> 1 lecture • 5min.
• Turing Machine Introduction Continuation –> 1 lecture • 5min.
• Instantaneous Description of Turing Machine –> 1 lecture • 6min.
• Turing Machine Examples –> 1 lecture • 8min.
• Turing Machine Examples Continuation –> 1 lecture • 6min.
• Turing Machine Examples Continuation –> 1 lecture • 7min.
• Turing Machine Examples Continuation –> 1 lecture • 10min.
• Palindrome using Turing Machine –> 1 lecture • 16min.
• Addition by Turing Machine –> 1 lecture • 6min.
• Subtraction By Turing Machine –> 1 lecture • 10min.
• 2’s Complement by Turing Machine –> 1 lecture • 6min.
• Multiplication by Turing Machine –> 1 lecture • 3min.
• Multiplication by Turing Machine Continuation –> 1 lecture • 11min.
• Multiplication by Turing Machine Continuation –> 1 lecture • 13min.
• Division by Turing Machine –> 1 lecture • 7min.
• Division by Turing Machine Continuation –> 1 lecture • 12min.
• Division by Turing Machine Continuation –> 1 lecture • 14min.

Requirements

Theoretical Computer Science is a field where all the real world computational problems come under it. Theoretical Computer Science is also called as Theory of Computation. Theory of computation speaks about “How efficiently the real world problems can be solved by using an algorithm in a model of computation. The model of computation denotes any mathematical model which is embedded on any electronic hardware through the software. Theory of computation is divided in to three sub fields. They are automata theory, computability theory and computational complexity theory. Automata theory denotes the study of problem solving in abstract machines. Here the abstract machines are called as mathematical model rather than it’s not a hardware. Automata theory has various types of automata such as Deterministic Finite Automata, Non-deterministic finite automata, Pushdown Automata and Linear Bounded Automata. These entire automata can be performed in a single hardware called “Turing Machine”. Till now nobody proved that, a problem that cannot be solved by a Turing Machine can be solved by a real world computer. The Computability speaks about “what are all the problems can be solved by a computer and cannot be solved by a computer”. This is called as decidability and un-decidability. The computational complexity theory speaks about “how much time and space an algorithm takes to solve a problem. This is called as Time and Space Complexity. These are the topics are discussed in this course “Principles in Theory of Computation”.