₹0 for students · Certificate · Intermediate

Automata and Computation

1 mini course, 5 lessons: finite automata, regular expressions, grammars, Turing machines and the limits of computing

5 lessons · ~1 hours · 10-question final exam · pass mark 70%

About the course

What you’ll learn

The theory behind regular expressions, compilers and the question 'what can computers compute at all?'. Build and simulate finite automata, connect them to regular expressions, see where they fail and grammars take over, understand pushdown automata and parsing, and meet Turing machines, the halting problem and P versus NP. Every machine is simulated in Python. Pass every lesson quiz and the final exam to earn a verifiable certificate.

Theory of computationAutomataRegular expressionsCompilers basics

Part of the career track: Computer Science Foundations

How the certificate works

Read each lesson’s study guide, then the full lesson and any notebooks or exercises.
Pass every lesson quiz with 70% or more.
Pass the final exam: 10 questions in 20 minutes.
Get a certificate with a public verification link, and add it to LinkedIn.

Syllabus

5 lessons in 1 mini courses

Each mini course takes about an hour. Already know one? Test out in the app and skip it.

1. Theory of computation essentials

Design automata and grammars, and explain the limits of computation.

Finite Automata

12 min · A DFA has states, a start state, accepting states and a transition rule.

NFAs and Regular Expressions

12 min · An NFA can have several possible moves; it accepts if any path accepts.

Beyond Regular: Context-Free Grammars

12 min · Finite automata can't count without limit: aⁿbⁿ and balanced brackets aren't regular.

Pushdown Automata and Parsing

10 min · A pushdown automaton is a finite automaton plus a stack.

Turing Machines and the Limits of Computing

12 min · A Turing machine has finite control and an unlimited read/write tape.

Written by Vikosha. Lessons, questions and exercises are original. Licence: Original Vikosha course..