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:
“Events, actions arise, that must be sung, that will sing themselves. Who can doubt, that poetry will revive and lead in a new age, as the star in the constellation Harp, which now flames in our zenith, astronomers announce, shall one day be the pole- star for a thousand years?”
—Ralph Waldo Emerson (1803–1882)
“To achieve harmony in bad taste is the height of elegance.”
—Jean Genet (1910–1986)
“I tell you, sir, the only safeguard of order and discipline in the modern world is a standardized worker with interchangeable parts. That would solve the entire problem of management.”
—Jean Giraudoux (1882–1944)