HomeCoursesTheory of Computation

Updated 27 Aug

AI-powered learning

Save

Theory of Computation

Name: Theory of Computation
Price: 59 USD
Author: Chuck Allison

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.

56 lessons

15h

Created by Chuck Allison

What's included

56 lessons across 12 modules
9 quizzes with instant feedback
AI Tutor on every lesson

Join 3.1 million developers at

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

Learning Roadmap

56 Lessons9 Quizzes10 Assessments

Getting Started

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

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.

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.

Exam on Properties of Regular Languages

Assessment

Pushdown Automata

3 Lessons

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

Exam on Pushdown Automata

Assessment

Context-Free Grammars

7 Lessons

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

Exam on Context-Free Grammars

Assessment

Properties of Context-Free Languages

7 Lessons

Master the key properties, algorithms, and formalisms of 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.

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.

Exam on the Landscape of Formal Languages

Assessment

10.

Computability

3 Lessons

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

Exam on Computability

Assessment

11.

Conclusion

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.

About this course

WHY I WROTE THIS COURSE

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.

ABOUT THE AUTHOR

Chuck Allison

Professor Emeritus of Computer Science. Previously a software engineer with two decades of experience.

Learn more about Chuck

Trusted by 3.1 million developers working at companies

These are high-quality courses. Trust me the price is worth it for the content quality. Educative 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

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

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 inference rules and master proof construction to sharpen 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