ATLAS

Automata Theory Learning and Simulation

or
Forgot password?
Enter the code of the class you teach to claim it.
or

Check your email

We sent you a verification link. Click it to activate your account, then come back here to sign in.

Reset password

Enter your email and we'll send you a link to reset your password.

Check your email

If an account exists with that email, we sent a password reset link.

© 2026 Kiumbura N. Githinji. All rights reserved.

ATLAS
CS 305 01 - Advanced Computing Code: TH305F
Profile Settings Keyboard Shortcuts
Sign Out

No Topics Yet

Join a class to see topics and start learning.

Topics

  • DFA Deterministic Finite Automata
    0/0
  • NFA Nondeterministic Finite Automata
    0/0
  • .*
    Regex Regular Expressions
    0/0
  • PDA Pushdown Automata
    0/4
  • CFG Context-Free Grammars
    0/3
  • Proofs Proof by Induction
    0/5
  • TM Turing Machines
    0/4
  • P
    P vs NP Computational Complexity
    0/3

Quick Actions

Workspace

Problem Description

Select a problem from the Problems tab to get started, or build your own automaton using the toolbar above.

Click anywhere to add a state, or use the toolbar above
Formal Notation

Syntax Guide:

states: q0, q1, q2
alphabet: a, b
initial: q0
accepting: q2
transitions:
  q0 -a-> q1
  q0 -b-> q0
  q1 -ε-> q2  (epsilon)

Test Strings

Step-by-Step Execution

Speed
Ready States: 0 | Transitions: 0
Press ? for keyboard shortcuts

No Problems Yet

Join a class to see problems assigned by your instructor.

Assigned Problems

No Progress to Show

Join a class to start tracking your progress on problems and topics.

Your Progress

0
Problems Completed
0%
Success Rate
0
Avg. Attempts
--
Class Standing

Progress by Topic

Activity Over Time

My Classes

Join a Class

Enter the class code provided by your instructor.

No classes yet

Click "Join Class" and enter a code from your instructor to get started.

Course Materials Unavailable

Join a class to access course modules, lessons, and study tools.

Course Center

Course Modules

  • Course Overview 100%
  • Mathematical Foundations 0%
  • Deterministic Finite Automata 0%
  • Nondeterministic Finite Automata 0%
  • .* Regular Expressions 0%
  • CFG & Pushdown Automata 0%
  • Turing Machines 0%
  • Decidability & Computability 0%
  • P P vs NP & Complexity 0%

Study Tools

  • Flashcards
  • Practice Quiz
  • Glossary

Course Overview

CS 305 01 - Advanced Computing

Welcome to CS 305 01!

This course explores the theoretical foundations of computer science. You'll learn about the fundamental limits of computation, what problems computers can and cannot solve, and the mathematical models that describe computation.

Learning Objectives

  • Understand finite automata (DFA, NFA) and their applications
  • Master regular expressions and their equivalence to finite automata
  • Learn context-free grammars and pushdown automata
  • Understand Turing machines and the Church-Turing thesis
  • Explore decidability and undecidable problems
  • Comprehend computational complexity (P, NP, NP-Complete)
  • Apply proof techniques including mathematical induction

Course Roadmap

1
Mathematical Foundations

Sets, proofs, induction, languages

2
Finite Automata

DFA, NFA, equivalence, minimization

3
Regular Languages

Regular expressions, pumping lemma

4
Context-Free Languages

CFG, PDA, parsing algorithms

5
Turing Machines

TM variants, Church-Turing thesis

6
Decidability

Decidable languages, halting problem

7
Complexity Theory

P, NP, NP-completeness, reductions

0% Complete

Mathematical Foundations

Essential mathematical concepts for automata theory

1

Sets and Set Operations

Union, intersection, complement, power sets, and Cartesian products

15 min Not Started
2

Strings and Languages

Alphabets, strings, concatenation, Kleene star, and formal languages

20 min Not Started
3

Proof Techniques

Direct proofs, proof by contradiction, and proof by contrapositive

25 min Not Started
4

Mathematical Induction

Weak induction, strong induction, and structural induction

30 min Not Started
Q

Module Quiz: Mathematical Foundations

Test your understanding of sets, languages, and proof techniques

10 questions Locked
0% Complete

Deterministic Finite Automata (DFA)

The simplest model of computation with finite memory

1

Introduction to DFA

What is a DFA? States, transitions, alphabet, and acceptance

20 min Not Started
2

Formal Definition

The 5-tuple definition: (Q, Σ, δ, q₀, F)

25 min Not Started
3

Designing DFAs

Step-by-step approach to constructing DFAs from language descriptions

35 min Not Started
4

DFA Operations

Complement, union, intersection, and concatenation of DFAs

30 min Not Started
5

DFA Minimization

Table-filling algorithm and Myhill-Nerode theorem

40 min Not Started
P

Interactive Practice: Build DFAs

Hands-on exercises in the Workspace

5 exercises Not Started
Q

