HomeCoursesTheory of Computation

Beginner

15h

Updated 5 months ago

Theory of Computation
Save

Gain insights into formal languages, regular languages, regular expressions, context-free languages, and Turing machines. Delve into automata models and enhance problem-solving skills through extensive exercises.

Join 2.7 million developers at

Overview

Content

Reviews

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 automata, and the relationship between them. Toward the end, you’ll learn about recursively enumerable languages, Turing machines with their variations, context-sensitive languages, and unrestricted grammars. By the end of the course, you’ll have gained a deep understanding of several formal languages and their associated automata. Also, since there are plenty of exercises throughout the course, your understanding and problem-solving skills will be thoroughly reinforced.

What are the mathematics behind computers? What are the theoretical foundations of computer languages? Such questions can be exp...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

Content

56 Lessons9 Quizzes10 Assessments

Getting Started

5 Lessons

Get familiar with core computation concepts, formal languages, and finite state machines.

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

Walk through finite automata concepts, including DFAs, NFAs, regular languages, and machine minimization.

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

Break apart regular expressions, their equivalence with finite automata, and regular grammars.

Regular Expressions

Equivalence of Regular Expressions and Regular Languages

Regular Grammars

Exam on Regular Expressions and Grammars

Assessment

Properties of Regular Languages

6 Lessons

Grasp the fundamentals of regular languages, decision algorithms, Pumping Theorem, and nonregular language properties.

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

Deepen your knowledge of pushdown automata, their applications, and deterministic vs. nondeterministic behaviors.

Adding a Stack to Finite Automata

Examples of PDA

Pushdown Automata and Determinism

Exam on Pushdown Automata

Assessment

Context-Free Grammars

7 Lessons

Focus on the structure, simplification, and conversion of context-free grammars and pushdown automata.

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

Properties of Context-Free Languages

7 Lessons

Master the key properties, algorithms, and formalisms of context-free languages.

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

Turing Machines

8 Lessons

Try out Turing machines, their definitions, functions, variations, and the Church-Turing Thesis.

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

The Landscape of Formal Languages

4 Lessons

Unpack the core of formal languages, from RE languages and unrestricted grammars to Chomsky hierarchy.

Recursively Enumerable Languages

Unrestricted Grammars

Equivalence of Unrestricted Grammars and Turing Machines

The Chomsky Hierarchy

Exam on the Landscape of Formal Languages

Assessment

10.

Computability

3 Lessons

Examine limits of computability, undecidability problems, and implications of Rice's theorem.

The Halting Problem

Reductions and Undecidability

Rice's Theorem and Decidability

Exam on Computability

Assessment

11.

Conclusion

1 Lessons

Grasp the fundamentals of computation models, language representation, and computational boundaries.

Wrap Up

Certificate of Completion

Showcase your accomplishment by sharing your certificate of completion.

Course Author:

Chuck Allison

Developed by MAANG Engineers

Every Educative resource is designed by our in-house team of ex-MAANG software engineers and PhD computer science educators — subject matter experts who’ve shipped production code at scale and taught the theory behind it. The goal is to get you hands-on with the skills you need to stay ahead in today's constantly evolving tech landscape. No videos, no fluff — just interactive, project-based learning with personalized feedback that adapts to your goals and experience.

Trusted by 2.7 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."

Software Developer

Carlos Matias La Borde

"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

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 Mock Interviews

Test your skills in a simulated interview setting. Receive personalized feedback based on your performance. Available for Coding Interviews, System Design, and more.

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!

Course

Python Regular Expressions with Data Scraping Projects

Gain insights into Python's regular expressions with practical examples, web scraping projects, coding exercises, and beginner-friendly lectures. Delve into real-world data and enhance your Python skills effectively.

3 h

beginner

Course

JavaScript Regular Expressions in Detail

Explore JavaScript regular expressions: learn about regex history, create patterns with special characters, parse data, and match passwords/emails, gaining comprehensive text processing skills.

3 h

beginner

Course

Regular Expressions for Programmers

Gain insights into regular expressions' utility for text manipulation. Learn about efficient searching and replacing commands to enhance productivity in daily programming tasks.

1 h 40 m

beginner

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.

6 h

beginner

Course

Introduction to Computers & Programming

Gain insights into basic computer anatomy, binary systems, and program lifecycles. Delve into logic building and core programming concepts with hands-on exercises and quizzes to reinforce learning.

6 h

beginner

Course

Introduction to Logic: Basics of Mathematical Reasoning

Gain insights into formal logic, propositional logic, and first-order logic. Learn about inference rules and master constructing rigorous proofs, enhancing critical thinking and problem-solving skills.

6 h

beginner

Course

Python Regular Expressions with Data Scraping Projects

beginner

3 hour

Course

JavaScript Regular Expressions in Detail

beginner

3 hour

Course

Regular Expressions for Programmers