Notebook 1: Finite-State Automata
Interactive Chapter 1 Notebook
This notebook turns the first chapter into a small laboratory. The focus is on the objects that matter early in automata theory:
- alphabets
- finite words
- languages as sets of words
- deterministic finite automata
The page is intentionally concrete. Each section lets you manipulate the definition and immediately see what changes.
Mental Model
Alphabet
A finite set of symbols. Example: {a, b}.
Word
A finite sequence built from the alphabet. Example: abba.
Language
A set of words sharing a property, such as “ends in a”.
DFA
A finite machine that reads a word left to right and decides whether that word belongs to a language.
1. Alphabet and Word Playground
Use this section to build a finite alphabet and inspect the words it generates up to a bounded length.
The key definition here is \(A^*\): the set of all finite words over the alphabet \(A\). The playground only shows a finite prefix of \(A^*\), because the full set is infinite as soon as the alphabet is non-empty.
2. Language Explorer
Now fix an alphabet and choose a property. The resulting language is the set of all words satisfying that property.
This is the main shift in viewpoint: a language is not one word, but a criterion for membership.
3. DFA Simulator
This DFA recognizes the language
\[ L = \{ w \in \{a,b\}^* \mid w \text{ contains an even number of } a \text{'s} \}. \]
The machine has only two states because parity is the only information it needs to remember.
Current Configuration
Transition Trace
Transition Table
| State | Read a | Read b |
|---|---|---|
q_even |
q_odd |
q_even |
q_odd |
q_even |
q_odd |
The deterministic point should be visible here: at every step there is exactly one next state.
Reading the Definitions Back Out of the Interaction
The notebook is useful only if the interactions map back to the formal objects.
\(A^*\)
The alphabet playground shows finite prefixes of the set of all finite words over an alphabet.
\(L \subseteq A^*\)
The language explorer separates generated words into “in the language” and “not in the language”.
\(\delta\) and \(\widehat{\delta}\)
The DFA simulator applies one-symbol transitions and accumulates them over a whole input word.
Acceptance
The final verdict depends only on the state reached after the full word is consumed.
Exercises to Try
- In the alphabet playground, compare the number of generated words for maximum lengths 2, 3, and 4.
- In the language explorer, check whether the empty word belongs to each sample language.
- In the DFA simulator, try
abba,aaa,bbbb, and the empty word. - Explain why the DFA only needs to remember parity, not the exact number of
a’s.