0(0)

Theory of Computation part 1

  • Course level: Beginner

Description

Theory of Computation part 1

This is an introductory course on the theory of computation intended for undergraduate students in computer science. In this course, we will introduce various models of computation and study their power and limitations. We will also explore the properties of corresponding language classes defined by these models and the relations between them. It is designed based on the syllabus given by the GATE Computer Science exam.

The Course contains a formal connection between algorithmic problem solving and the theory of languages, automata. It also develops them into a mathematical (and less magical) view towards the algorithmic design and in general computation itself. The course should, in addition, clarify the practical view towards the applications of these ideas in the engineering part of CS.

Who this course is for:

  1. Anyone who is interested in learning the theory of computation and its concepts.

 

 

 

What Will I Learn?

  • One can master Finite Automata of Theory of Computation
  • In-depth understanding of the basics of the Theory of Computation concepts
  • Understanding the need to study the theory of computation
  • Understanding the advanced concepts of the theory of computation like Push Down Automata

Topics for this course

35 Lessons

Theory of Computation part 1

Introduction to Theory of Computation, Need of Theory of Computation, Target Audience of TOC7:25
Why study theory of Computation?, Theory of Computation, TOC7:48
Content & Course flow in Theory of Computation Lecture Series, Chomsky’s Hierachy, TOC12:09
Regular language in Theory of Computation, Definition and Meaning of Regular Language, TOC10:18
Operations on Regular language in Theory of Computation, (Union, Concatenation & Star Operation)8:16
Examples of regular language in Theory of computation, Rules of Regular Language, TOC17:29
Examples of Regular Language in Theory of Computation, (Rules of Regular Language), TOC15:07
Finite Automata definition, Important Terminologies of Finite Automata, Theory of Computation, TOC11:11
Finite Automata Examples in Theory of Computations, Examples of DFA & NFA, DFA, NFA14:52
Non Deterministic Finite Automata (NFA) – TOC, Examples of Non-Deterministic Finite Automata (NFA)14:38
DFA Examples 1 – Theory of Computation, Dead State in Finite Automata, Deterministic Finite Automata18:31
DFA Examples 2- Theory of Computation, Dead State in Finite Automata, Deterministic Finite Automata16:50
DFA Examples 3 – Theory of Computation, Dead State in Finite Automata, Language accepted by DFA7:37
DFA Examples 4, Dead State in Finite Automata, Atleast constraint in DFA, Atmost Constraints in DFA14:57
Non Deterministic Finite Automata Theory & Example-1, Multiple Transition Path in NFA, TOC00:00:00
NFA Examples 2 – Theory of Computation, Validation check of NFA, NFA Example with substring, TOC00:00:00
NFA Example 3 – Theory of Computation, Validation check of NFA, Accepting State in NFA, TOC00:00:00
NFA Examples 4 – Theory of computation, NFA accepting words, NFA non-accepting words, TOC00:00:00
NFA to DFA Conversion – Theory of Computation, Algorithm to convert NFA to DFA, Equivalency NFA=DFA00:00:00
NFA to DFA Conversion Examples – Theory of Computation, Subset construction method, TOC00:00:00
NFA to DFA Conversion Examples 2, Language identified by NFA/ DFA, NFA to DFA from transition table00:00:00
NFA to DFA Conversion Example 3, Minimization of DFA, Non Reachable State, Power Set Construction00:00:00
Minimization of Deterministic Finite Automata – Theory of Computation, Speed up the execution of DFA00:00:00
Minimization of DFA- Triangulation method, State reduction, Non-Reachable state, Merging states, DFA00:00:00
Minimization of DFA Example 1 – Theory of Computation, State Reduction of DFA, DFA00:00:00
Minimization of DFA Example, State Reduction of DFA, MFA – Theory of Computation, DFA00:00:00
Minimization of DFA with multiple final states – Theory of Computation, State Reduction of DFA, DFA00:00:00
Minimization of DFA – Partition Method –Theory Of Computation, State Reduction of DFA, DFA00:00:00
Minimization of DFA with Multiple Final States, Triangulation Method – Myhill Nerod Theoram, DFA00:00:00
Minimization of DFA, Non Reachable state, Partition Method, State Reduction of DFA, DFA00:00:00
Minimization of DFA ( Non-reachable Region) – Theory of Computation, State Reduction of DFA, DFA00:00:00
Finite Automata with Output – Mealy & Moore Machine – Theory of Computation00:00:00
Finite Automata with Output – Mealy Machine [Examples-1] – Theory of Computatio00:00:00
Finite Automata with Output – Mealy Machine [Examples-2] – Theory of Computation00:00:00
Finite Automata with Output – Mealy Machine [Examples-3] – Theory of Computation00:00:00
Theory of Computation
Free

Enrolment validity: Lifetime