This course provides a comprehensive study of formal languages, covering regular languages, context-free languages, and recursively enumerable languages.

Beginner

56 Lessons

15h

Certificate of Completion

This course provides a comprehensive study of formal languages, covering regular languages, context-free languages, and recursively enumerable languages.

AI-POWERED

AI-POWERED

Explanations

This course includes

10 Assessments

10 Playgrounds

9 Quizzes

This course includes

10 Assessments

10 Playgrounds

9 Quizzes

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

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

What You'll Learn

A solid understanding of formal languages, their structures and properties

Show more

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

Trusted by 1.4 million developers working at companies

Anthony Walker

@_webarchitect_

Emma Bostian 🐞

@EmmaBostian

Evan Dunbar

ML Engineer

Carlos Matias La Borde

Software Developer

Souvik Kundu

Front-end Developer

Vinay Krishnaiah

Software Developer

Eric Downs

Musician/Entrepeneur

Kenan Eyvazov

DevOps Engineer

Souvik Kundu

Front-end Developer

Eric Downs

Musician/Entrepeneur

Anthony Walker

@_webarchitect_

Emma Bostian 🐞

@EmmaBostian

Hands-on Learning Powered by AI

See how Educative uses AI to make your learning more immersive than ever before.

Instant Code Feedback

AI-Powered Mock Interviews

Adaptive Learning

Explain with AI

AI Code Mentor