Theory of Computation part 1

Wishlist Share
Share Course
Page Link
Share On Social Media

About Course

Theory of Computation part 1

The theory of computation is a branch of computer science that studies the ability of computers to solve problems. It is a mathematical field of study that focuses on the power and limitations of computing devices. In other words, it is concerned with the study of what computers can and cannot do. The theory of computation is based on the idea that any problem can be solved if it is broken down into smaller problems and each problem is solved one at a time. This approach is known as an algorithm, which is a sequence of instructions that can be followed to solve a given problem. Algorithms are used in computer programming to create software applications. The most important concept in the theory of computation is the Turing machine, which is a hypothetical machine that can solve any computable problem. This machine is used to prove theorems and to determine the computational power of computers. The theory of computation also studies the complexity of algorithms. Complexity refers to the amount of time and resources needed to solve a given problem. Algorithms that require more time and resources are said to be more complex than those that require less. The theory of computation is also used to study the limits of what computers can do. For example, some problems may be too difficult to solve efficiently and require too much time to compute. In these cases, computers might not be able to solve them and we must look for alternative solutions. The theory of computation is a fascinating field that has many applications in the real world. It is used to create more efficient algorithms and solve complex problems. It is also a powerful tool for understanding the power and limitations of computers.

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.

 

Show More

What Will You 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

Course Content

Theory of Computation part 1

  • Introduction to Theory of Computation, Need of Theory of Computation, Target Audience of TOC
    07:25
  • Why study theory of Computation?, Theory of Computation, TOC
    07:48
  • Content & Course flow in Theory of Computation Lecture Series, Chomsky’s Hierachy, TOC
    12:09
  • Regular language in Theory of Computation, Definition and Meaning of Regular Language, TOC
    10:17
  • Operations on Regular language in Theory of Computation, (Union, Concatenation & Star Operation)
    08:16
  • Examples of regular language in Theory of computation, Rules of Regular Language, TOC
    17:29
  • Examples of Regular Language in Theory of Computation, (Rules of Regular Language), TOC
    15:07
  • Finite Automata definition, Important Terminologies of Finite Automata, Theory of Computation, TOC
    11:11
  • Finite Automata Examples in Theory of Computations, Examples of DFA & NFA, DFA, NFA
    14: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 Automata
    18:31
  • DFA Examples 2- Theory of Computation, Dead State in Finite Automata, Deterministic Finite Automata
    16:50
  • DFA Examples 3 – Theory of Computation, Dead State in Finite Automata, Language accepted by DFA
    07:37
  • DFA Examples 4, Dead State in Finite Automata, Atleast constraint in DFA, Atmost Constraints in DFA
    14:57
  • Non Deterministic Finite Automata Theory & Example-1, Multiple Transition Path in NFA, TOC
    00:00
  • NFA Examples 2 – Theory of Computation, Validation check of NFA, NFA Example with substring, TOC
    00:00
  • NFA Example 3 – Theory of Computation, Validation check of NFA, Accepting State in NFA, TOC
    00:00
  • NFA Examples 4 – Theory of computation, NFA accepting words, NFA non-accepting words, TOC
    00:00
  • NFA to DFA Conversion – Theory of Computation, Algorithm to convert NFA to DFA, Equivalency NFA=DFA
    00:00
  • NFA to DFA Conversion Examples – Theory of Computation, Subset construction method, TOC
    00:00
  • NFA to DFA Conversion Examples 2, Language identified by NFA/ DFA, NFA to DFA from transition table
    00:00
  • NFA to DFA Conversion Example 3, Minimization of DFA, Non Reachable State, Power Set Construction
    10:31
  • Minimization of Deterministic Finite Automata – Theory of Computation, Speed up the execution of DFA
    11:22
  • Minimization of DFA- Triangulation method, State reduction, Non-Reachable state, Merging states, DFA
    00:00
  • Minimization of DFA Example 1 – Theory of Computation, State Reduction of DFA, DFA
    00:00
  • Minimization of DFA Example, State Reduction of DFA, MFA – Theory of Computation, DFA
    00:00
  • Minimization of DFA with multiple final states – Theory of Computation, State Reduction of DFA, DFA
    00:00
  • Minimization of DFA – Partition Method –Theory Of Computation, State Reduction of DFA, DFA
    00:00
  • Minimization of DFA with Multiple Final States, Triangulation Method – Myhill Nerod Theoram, DFA
    00:00
  • Minimization of DFA, Non Reachable state, Partition Method, State Reduction of DFA, DFA
    00:00
  • Minimization of DFA ( Non-reachable Region) – Theory of Computation, State Reduction of DFA, DFA
    00:00
  • Finite Automata with Output – Mealy & Moore Machine – Theory of Computation
    00:00
  • Finite Automata with Output – Mealy Machine [Examples-1] – Theory of Computatio
    00:00
  • Finite Automata with Output – Mealy Machine [Examples-2] – Theory of Computation
    00:00
  • Finite Automata with Output – Mealy Machine [Examples-3] – Theory of Computation
    00:00

Student Ratings & Reviews

No Review Yet
No Review Yet
Each day we give 100 Discount Coupons to the first 100 new visitors to our website. To benefit from this offer, use this code 1DF835024E during your orders to get 20% OFF
This is default text for notification bar