Every Regular Language Has Generalized Star Height At Most Three

A finite-state machine recognizes a language by reading one letter at a time, updating its state, and accepting or rejecting at the end. A regular expression describes a language through operations on sets of words. The key operation for measuring expression depth is Kleene star: it permits zero or more repetitions of a language.

Star height counts the deepest nesting of stars in an expression. For example, (ab*)* has height two: the star on b sits inside the star around ab*. But that is the height of this particular expression, not necessarily of the language it describes. Another expression for the same language might be shallower.

The manuscript Generalized Star Height at Most Three claims that every regular language over a finite alphabet has an expression of generalized star height at most three, using that same alphabet.^† “Generalized” expressions allow complement as well as the usual operations. Union and concatenation take the maximum height of their inputs; complement preserves height; only star increases it, by one. Complement is relative to all words over the original alphabet: the complement of the empty language is therefore the universal language, with height zero. Star-free does not mean finite.

The bound is a ceiling, not a claim that three layers are necessary. It leaves open whether one layer always suffices. Nor does it bound expression length or the time required to construct an expression; an expression can be shallow and still enormous.

The proof begins by summarizing each word by its effect on a finite machine. These summaries form a finite monoid: they compose associatively, and the empty word acts as the identity. Reading two pieces of a word corresponds to composing their summaries.

It then divides words into complete pieces, called episodes, followed by a remainder. Episodes form a prefix code: no episode is a proper prefix of another. That condition makes the decomposition unique. If two proposed first pieces both fit, one must be a prefix of the other; the code property forces them to be equal. The same reasoning applies at each subsequent boundary. This uniqueness lets the proof combine local computations into a computation for the whole word.

The central difficulty is checking an episode using two independent tests. Cut it into a prefix and suffix. The left test proposes an input state and auxiliary information; the right proposes an output state and its own information. The tests cannot communicate through concatenation. They must nevertheless guarantee that any successful pair beginning at a true boundary consumes exactly the first episode and transmits its prescribed update. Outside a specified exceptional class, every input state must also admit at least one successful split.

A clock restricts which tags on the two sides can be compatible: they must agree, except for one permitted unequal pair. A separate end guard forces the true episode endpoint and a shared clock anchor. To handle the allowed mismatch, the construction can add an affine correction to the state update.

The local recovery step explains why that correction does not permanently change the computation. Write an update as xL + b, where L is linear and b is a fixed translation. Composing it with another affine update, yA + c, gives xLA + bA + c. So a whole sequence of updates still has one linear part and one translation.

Run that same sequence twice: once from input x, producing xL + b, and once from zero, producing b. Subtract the second output from the first, and the translation disappears, leaving xL. The method does not require L to be invertible.

The displayed example uses pairs of bits, with addition modulo two. Its composite sends an input pair (u,v) to (v,1). Starting from (1,1) gives (1,1); starting from (0,0) gives (0,1). Their difference is (1,0), the linear output for (1,1), even though the map discards a coordinate.

To express the recovery as a language condition, require both runs to succeed on the same word, using intersection, and take a finite union over possible translations. Boolean operations add no star. This establishes the local recovery identity; it is not, by itself, a proof of the global theorem.

The global construction has to ensure that the independent tests exist even when a cut hides an interval’s monoid value from both sides. A shift-table lemma supplies a correction: for each tuple and input, some coordinate can vary without changing the corrected output. The correction is fixed before the input is chosen, though the coordinate that works may depend on the input. A test can then check every possible value of the hidden entry.

Local markers provide readable boundaries. Where markers are absent, periodic stretches supply alternative cuts. Exceptional episodes are not discarded: a second split uses earlier candidate cuts and multiple copies of each metadata choice. The exceptional condition serves as a witness to the true origin; a counting argument limits false witnesses so that a usable copy of every choice remains. The suffix must also check its exact end. These clock, marker, and decoding arguments are technical proof obligations; the manuscript’s roadmap does not replace their full details.

The height accounting starts with component tests of height at most one. Exact end rules reduce the unbounded words those tests recognize to finitely many templates: a fixed beginning, repetitions of one fixed non-empty word, and a fixed ending. The accepted repetition counts are eventually periodic. For instance, counts 2, 5, 8, 11, … can be written as two initial copies followed by any number of three-copy blocks, using one star.

Under the split lemma’s hypotheses, if skipped computations have height H, the new computation has height at most max(2, H + 1). The inner split handles the first episode while skipping no earlier computation, so its skipped height is zero and it produces a computation of height at most two. Affine recovery and a linear lift preserve that bound. This inner computation supplies the exception-handling computations required by the outer split. The outer split therefore starts with skipped computations of height at most two and raises the bound to three.

Finally, the construction recovers the original monoid action, attaches a remainder of height at most one, and takes a finite union of accepting products. Concatenation and union add no layer.

The proof’s organizing idea is to reorganize the computation rather than simplify every loop in the machine one by one: uniquely delimited episodes, independently checked splits, and corrections that can later be removed without another star. Two rounds yield the claimed bound over the original alphabet. The empty alphabet is a separate harmless case: its only word is the empty word, so its languages are the empty language and the singleton containing the empty word, both of height zero.