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:
“I would that we were, my beloved, white birds on the foam of the sea!
We tire of the flame of the meteor, before it can fade and flee;
And the flame of the blue star of twilight, hung low on the rim of the sky,
Has awaked in our hearts, my beloved, a sadness that may not die.”
—William Butler Yeats (1865–1939)
“Much more frequent in Hollywood than the emergence of Cinderella is her sudden vanishing. At our party, even in those glowing days, the clock was always striking twelve for someone at the height of greatness; and there was never a prince to fetch her back to the happy scene.”
—Ben Hecht (1893–1964)
“My problem lies in reconciling my gross habits with my net income.”
—Errol Flynn (1909–1959)