Strings and finite automata
The vocabulary of the subject, alphabets, strings and languages, and the deterministic finite automaton: how to define, run and design one, and how to combine two.
About 4 hours of study
Learning objectives
- Describe problems as languages over an alphabet
- Define and simulate a DFA
- Design DFAs and build complements and products
Lessons
- 1
Alphabets, strings and languages Intermediate
The vocabulary of the theory of computation: alphabets, strings, the empty string, and languages as sets of strings, built and tested in Python.
- 2
Deterministic finite automata (DFA) Intermediate
A DFA reads a string one symbol at a time with a fixed, finite memory. Define one as five parts, draw its table and run it in Python.
- 3
Designing DFAs: memory, complement and product Intermediate
Design a DFA by deciding what it must remember, then build new machines from old ones: swap accepting states for the complement, and run two machines at once for intersection and union.
Module practice
- Theory: Facts about a wordEasy
- Theory: Every string of a given lengthMedium
- Theory: Concatenating two languagesHard
- Theory: An even number of a'sEasy
- Theory: Run any DFAMedium
- Theory: Show a DFA's runHard
- Theory: The complement of a DFAEasy
- Theory: A DFA for divisibilityMedium
- Theory: Two DFAs at onceHard