Home>Courses>Theory of Computation

Theory of Computation

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.

Beginner

56 Lessons

15h

Certificate of Completion

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

Course Content

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

11.

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

13.

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

15.

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

17.

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

19.

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

21.

Conclusion

1 Lessons

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

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

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.

beginner

6 hours

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.

beginner

6 hours

Course

Learn Python 3 from Scratch

beginner

6 hour

Course

Introduction to Computers & Programming

beginner

6 hour

Course

Introduction to Logic: Basics of Mathematical Reasoning

beginner

6 hour

Related Courses and Skill Paths

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.

beginner

3 hours

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.

beginner

3 hours

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.

beginner

1 hour 40 mins

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