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:
“The Star that bids the Shepherd fold,
Now the top of Heav’n doth hold,
And the gilded Car of Day,
His glowing Axle doth allay
In the steep Atlantick stream,”
—John Milton (1608–1674)
“If a hermit lives in a state of ecstasy, his lack of comfort becomes the height of comfort. He must relinquish it.”
—Jean Cocteau (1889–1963)
“[How] the young . . . can grow from the primitive to the civilized, from emotional anarchy to the disciplined freedom of maturity without losing the joy of spontaneity and the peace of self-honesty is a problem of education that no school and no culture have ever solved.”
—Leontine Young (20th century)