Star Height - Eggan's Theorem

Eggan's Theorem

In his seminal study of the star height of regular languages, Eggan (1963) established a relation between the theories of regular expressions, finite automata, and of directed graphs. In subsequent years, this relation became known as Eggan's theorem, cf. Sakarovitch (2009). We recall a few concepts from graph theory and automata theory.

In graph theory, the cycle rank r(G) of a directed graph G = (V, E) is inductively defined as follows:

• If G is acyclic, then r(G) = 0.
• If G is strongly connected and E is nonempty, then

where G - v is the digraph resulting from deletion of vertex v and all edges beginning or ending at v.

• If G is not strongly connected, then r(G) is equal to the maximum cycle rank among all strongly connected components of G.

In automata theory, a nondeterministic finite automaton with ε-moves (ε-NFA) is defined as a 5-tuple, (Q, Σ, δ, q₀, F), consisting of

• a finite set of states Q
• a finite set of input symbols Σ
• a set of labeled edges δ, referred to as transition relation: Q × (Σ ∪{ε}) × Q. Here ε denotes the empty word.
• an initial state q₀ ∈ Q
• a set of states F distinguished as accepting states F ⊆ Q.

A word w ∈ Σ* is accepted by the ε-NFA if there exists a directed path from the initial state q₀ to some final state in F using edges from δ, such that the concatenation of all labels visited along the path yields the word w. The set of all words over Σ* accepted by the automaton is the language accepted by the automaton A.

When speaking of digraph properties of a nondeterministic finite automaton A with state set Q, we naturally address the digraph with vertex set Q induced by its transition relation. Now the theorem is stated as follows.

Eggan's Theorem: The star height of a regular language L equals the minimum cycle rank among all nondeterministic finite automatons with ε-moves accepting L.

Proofs of this theorem are given by Eggan (1963), and more recently by Sakarovitch (2009).