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

Lessons

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

Module quiz

1. Which set is the language of all strings over Σ, including the empty string?
2. A DFA reads 'abb'. How many transitions does it make?
3. What makes a finite automaton deterministic?
4. How many states does the remainder DFA for 'divisible by 5' need?
5. A product DFA accepts only pairs where both halves accept. Which language does it recognise?
6. Swapping the accepting states of an incomplete DFA can fail. Why?

Nondeterminism ›