Star height
Encyclopedia
In theoretical computer science
, more precisely in the theory of formal languages, the star height is a measure for the structural complexity
of regular expressions: The star height equals the maximum nesting depth of stars appearing in the regular expression.
The concept of star height was first defined and studied by Eggan (1963).
E over a finite alphabet
A is inductively defined as follows:
Here,
is the special regular expression denoting the empty set and ε the special one denoting the empty word;
E and F are arbitrary regular expressions.
The star height h(L) of a regular language L is defined as the minimum star height among all regular expressions representing L.
The intuition is here that if the language L has large star height, then it is in some sense inherently complex, since it cannot be described
by means of an "easy" regular expression, of low star height.
For illustration, the regular expression
over the alphabet A = {a,b}
has star height 2. However, the described language is just the set of all words ending in an a: thus the language can also be described by the expression
which is only of star height 1. To prove that this language indeed has star height 1, one still needs to rule out that it could be described by a regular
expression of lower star height. For our example, this can be done by an indirect proof: One proves that a language of star height 0
contains only finitely many words. Since the language under consideration is infinite, it cannot be of star height 0.
s. In subsequent years, this relation became known as Eggan's theorem, cf. . 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:
In automata theory, a nondeterministic finite automaton with ε-moves (ε-NFA) is defined as a 5-tuple, (Q, Σ, δ, q0, F), consisting of
A word w ∈ Σ* is accepted by the ε-NFA if there exists a directed path from the initial state q0 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.
Proofs of this theorem are given by , and more recently by .
using only the standard operators set union, concatenation
, and Kleene star
. Generalized regular expressions are defined just as regular expressions, but here also the set complement operator is allowed
(the complement is always taken with respect to the set of all words over A). If we alter the definition such that taking complements does not increase the star height, that is,
we can define the generalized star height of a regular language L as the minimum star height among all generalized regular expressions
representing L.
Note that, whereas it is immediate that a language of (ordinary) star height 0 can contain only finitely many words, there exist infinite
languages having generalized star height 0. For instance, the regular expression
which we saw in the example above, can be equivalently described by the generalized regular expression
,
since the complement of the empty set is precisely the set of all words over A. Thus the set of all words over the alphabet A ending in the letter a has star height one, while its
generalized star height equals zero.
Languages of generalized star height zero are also called star-free languages
. It can be shown that a language L is star-free if and only if its syntactic monoid
is aperiodic
.
Theoretical computer science
Theoretical computer science is a division or subset of general computer science and mathematics which focuses on more abstract or mathematical aspects of computing....
, more precisely in the theory of formal languages, the star height is a measure for the structural complexity
of regular expressions: The star height equals the maximum nesting depth of stars appearing in the regular expression.
The concept of star height was first defined and studied by Eggan (1963).
Formal definition
More formally, the star height of a regular expressionE over a finite alphabet
Alphabet
An alphabet is a standard set of letters—basic written symbols or graphemes—each of which represents a phoneme in a spoken language, either as it exists now or as it was in the past. There are other systems, such as logographies, in which each character represents a word, morpheme, or semantic...
A is inductively defined as follows:
-
, 
, and 
for all alphabet symbols a in A. -
-
Here,
is the special regular expression denoting the empty set and ε the special one denoting the empty word;E and F are arbitrary regular expressions.
The star height h(L) of a regular language L is defined as the minimum star height among all regular expressions representing L.
The intuition is here that if the language L has large star height, then it is in some sense inherently complex, since it cannot be described
by means of an "easy" regular expression, of low star height.
Examples
While computing the star height of a regular expression is easy, determining the star height of a language can be sometimes tricky.For illustration, the regular expression
over the alphabet A = {a,b}
has star height 2. However, the described language is just the set of all words ending in an a: thus the language can also be described by the expression
which is only of star height 1. To prove that this language indeed has star height 1, one still needs to rule out that it could be described by a regular
expression of lower star height. For our example, this can be done by an indirect proof: One proves that a language of star height 0
contains only finitely many words. Since the language under consideration is infinite, it cannot be of star height 0.
Eggan's theorem
In his seminal study of the star height of regular languages, established a relation between the theories of regular expressions, finite automata, and of directed graphDirected graph
A directed graph or digraph is a pair G= of:* a set V, whose elements are called vertices or nodes,...
s. In subsequent years, this relation became known as Eggan's theorem, cf. . We recall a few concepts from graph theory
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
and automata theory
Automata theory
In theoretical computer science, automata theory is the study of abstract machines and the computational problems that can be solved using these machines. These abstract machines are called automata...
.
In graph theory, the cycle rank
Cycle rank
In graph theory, the cycle rank of a directed graph is a digraph connectivity measure proposed first by Eggan and Büchi . Intuitively, this concept measures how close adigraph is to a directed acyclic graph , in the sense that a DAG has...
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
-
- 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, Σ, δ, q0, 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 q0 ∈ 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 q0 to some final state in F using edges from δ, such that the concatenation
Concatenation
In computer programming, string concatenation is the operation of joining two character strings end-to-end. For example, the strings "snow" and "ball" may be concatenated to give "snowball"...
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 rankCycle rankIn graph theory, the cycle rank of a directed graph is a digraph connectivity measure proposed first by Eggan and Büchi . Intuitively, this concept measures how close adigraph is to a directed acyclic graph , in the sense that a DAG has...
among all nondeterministic finite automata with ε-moves accepting L.
Proofs of this theorem are given by , and more recently by .
Generalized star height
The above definition assumes that regular expressions are built from the elements of the alphabet Ausing only the standard operators set union, concatenation
Concatenation
In computer programming, string concatenation is the operation of joining two character strings end-to-end. For example, the strings "snow" and "ball" may be concatenated to give "snowball"...
, and Kleene star
Kleene star
In mathematical logic and computer science, the Kleene star is a unary operation, either on sets of strings or on sets of symbols or characters. The application of the Kleene star to a set V is written as V*...
. Generalized regular expressions are defined just as regular expressions, but here also the set complement operator is allowed
(the complement is always taken with respect to the set of all words over A). If we alter the definition such that taking complements does not increase the star height, that is,
we can define the generalized star height of a regular language L as the minimum star height among all generalized regular expressions
representing L.
Note that, whereas it is immediate that a language of (ordinary) star height 0 can contain only finitely many words, there exist infinite
languages having generalized star height 0. For instance, the regular expression
which we saw in the example above, can be equivalently described by the generalized regular expression
,since the complement of the empty set is precisely the set of all words over A. Thus the set of all words over the alphabet A ending in the letter a has star height one, while its
generalized star height equals zero.
Languages of generalized star height zero are also called star-free languages
Star-free language
A regular language is said to be star-free if it can be described by a regular expression constructed from the letters of the alphabet, the empty set symbol, all boolean operators – including complementation – and concatenation but no Kleene star...
. It can be shown that a language L is star-free if and only if its syntactic monoid
Syntactic monoid
In mathematics and computer science, the syntactic monoid M of a formal language L is the smallest monoid that recognizes the language L.-Syntactic quotient:...
is aperiodic
Aperiodic monoid
In mathematics, an aperiodic semigroup is a semigroup S such that for every x ∈ S, there exists a nonnegative integer n such thatxn = xn + 1.An aperiodic monoid is an aperiodic semigroup which is a monoid...
.