INTERACTIVE COURSE

Beginner

56 Lessons

15h

Certificate of Completion

AI Explanations

AI Explanations

10 Assessments

10 Playgrounds

9 Quizzes

260 Illustrations

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

Course Content

1

Getting Started

Prerequisites and Learning OutcomesIntroduction to ComputationFormal LanguagesFinite State MachinesFinite Automata in Real-life Situations

Exam on Formal Languages

Assessment

2

Finite Automata

Deterministic Finite AutomataRegular LanguagesNondeterministic Finite AutomataEquivalence of NFAs and DFAsNFAs and ComplementsMinimal AutomataMachines with OutputComputer ArithmeticMinimal Mealy Machines

Exam on Finite Automata

Assessment

3

Regular Expressions and Grammars

Exam on Regular Expressions and Grammars

Assessment

4

Properties of Regular Languages

Closure PropertiesDecision Algorithms for Equality of Two LanguagesOther Decision AlgorithmsPumping Theorem for Regular LanguagesNonregular LanguagesUsing Closure Properties to Show Nonregularity

Exam on Properties of Regular Languages

Assessment

5

Pushdown Automata

Exam on Pushdown Automata

Assessment

6

Context-Free Grammars

7 Lessons

Exam on Context-Free Grammars

Assessment

7

Properties of Context-Free Languages

7 Lessons

Exam on Properties of Context-Free Languages

Assessment

8

Turing Machines

8 Lessons

Exam on Turing Machines

Assessment

9

The Landscape of Formal Languages

4 Lessons

Exam on the Landscape of Formal Languages

Assessment

10

Computability

3 Lessons

Exam on Computability

Assessment

11

Conclusion

1 Lesson

COURSE AUTHOR

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