Principles In Theory Of Computation

Automata Theory, Computability Theory, Computational Complexity Theory

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

Requirements

Basic Mathematical Knowledge

Description

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”.

Overview

Section 1: Introduction

Lecture 1 Introduction

Section 2: Minimization of Finite Automata

Lecture 2 Minimization of Finite Automata

Section 3: Regular Expression to Finite Automata

Lecture 3 Regular Expression to Finite Automata

Section 4: Regular Expression to Finite Automata Continuation

Lecture 4 Regular Expression to Finite Automata

Section 5: Regular Expression to Finite Automata Continuation

Lecture 5 Regular Expression to Finite Automata

Section 6: Finite Automata to Regular Expression

Lecture 6 Finite Automata to Regular Expression

Section 7: Finite Automata to Regular Expression Continuation

Lecture 7 Finite Automata to Regular Expression

Section 8: Finite Automata to Regular Expression Continuation

Lecture 8 Finite Automata to Regular Expression

Section 9: Finite Automata to Regular Expression using Arden's Theorem

Lecture 9 Finite Automata to Regular Expression using Arden's Theorem

Section 10: Pumping Lemma for Regular Languages

Lecture 10 Pumping Lemma for Regular Languages

Section 11: Pumping Lemma for Regular Languages Continuation

Lecture 11 Pumping Lemma for Regular Languages

Section 12: Pumping Lemma for Regular Languages Continuation

Lecture 12 Pumping Lemma for Regular Languages

Section 13: Leftmost Derivation & Rightmost Derivation

Lecture 13 Leftmost Derivation & Rightmost Derivation

Section 14: Ambiguous Grammar

Lecture 14 Ambiguous Grammar

Section 15: Simplification of CFG

Lecture 15 Simplification of CFG

Section 16: Simplification of CFG continuation

Lecture 16 Simplification of CFG

Section 17: Simplification of CFG continuation

Lecture 17 Simplification of CFG

Section 18: Chomsky Normal Form (CNF)

Lecture 18 Chomsky Normal Form (CNF)

Section 19: Greibach Normal Form (GNF)

Lecture 19 Greibach Normal Form (GNF)

Section 20: Greibach Normal Form (GNF) Continuation

Lecture 20 Greibach Normal Form (GNF)

Section 21: Introduction to Pushdown Automata (PDA)

Lecture 21 Introduction to Pushdown Automata (PDA)

Section 22: Introduction to Pushdown Automata (PDA) Continuation

Lecture 22 Introduction to Pushdown Automata (PDA)

Section 23: Equivalence of PDA & CFG

Lecture 23 Convert PDA to CFG

Section 24: Equivalence of PDA & CFG Continuation

Lecture 24 Convert PDA to CFG

Section 25: Equivalence of PDA & CFG Continuation

Lecture 25 CFG to PDA

Section 26: Push Down Automata Solved Examples

Lecture 26 Push Down Automata Solved Examples

Section 27: Push Down Automata Solved Examples Continuation

Lecture 27 Push Down Automata Solved Examples

Section 28: Turing Machine Introduction

Lecture 28 Turing Machine Introduction

Section 29: Turing Machine Introduction Continuation

Lecture 29 Turing Machine Introduction

Section 30: Turing Machine Introduction Continuation

Lecture 30 Turing Machine Introduction

Section 31: Instantaneous Description of Turing Machine

Lecture 31 Instantaneous Description of Turing Machine

Section 32: Turing Machine Examples

Lecture 32 Turing Machine Examples

Section 33: Turing Machine Examples Continuation

Lecture 33 Turing Machine Examples

Section 34: Turing Machine Examples Continuation

Lecture 34 Turing Machine Examples

Section 35: Turing Machine Examples Continuation

Lecture 35 Turing Machine Examples

Section 36: Palindrome using Turing Machine

Lecture 36 Palindrome using Turing Machine

Section 37: Addition by Turing Machine

Lecture 37 Addition by Turing Machine

Section 38: Subtraction By Turing Machine

Lecture 38 Subtraction By Turing Machine

Section 39: 2's Complement by Turing Machine

Lecture 39 2's Complement by Turing Machine

Section 40: Multiplication by Turing Machine

Lecture 40 Multiplication by Turing Machine

Section 41: Multiplication by Turing Machine Continuation

Lecture 41 Multiplication by Turing Machine

Section 42: Multiplication by Turing Machine Continuation

Lecture 42 Multiplication by Turing Machine

Section 43: Division by Turing Machine

Lecture 43 Division by Turing Machine

Section 44: Division by Turing Machine Continuation

Lecture 44 Division by Turing Machine

Section 45: Division by Turing Machine Continuation

Lecture 45 Division by Turing Machine

Learner who is interested in theoretical computer Science,Learner who is interested in solving real world problems,Learner who is interested in developing a programming language