Module Quiz: DFA

Test your understanding of deterministic finite automata

15 questions Locked
0% Complete

Nondeterministic Finite Automata (NFA)

The power of nondeterminism and its equivalence to DFA

1

Introduction to NFA

What is nondeterminism? How NFAs process input strings

20 min Not Started
2

Epsilon Transitions

ε-transitions, ε-closure, and ε-NFA

25 min Not Started
3

NFA to DFA Conversion

Subset construction algorithm (powerset construction)

35 min Not Started
4

NFA-DFA Equivalence

Proving that NFAs and DFAs recognize the same languages

25 min Not Started
Q

Module Quiz: NFA

Test your understanding of nondeterministic finite automata

12 questions Locked
0% Complete

Regular Expressions

A powerful notation for describing regular languages

1

Regular Expression Basics

Syntax: union, concatenation, Kleene star

25 min Not Started
2

Regex to NFA Conversion

Thompson's construction algorithm

30 min Not Started
3

DFA to Regex Conversion

State elimination method

35 min Not Started
4

Pumping Lemma for Regular Languages

Proving languages are NOT regular

40 min Not Started
Q

Module Quiz: Regular Expressions

Test your understanding of regular expressions and the pumping lemma

15 questions Locked
0% Complete

Context-Free Grammars & Pushdown Automata

Beyond regular languages: the power of a stack

1

Context-Free Grammars

Productions, derivations, and parse trees

30 min Not Started
2

Designing CFGs

Creating grammars for various languages

25 min Not Started
3

Pushdown Automata

Finite automata with a stack

35 min Not Started
4

CFG-PDA Equivalence

Converting between CFGs and PDAs

30 min Not Started
5

Chomsky Normal Form

Converting CFGs to CNF and the CYK algorithm

35 min Not Started
Q

Module Quiz: CFG & PDA

Test your understanding of context-free languages

15 questions Locked
0% Complete

Turing Machines

The universal model of computation

1

Introduction to Turing Machines

Tape, head, states, and transitions

30 min Not Started
2

Formal Definition

The 7-tuple and configurations

25 min Not Started
3

TM Variants

Multi-tape, nondeterministic, and universal TMs

35 min Not Started
4

Church-Turing Thesis

What does it mean to compute?

25 min Not Started
Q

Module Quiz: Turing Machines

Test your understanding of Turing machines

12 questions Locked
0% Complete

Decidability & Computability

What problems can and cannot be solved by algorithms

1

Decidable Languages

Languages that have deciding Turing machines

25 min Not Started
2

The Halting Problem

The most famous undecidable problem

35 min Not Started
3

Reductions

Proving undecidability through reduction

40 min Not Started
4

Rice's Theorem

Non-trivial properties of languages are undecidable

30 min Not Started
Q

Module Quiz: Decidability

Test your understanding of decidable and undecidable problems

12 questions Locked
0% Complete

P vs NP & Complexity Theory

The million dollar question

1

Time Complexity

Big-O notation and analyzing Turing machines

25 min Not Started
2

The Class P

Problems solvable in polynomial time

25 min Not Started
3

The Class NP

Problems verifiable in polynomial time

30 min Not Started
4

NP-Completeness

The hardest problems in NP and polynomial reductions

40 min Not Started
5

Cook-Levin Theorem

SAT is NP-complete

35 min Not Started
Q

Module Quiz: Complexity Theory

Test your understanding of P, NP, and NP-completeness

15 questions Locked

Flashcards

Review key concepts and definitions

Definition

What is a DFA?

Click to reveal answer
Answer

A Deterministic Finite Automaton (DFA) is a 5-tuple (Q, Σ, δ, q₀, F) where Q is a finite set of states, Σ is a finite alphabet, δ: Q × Σ → Q is the transition function, q₀ ∈ Q is the start state, and F ⊆ Q is the set of accepting states.

1 / 50
How well did you know this?

Practice Quiz

Test your knowledge with practice questions

Question 1 of 10

Which of the following is true about DFAs?

Quiz Complete!

8 / 10
80%
8 Correct
2 Incorrect
0 Skipped

Glossary

Key terms and definitions

A
Accepting State

A state in a finite automaton that, when reached after processing an input string, causes the automaton to accept that string. Also called a final state.

Alphabet (Σ)

A finite, non-empty set of symbols used to form strings. Common examples include {0,1} (binary) and {a,b}.

C
Church-Turing Thesis

The hypothesis that any function that can be computed by an algorithm can be computed by a Turing machine.

Context-Free Grammar (CFG)

A formal grammar where every production rule has a single non-terminal on the left side. CFGs generate context-free languages.

D
Decidable Language

A language for which there exists a Turing machine that always halts (accepts or rejects) for every input.

DFA (Deterministic Finite Automaton)

A finite automaton where for each state and input symbol, there is exactly one transition to a next state.

E
Epsilon (ε)

The empty string - a string of length zero. Also used to denote epsilon transitions in NFAs.

H
Halting Problem

