Home>Courses>Theory of Computation

Theory of Computation

This course provides a comprehensive study of formal languages, covering regular languages, context-free languages, and recursively enumerable languages.

Beginner

56 Lessons

15h

Certificate of Completion

This course provides a comprehensive study of formal languages, covering regular languages, context-free languages, and recursively enumerable languages.

AI-POWERED

Explanations

AI-POWERED

Explanations

This course includes

10 Assessments

10 Playgrounds

9 Quizzes

Course Overview

What You'll Learn

Course Content

Recommendations

Course Overview

What are the mathematics behind computers? What are the theoretical foundations of computer languages? Such questions can be explored by understanding formal languages and automata models. In this comprehensive course, you’ll explore formal languages, regular languages, and how to model them with their associated automata models. Next, you’ll cover regular expressions and grammar, and their equivalents. Then, you’ll explore context-free languages (the foundations of programming languages), pushdown automa...Show More

What You'll Learn

A solid understanding of formal languages, their structures and properties

Working knowledge of capabilities and limitations of different types of automata

The ability to convert between regular expressions, finite automata, context-free grammars and pushdown automata

Insights into computability theory, undecidability, reductions and the halting problem

A solid understanding of formal languages, their structures and properties

Course Content

Getting Started

5 Lessons

Prerequisites and Learning Outcomes

Introduction to Computation

Formal Languages

Finite State Machines

Finite Automata in Real-life Situations

Exam on Formal Languages

Assessment

Finite Automata

9 Lessons

Deterministic Finite Automata

Regular Languages

Nondeterministic Finite Automata

Equivalence of NFAs and DFAs

Minimal Mealy Machines

Exam on Finite Automata

Assessment

Regular Expressions and Grammars

3 Lessons

Regular Expressions

Equivalence of Regular Expressions and Regular Languages

Regular Grammars

Exam on Regular Expressions and Grammars

Assessment

Properties of Regular Languages

6 Lessons

Closure Properties

Decision Algorithms for Equality of Two Languages

Other Decision Algorithms

Pumping Theorem for Regular Languages

Nonregular Languages

Using Closure Properties to Show Nonregularity

Exam on Properties of Regular Languages

Assessment

Pushdown Automata

3 Lessons

Adding a Stack to Finite Automata

Examples of PDA

Pushdown Automata and Determinism

Exam on Pushdown Automata

Assessment

11.

Context-Free Grammars

7 Lessons

Introduction to Context-free Grammars

Context-free Grammars and Derivations

Simplifying Grammars

Derivation Trees and Ambiguous Grammars

Equivalence of PDAs and CFGs

From PDA to CFG (General Case)

Examples of Converting PDA to CFG (General Case)

Exam on Context-Free Grammars

Assessment

13.

Properties of Context-Free Languages

7 Lessons

Chomsky Normal Form

Chomsky Normal Form Rules

Closure Properties

Decision Algorithms

Is a CFL Empty or Infinite?

Infinite CFLs and Another Pumping Theorem

Examples Using the Pumping Theorem for Context-free Languages

Exam on Properties of Context-Free Languages

Assessment

15.

Turing Machines

8 Lessons

Introduction to Turing Machines

The Standard Turing Machine

Turing Machines as Functions

Formal Definition and Examples of Turing Machines

Church-Turing Thesis

Variations on Turing Machines

The Universal Turing Machine

Nondeterministic Turing machine = Deterministic Turing machine

Exam on Turing Machines

Assessment

17.

The Landscape of Formal Languages

4 Lessons

Recursively Enumerable Languages

Unrestricted Grammars

Equivalence of Unrestricted Grammars and Turing Machines

The Chomsky Hierarchy

Exam on the Landscape of Formal Languages

Assessment

19.

Computability

3 Lessons

The Halting Problem

Reductions and Undecidability

Rice's Theorem and Decidability

Exam on Computability

Assessment

21.

Conclusion

1 Lessons

Wrap Up

Course Author

Chuck Allison

Trusted by 2.5 million developers working at companies

"These are high-quality courses. Trust me. I own around 10 and the price is worth it for the content quality. EducativeInc came at the right time in my career. I'm understanding topics better than with any book or online video tutorial I've done. Truly made for developers. Thanks"

Anthony Walker

@_webarchitect_

"Just finished my first full #ML course: Machine learning for Software Engineers from Educative, Inc. ... Highly recommend!"

Evan Dunbar

ML Engineer

"You guys are the gold standard of crash-courses... Narrow enough that it doesn't need years of study or a full blown book to get the gist, but broad enough that an afternoon of Googling doesn't cut it."

Carlos Matias La Borde

Software Developer

"I spend my days and nights on Educative. It is indispensable. It is such a unique and reader-friendly site"

Souvik Kundu

Front-end Developer

"Your courses are simply awesome, the depth they go into and the breadth of coverage is so good that I don't have to refer to 10 different websites looking for interview topics and content."

Vinay Krishnaiah

Software Developer

"I've tried probably 5-7 different sites and Educative is easily the best. It perfectly blends explanation with interactivity"

Eric Downs

Musician/Entrepeneur

Hands-on Learning Powered by AI

See how Educative uses AI to make your learning more immersive than ever before.

Instant Code Feedback

Evaluate and debug your code with the click of a button. Get real-time feedback on test cases, including time and space complexity of your solutions.

AI-Powered Mock Interviews

Put your skills to the test in a simulated interview setting. Receive personalized feedback based on your performance. Available in Premium & Premium Plus plans.

Adaptive Learning

At various checkpoints throughout Educative courses, you will be prompted to take a quick assessment. Receive a condensed curriculum tailored to your strengths and skill gaps.

Explain with AI

Select any text within any Educative course, and get an instant explanation — without ever leaving your browser.

AI Code Mentor

AI Code Mentor helps you quickly identify errors in your code, learn from your mistakes, and nudge you in the right direction — just like a 1:1 tutor!

Recommended before starting this course

Course

Learn Python 3 from Scratch

Gain insights into Python 3 basics, from built-in functions to data types and program structures, culminating in a hands-on project. Become a lifelong learner in computing.

beginner

6 hours

Course

Introduction to Computers & Programming

An introductory course on computers and programming focusing on logic building and problem-solving skills through hands-on exercises.

beginner

6 hours

Course

Introduction to Logic: Basics of Mathematical Reasoning

Basic concepts of mathematical logic will be covered. This will help us to understand and construct mathematical reasoning and arguments.

beginner

6 hours