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 obvious parallels between Star Wars and The Wizard of Oz have frequently been noted: in both there is the orphan hero who is raised on a farm by an aunt and uncle and yearns to escape to adventure. Obi-wan Kenobi resembles the Wizard; the loyal, plucky little robot R2D2 is Toto; C3PO is the Tin Man; and Chewbacca is the Cowardly Lion. Darth Vader replaces the Wicked Witch: this is a patriarchy rather than a matriarchy.”
—Andrew Gordon, U.S. educator, critic. “The Inescapable Family in American Science Fiction and Fantasy Films,” Journal of Popular Film and Television (Summer 1992)
“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)
“The great problem of American life [is] the riddle of authority: the difficulty of finding a way, within a liberal and individualistic social order, of living in harmonious and consecrated submission to something larger than oneself.... A yearning for self-transcendence and submission to authority [is] as deeply rooted as the lure of individual liberation.”
—Wilfred M. McClay, educator, author. The Masterless: Self and Society in Modern America, p. 4, University of North Carolina Press (1994)