The star height problem in formal language theory is the question whether all regular languages can be expressed using regular expressions of limited star height, i.e. with a limited nesting depth of Kleene stars. Specifically, is a nesting depth of one always sufficient? If not, is there an algorithm to determine how many are required? The problem was raised by Eggan (1963).
Read more about Star Height Problem: Families of Regular Languages With Unbounded Star Height, Computing The Star Height of Regular Languages
Famous quotes containing the words star, height and/or problem:
“And though in tinsel chain and popcorn rope
My tree, a captive in your window bay,
Has lost its footing on my mountain slope
And lost the stars of heaven, may, oh, may
The symbol star it lifts against your ceiling
Help me accept its fate with Christmas feeling.”
—Robert Frost (1874–1963)
“To say more than human things with human voice,
That cannot be; to say human things with more
Than human voice, that, also, cannot be;
To speak humanly from the height or from the depth
Of human things, that is acutest speech.”
—Wallace Stevens (1879–1955)
“And just as there are no words for the surface, that is,
No words to say what it really is, that it is not
Superficial but a visible core, then there is
No way out of the problem of pathos vs. experience.”
—John Ashbery (b. 1927)