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:
“My advice to those who think they have to take off their clothes to be a star is, once you’re boned, what’s left to create the illusion? Let ‘em wonder. I never believed in givin’ them too much of me.”
—Mae West (1892–1980)
“The height of cleverness is being able to conceal it.”
—François, Duc De La Rochefoucauld (1613–1680)
“The problem for the King is just how strict
The lack of liberty, the squeeze of the law
And discipline should be in school and state....”
—Robert Frost (1874–1963)