Notebook 17: ω-Regular Expressions ↔︎ Büchi Automata

Every ω-regular language is a finite union of terms U·Vω. See the correspondence between an ω-regular expression and its Büchi automaton, and test ultimately-periodic words against both.

ω-Regular Expressions

An \(\omega\)-regular expression denotes a language of infinite words as a finite union \[ \bigcup_{i=1}^{n} U_i\, V_i^{\omega}, \] where each \(U_i,V_i\) is an ordinary regular language of finite words and \(V_i\) contains no empty word. The Büchi–expression equivalence theorem says these denote exactly the Büchi-recognisable (\(\omega\)-regular) languages.

Two features make the \(U\,V^{\omega}\) shape the right normal form:

  • the \(\omega\)-power \(V^{\omega}\) supplies the infinite behaviour by repeating finite blocks from \(V\) forever;
  • the finite prefix \(U\) absorbs a transient that need not follow the periodic pattern.

Below are two languages over \(\Sigma=\{a,b\}\), each shown as an expression and as its Büchi automaton. Membership of an ultimately-periodic word \(u\cdot v^{\omega}\) is decided by looking only at the period \(v\).

Widget: expression ↔︎ automaton

Büchi automaton

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

Notice \(L_1\) and \(L_2\) are complements of each other: every \(\omega\)-word has either finitely or infinitely many \(a\)’s. That \(L_1\) is again \(\omega\)-regular is a special case of the general complementation theorem — proved algebraically in Chapter 4 (Notebook 24).