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:
“A rocket is an experiment; a star is an observation.”
—José Bergamín (1895–1983)
“The Woodrovian style, at the height of the Wilson hallucination, was much praised by cornfed connoisseurs.”
—H.L. (Henry Lewis)
“The government is huge, stupid, greedy and makes nosy, officious and dangerous intrusions into the smallest corners of life—this much we can stand. But the real problem is that government is boring. We could cure or mitigate the other ills Washington visits on us if we could only bring ourselves to pay attention to Washington itself. But we cannot.”
—P.J. (Patrick Jake)