Notebook 16: The DBA vs NBA Gap

Why ‘finitely many saves’ needs nondeterminism: an NBA guesses the last save and accepts, while no deterministic Büchi automaton can separate the two cases. The obstruction that forces the whole complementation chapter.

Deterministic Büchi Automata Are Strictly Weaker

For finite words, complementing a DFA is a one-line trick: complete it with a sink and swap accepting / non-accepting states. This fails for Büchi automata for two reasons — nondeterminism (no unique run to reverse) and, more deeply, that deterministic Büchi automata (DBA) recognise strictly fewer languages than nondeterministic ones (NBA).

The running witness is the complement of “infinitely many saves”. After the initial open, over \(\Gamma=\{\texttt{edit},\texttt{save},\texttt{idle}\}\): \[ \overline{L}=\{\alpha : \text{only finitely many } \texttt{save}\text{ occur}\}. \]

This notebook shows both halves of the gap: an NBA does recognise \(\overline L\), and a natural DBA attempt provably fails.

Widget 1: The NBA recognises \(\overline{L}\)

The NBA guesses the position after which no more save ever arrives, then jumps to an accepting component that reads only edit/idle (a save there kills the run). A word \(u\cdot v^{\omega}\) has only finitely many saves iff its period \(v\) contains no save.

Word α = u · vω (stem + 3 periods)

Widget 2: Any deterministic attempt fails

Here is the most natural DBA one might try for \(\overline L\) — call it \(\mathcal D\). It accepts whenever it keeps seeing non-save symbols:

  • \(d_0\) (accepting): reading edit or idle stays / returns here.
  • \(d_1\) (non-accepting): reading save goes here.

\(\mathcal D\) visits its accepting state \(d_0\) infinitely often exactly when edit/idle occur infinitely often — which is not the same as “finitely many saves”. The button below feeds \(\mathcal D\) the adversarial word \((\texttt{save}\ \texttt{idle})^{\omega}\): it has infinitely many saves (so it is not in \(\overline L\)), yet \(\mathcal D\) accepts it.

the general obstruction: delay each save past the next visit to d0

Run of 𝒟 (period shown 4×)

The lesson is not that complementation is impossible — \(\omega\)-regular languages are closed under complement. It is that the finite-word state-swapping shortcut does not transfer. The rest of the chapter builds the complement algebraically, via the congruence \(\approx_{\mathcal A}\) and a Ramsey decomposition — see Notebook 21 and Notebook 23.