Theory of Computation
Beginner
56 Lessons
15h
Certificate of Completion
Takeaway Skills
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
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
Course Content
Getting Started
Exam on Formal Languages
Assessment
Finite Automata
Exam on Finite Automata
Assessment
Regular Expressions and Grammars
Exam on Regular Expressions and Grammars
Assessment
Properties of Regular Languages
Exam on Properties of Regular Languages
Assessment
Pushdown Automata
Exam on Pushdown Automata
Assessment
Context-Free Grammars
7 Lessons
Exam on Context-Free Grammars
Assessment
Properties of Context-Free Languages
7 Lessons
Exam on Properties of Context-Free Languages
Assessment
Turing Machines
8 Lessons
Exam on Turing Machines
Assessment
The Landscape of Formal Languages
4 Lessons
Exam on the Landscape of Formal Languages
Assessment
Computability
3 Lessons
Exam on Computability
Assessment
Conclusion
1 Lesson
How You'll Learn
You don’t get better at swimming by watching others. Coding is no different. Practice as you learn with live code environments inside your browser.
Videos are holding you back. Educative‘s interactive, text-based lessons accelerate learning — no setup, downloads, or alt-tabbing required.
Learn faster and smarter with adaptive AI tools embedded in every Educative course.
Built-in assessments let you test your skills. Completion certificates let you show them off.
Recommended Courses
BEFORE STARTING THIS COURSE
AFTER FINISHING THIS COURSE