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:
“What is Africa to me:
Copper sun or scarlet sea,
Jungle star or jungle track,
Strong bronzed men, or regal black
Women from whose loins I sprang
When the birds of Eden sang?”
—Countee Cullen (1903–1946)
“It’s the height of folly to want to be the only wise one.”
—François, Duc De La Rochefoucauld (1613–1680)
“Like the effects of industrial pollution ... the AIDS crisis is evidence of a world in which nothing important is regional, local, limited; in which everything that can circulate does, and every problem is, or is destined to become, worldwide.”
—Susan Sontag (b. 1933)