Notebook 21: The ≈𝒜 Profile of a Word
What \(\approx_{\mathcal A}\) Remembers
The congruence at the core of the complementation proof does not remember the exact word. For a finite word \(u\) it remembers only, for every pair of states \((p,q)\):
- whether some path labelled \(u\) goes from \(p\) to \(q\) at all, and
- if so, whether such a path can visit an accepting state along the way.
This is a finite profile — a grid over \(Q\times Q\) with entries in \(\{-,\ q,\ q^{F}\}\):
- \(-\) : no path from \(p\) to \(q\) labelled \(u\);
- \(q\) : a path reaches \(q\), but without visiting \(F\);
- \(q^{F}\) : a path reaches \(q\) visiting an accepting state.
Two words are \(\approx_{\mathcal A}\)-equivalent exactly when they have the same grid. There are finitely many grids, so \(\approx_{\mathcal A}\) has finite index — and it saturates \(L(\mathcal A)\). The automaton \(\mathcal A\) used here (from the chapter) accepts the \(\omega\)-words in which the block \(ab\) occurs infinitely often, separated by \(c\)’s. Note \(\Delta\) is partial: a missing transition means the run has nowhere to go, not a sink.
Widget: compute and compare profiles
Automaton 𝒜 (F = {s₁})
The default pair reproduces the chapter’s example: for \(u=c\) the only non-trivial cell is \((s_2,s_2)=s_2\) (a \(c\)-loop that never touches \(F\)), whereas for \(u=ab\) two cells carry \(F\), at \((s_0,s_2)\) and \((s_2,s_2)\) — the path \(s_0\!\to\!s_1\!\to\!s_2\) visits \(s_1\in F\). Different cells at the same position, so \(c\not\approx_{\mathcal A}ab\). Try abc vs abcc: equal grids — the extra \(c\) just loops at \(s_2\), which is why every block \(ab\,c^{i}\) falls in one class (the key fact behind Notebook 23).