The problem of determining whether a given Turing machine halts on a given input. Proven undecidable by Alan Turing.

K
Kleene Star (*)

An operation on a set that produces all possible strings (including empty string) by concatenating zero or more elements from the set.

N
NFA (Nondeterministic Finite Automaton)

A finite automaton that can have multiple transitions for the same input symbol, or epsilon transitions.

NP (Nondeterministic Polynomial)

The class of decision problems for which a solution can be verified in polynomial time by a deterministic Turing machine.

NP-Complete

A problem that is both in NP and NP-hard. If any NP-complete problem can be solved in polynomial time, then P = NP.

P
P (Polynomial Time)

The class of decision problems that can be solved by a deterministic Turing machine in polynomial time.

PDA (Pushdown Automaton)

A finite automaton augmented with a stack memory. PDAs recognize exactly the context-free languages.

Pumping Lemma

A property of regular languages (and separately, context-free languages) used to prove that certain languages are not regular (or not context-free).

R
Regular Expression

A notation for describing regular languages using union, concatenation, and Kleene star operations.

Regular Language

A language that can be recognized by a DFA (equivalently: NFA, or described by a regular expression).

T
Transition Function (δ)

A function that defines how an automaton moves from one state to another based on the current state and input symbol.

Turing Machine

A mathematical model of computation with an infinite tape, a head that reads/writes symbols, and a finite state control.

Slides
Introduction to DFA

Instructor Dashboard

You don't have a class linked yet. Enter your class code to claim it:

0
Students Enrolled
0
Active Today
0
Submissions Today
0
Need Attention

Class Completion Rates

Recent Submissions

Problem Performance

Class Roster

Students

24
Enrolled
18
Active This Week
72%
Avg. Progress
3
Struggling
Student Progress Problems Enrolled On Last Active Status Actions

Course Materials

Problems Manager

0
Total Problems
0
Assigned
0%
Avg. Completion
Problem Topic Assigned Completion Avg. Attempts Actions

Quiz Gradebook

Quiz Passkey

Active Passkey: None

4-20 characters, letters and numbers only

0
Total Students
0
Completed Quiz
--
Class Average
0
Not Started
Student Status Attempt 1 Attempt 2 Attempt 3 Best Average

ATLAS AI

Hey there! Ready to learn?

Hi! I'm Atlas, your AI tutor.

Ask me anything about automata theory, or pick a topic below to get started.

Automaton Conversion

Input

Animation

Step 1: Initialize

Output

Create New Problem

Keyboard Shortcuts

General

Ctrl + S Save
Ctrl + Z Undo
Ctrl + Shift + Z Redo
Ctrl + Enter Run/Test
Ctrl + Shift + Enter Submit
? Show shortcuts

Canvas Tools

V Select tool
S State tool
T Transition tool
D Delete tool
Esc Cancel / Deselect

State Properties

Space Toggle accepting state
I Set as initial state
Delete Delete selected

Execution

Space Play/Pause
← Step back
→ Step forward

Profile Settings

JD
Email cannot be changed

Change Password

Help & Support

Need a refresher? Run the interactive tutorial or watch the animated demo to learn how to use all features.

Sign Out

Are you sure you want to sign out?

You will need to sign in again to access your work.

Drop Class

Are you sure you want to drop ?

You can rejoin later with the class code.

Deactivate Passkey

Deactivate the current quiz passkey?

Students will not be able to start new quiz attempts until you set a new one. In-progress attempts will not be affected.

Delete Problem

Delete ""?

This action cannot be undone. Any student progress on this problem will be lost.

Add Transition

Hi there! I'm Atlas, your guide!
Step 1 of 10

Welcome to ATLAS!

Let's take a quick tour to help you get started.

Hi! I'm Atlas, your friendly guide!

Welcome to ATLAS!

Automata Theory Learning and Simulation

You've successfully created your account. I'll help you learn and practice automata theory concepts through interactive simulations!

Build DFA, NFA, and more
Test with step-by-step execution
Track your progress
Welcome to the ATLAS demo! Step 1 of 19
Let me show you how ATLAS works!
Step 1 of 19
Need help?
Atlas AI

Hi! I'm Atlas.

Ask me anything about automata theory.

Quick Tips
Getting Started

Click on a topic in the sidebar to begin. Start with DFA for the basics!

Adding States

Select the State tool (S) and click anywhere on the canvas to add a new state.

Creating Transitions

Select Transition tool (T), click a state, then click another state to connect them.

Accepting States

Double-click any state to toggle it as an accepting state (shown with double circle).

Initial State

Right-click a state to set it as the initial state (shown with incoming arrow).

Testing Strings

Enter a string in the test panel and click Run to see if your automaton accepts it.

Keyboard Shortcuts

Press ? anytime to see all keyboard shortcuts. Use V, S, T, D to switch tools!

Add Module

Delete Module

Are you sure you want to delete ? This cannot be undone.

© 2026 Kiumbura N. Githinji. All rights reserved.