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:
“Relying on any one disciplinary approach—time-out, negotiation, tough love, the star system—puts the parenting team at risk. Why? Because children adapt to any method very quickly; today’s effective technique becomes tomorrow’s worn dance.”
—Ron Taffel (20th century)
“To say more than human things with human voice,
That cannot be; to say human things with more
Than human voice, that, also, cannot be;
To speak humanly from the height or from the depth
Of human things, that is acutest speech.”
—Wallace Stevens (1879–1955)
“Every reform was once a private opinion, and when it shall be a private opinion again, it will solve the problem of the age.”
—Ralph Waldo Emerson (1803–1882)