Theory of Computation(TOC) : Automata Theory for 2021

Learn DFA, NFA, DPDA, NPDA, LBA, Turing Machine.
English [Auto]
Able to design Finite Automata machines for given problems.
Able to analyze a given Finite Automata machine and find out its Language.
Able to design Pushdown Automata machine for given CF language(s).
Able to generate the strings/sentences of a given context-free languages using its grammar.


  • No prerequisites. Starting from scratch.



Formal languages and automata theory deals with the concepts of automata, formal languages, grammar, computability and decidability. The reasons to study Formal Languages and Automata Theory are Automata Theory provides a simple, elegant view of the complex machine that we call a computer. Automata Theory possesses a high degree of permanence and stability, in contrast with the ever-changing paradigms of the technology, development, and management of computer systems. Further, parts of the Automata theory have direct bearing on practice, such as Automata on circuit design, compiler design, and search algorithms; Formal Languages and Grammars on

compiler design; and Complexity on cryptography and optimization problems in manufacturing, business, and management. Last, but not least, research oriented students will make good use of the Automata theory studied in this course.

Course Objectives:

To understand the concept of machines: finite automata, pushdown automata, linear bounded automata, and Turing machines.

To understand the formal languages and grammars: regular grammar and regular languages, context-free languages and context-free grammar; and introduction to context-sensitive language and context-free grammar, and unrestricted grammar and languages.

To understand the relation between these formal languages, grammars, and machines.

To understand the complexity or difficulty level of problems when solved using these machines.

To understand the concept of algorithm.

To compare the complexity of problems.

Who this course is for:

  • For everyone

  • Academic Students.

  • Interview Preparation Persons.

  • Competitive Exam Preparation Aspirants.

  • Anyone interested in Theory of computation/ Automata Theory.

Who this course is for:

  • Academic Students.
  • Competitive Exams Aspirants.

Course content

1 section9 lectures1h 22m total length
  • Deterministic Finite Automata : Definition
  • Language of DFA ( L(M)).
  • Construct Minimal DFA : Example 1
  • Construct Minimal DFA : Example 2
  • Construct Minimal DFA : Example 3
  • Construct Minimal DFA : Example 4
  • Key points : No.of States for starting with, ending with and substring.
  • Construct Minimal DFA : Example 5
  • Construct Minimal DFA : Example 6


Professional GATE CS/IT Faculty
Atchyut Kumar
  • 4.6 Instructor Rating
  • 192 Reviews
  • 7,249 Students
  • 12 Courses

Atchyut Kumar is popular programming and GATE CS/IT instructor. He did his Masters from National Institute of Technology-Calicut. He is GATE CS/IT top ranker with 99.97 percentile. He have three years of experience in database development and 7+ years years as GATE faculty.  Totally, He have 11+ Years of overall experience in Teaching/research/Industry where trained over 30000 students in classroom and online courses. He is expert in problem solving techniques, algorithms, competitive programming. Most of his ex-students are working in Amazon, Samsung, Oracle, Google, Adobe and more  and some of them pursuing higher studies like MS, M.Tech or Ph.D.