Formal Definition
More formally, the star height of a regular expression E over a finite alphabet 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.
Read more about this topic: Star Height
Famous quotes containing the words formal and/or definition:
“The formal Washington dinner party has all the spontaneity of a Japanese imperial funeral.”
—Simon Hoggart (b. 1946)
“Was man made stupid to see his own stupidity?
Is God by definition indifferent, beyond us all?
Is the eternal truth man’s fighting soul
Wherein the Beast ravens in its own avidity?”
—Richard Eberhart (b. 1904)