CS 3202N · Finite automata · Lessons 1–7

Every method on the sheet, marked as you go.

One module per lesson, each generating a new machine every time. Tables are marked cell by cell and diagrams by the language they accept, so a machine drawn differently from the key still counts, and a subtly wrong one is told which string gives it away.

Modules

One per lesson, in the order they were taught.

7 modules

Lesson 1
5-Tuple & Transition Table
Read a state transition diagram cold and write down (Q, Σ, δ, q₀, F), then build its transition table. DFA and NFA figures both appear, so the shape of a δ cell is part of the question.
Not started
Lesson 2
Design a DFA or NFA
Given a language in words, draw a machine that accepts it. Marked by comparing languages, not shapes — any correct machine passes, and a wrong one comes back with the exact string it gets wrong.
Not started
Lesson 3
NFA → DFA
Subset construction, in the order you would write it by hand: discover the composite states, fill the DFA table, then draw the DFA. Includes the dead state everyone forgets. Hard mode hands you an NFA that converts to 12–18 DFA states — exam length.
Not started
Lesson 4
ε-NFA → NFA
Take every ε-closure, read each symbol from it, then close again — ε*·a·ε* in three marked stages — and work out which states quietly become accepting on the way. That last part is where the marks go.
Not started
Lesson 5
ε-NFA → DFA
The full pipeline in five marked stages: closures, the ε-NFA table, the NFA table, the DFA table, and the DFA diagram. Each stage is checked before the next unlocks, so an early slip does not silently ruin the rest.
Not started
Lesson 6
Minimise a DFA
Equivalence rounds, written the way they go in your notebook: 0-equivalence, 1-equivalence, and on until a round repeats. Then the merged table and the minimal diagram. Every DFA here has states that really do merge.
Not started
Lesson 7
Moore & Mealy machines
Machines that print. Write a Moore or Mealy machine out as its 6-tuple, run inputs through one and write the output, turn a Moore table into a Mealy one, and split a Mealy machine's states to make it Moore.
Not started

Reference

Method sheet
One page: the 5-tuple, the three machine types side by side, each conversion, DFA minimisation and Moore and Mealy machines, written out as the steps you actually perform — with the traps flagged.
Open

Modules

5-Tuple & Transition Table

Design a DFA or NFA

NFA → DFA

ε-NFA → NFA

ε-NFA → DFA

Minimise a DFA

Moore & Mealy machines

Reference

Method sheet