NOTE:

Course Objectives: • To introduce the mathematical foundations of computation • To develop mathematical proofs for computation and algorithms. • To prepare students in automation theory, formal languages, algorithms & logic

Introduction to TOC and Languages:

Lec-1

Sets and Relations:

Well-academy-lecture

Automata:

Lec-3

Grammar:

Lec-5

Definite Finite Automata(DFA) :

Lec-6

or

Lec-10

(watch the next few lectures in playlist for examples)

NFA:

Lec-13

Difference btw NFA and DFA:

Lec-14

Conversion from NFA to DFA:

Lec-16

Finite Automata with Epsilon transitions:

Lec-18

Limitations of DFA and Applications of DFA:

Lec-19

Moore Machine:

Lec-20

Mealy Machine:

Lec-21

Moore Machine to Mealy machine:

Lec-23

Mealy Machine to Moore machine:

Lec-24

Regular Expressions:

Lec-27

Important questions of Regular Expressions:

Lec-30

Pumping lemma:

Lec-31

Closure Properties of Regular Languages:

Lec-32

Closure Properties of Other Languages:

Lec-37

Context-Free Grammar and Context-Free Languages:

Lec-46

Conversion of CFL to CFG:

Lec-48

Left Most & Right Most Derivation in CFG:

Lec-49

Push Down Automata(PDA):

Lec-50

Construction of pushdown automata:

Lec-51

Turing Machine:

Lec-56

Types of Turing Machines:

# TOC Lec 50 - Variants of Turing machine by Deeba Kannan

Multi tape turning Machine:

TOC: Multitape Turing Machine by neso academy

Designing of turning Machines:

Lec-58

and

Lec-59

Linear Bounded Automata:

Lec-57

Undecidabilty:

Recursive vs Recursive Enumerable Languages:

Lec-60

Decidability and Undecidability:

Lec-108

The Halting Problem:

Lec-110

Undecidability of the Halting Problem:

Lec-111

The Post Correspondence Problem:

Lec-112

Undecidability of the Post Correspondence Problem:

Lec-113

Chomsky hierarchy of languages:

Lec-38

or

# Chomsky classification of grammar | TOC by knowledge gate